Chapter 22 Answers

Graph Basics

Question for the directed graph at right

• Is 2 1? Yes

• Is x y  for all x, y Î V? Yes

• Is the Web a directed or undirected graph?  Directed

• What does in-degree and out-degree correspond to on the Web?  In-degree is # of href's to a URL; out-degree is # of href's from a page (URL)

• Is x y  for all x, y Î V where V is all Web pages? No, since some parts of the Web are unreachable (server dead, blocked access, pages that are too deeply linked, etc)

• What does Google Google? A small subset of the Web comprised of submitted sites and sites discovered via out-links while spidering but not all pages on a site are examined or all text on a page.

Question for the directed graph at right

• Give one cycle. <1,2,3,4,1>

• Is the graph a DAG? No

• Give an example of a DAG. A binary search tree.

Question for the directed graph at right

• Is the graph strongly connected? Yes

Question - 5 × 5 matrix

• Directed or undirected graph? Directed because edge connections are not symmetric, also loop of (5,5).

• V? {1,2,3,4,5}

• |V|? 5

• E? {(1,2),(1,5),(2,1),(2,3),(2,4),(2,5),(3,2),(3,4),(4,2),(4,3),(4,5),(5,2),(5,5)}

• |E|? 13

• (1, 2) Î E? Yes

• (2, 1) Î E? Yes

• Out-degree of vertex 4? 3

• In-degree of vertex 2? 4

• Which edge is missing for vertex 5? (5,1)

Question

• Suggest an algorithm to search a directed graph for a strongly connected graph (every vertex is reachable) given some starting vertex.
  • A solution could iterate starting from each vertex,
  • recursively exploring the edge to adjacent vertices,
  • marking each vertex when visited,
  • stopping further exploring when reaching already visited vertex.
  • When all edges from starting vertex explored, if count of visited equals count of vertices in graph then continue until all vertices have been found to connect to all other vertices.
• What problem must be handled on the directed graph above? Looping.
• How might the problem be resolved? Marking vertices as visited.
• What would you guess the worst case performance for an algorithm searching for a vertex in the directed graph at right? O(|E|)
• What would you guess the worst case performance of the algorithm for determining a strongly connected graph? O(|V|*|E|)

BFS

Question - Would it be possible for breadth first search starting at Arad to reach Neamt on the way to Fagaras? No. What about depth first? Yes.

Question After executing BFS,

1. What does d[ x ] mean? The distance in edges from vertex s to vertex x.
2. What does p[ x ] mean? Equals u, the last edge (u, x) from s to vertex x.
3. What is the maximum distance to source s? 3
4. Trace the path starting at p[ y ] to the source s. y"x"w"s

   w	x	y
   s	w	x

BFS (G, s)          -- Initialize arrays 1 for each vertex u Î V[G] - {s} do 2    color[u] ¬ WHITE 3    d[u] ¬ ¥ 4    p[u] ¬ NIL 5 color[s] ¬ GRAY 6 d[s] ¬ 0 7 p[s] ¬ NIL 8 Q ¬ Æ 9 Enqueue (Q, s) 10 while Q ¹ Æ do 11    u ¬ Dequeue (Q) 12    for each v Î Adj[u] do 13        if color[v] = WHITE then 14           color[v] ¬ GRAY 15           d[v] ¬ d[u] + 1 16           p[v] ¬ u 17           Enqueue (Q, v) 18    color[u] ¬ BLACK

Question Execute the BFS on source vertex 5, visiting adjacent vertices at line 12 in numerical order.   1 2 3 4 5 p NIL NIL NIL NIL NIL d ¥ ¥ ¥ ¥ 0 color WHITE WHITE WHITE WHITE GRAY Q=<5>   1 2 3 4 5 p 5 5 NIL 5 NIL d 1 1 ¥ 1 0 color GRAY GRAY WHITE GRAY BLACK Q=<1,2,4>   1 2 3 4 5 p 5 5 NIL 5 NIL d 1 1 ¥ 1 0 color BLACK GRAY WHITE GRAY BLACK Q=<2,4>   1 2 3 4 5 p 5 5 2 5 NIL d 1 1 2 1 0 color BLACK BLACK GRAY GRAY BLACK Q=<4,3>   1 2 3 4 5 p 5 5 2 5 NIL d 1 1 2 1 0 color BLACK BLACK GRAY BLACK BLACK Q=<3>   1 2 3 4 5 p 5 5 2 5 NIL d 1 1 2 1 0 color BLACK BLACK BLACK BLACK BLACK Q=Æ   Count the number of times Line 12 is executed. 14 Did it agree with |V|+|E|+1? Not quite. |V|+|E|+1=5+7+1=13? Vertex Count 1 2 2 4 3 2 4 3 5 3 Total 14 Draw BFS tree.     5   / | \  1 2 4     |     3

Analysis - BFS is O(V+E) due to line 12.

• O(V) because every vertex is enqueued at most once, Line 17.
• O(E) because every vertex is dequeued at most once and we examine (u, v) only when u is dequeued. Therefore, every edge examined at most once if directed, at most twice if undirected.

Note that this is for an adjacency list representation.

Question

1. Is every vertex visited for an undirected graph? Yes, if all vertices are reachable, x y  for all x, y Î V. a directed graph? No. See the graph at right.
2. Give an example that contradicts the statement "every edge is examined in an undirected graph". If the graph is not strongly connected.
3. What is the purpose of the queue? Maintain the reachable vertices that have not been explored. Think about what happens in Lines 12-17.
4. What would be the running time for an adjacency matrix representation? Hint: Consider how edges are represented at right. O(V²)
5. Run BFS on the graph at right starting at D.

   	A	B	C	D	E
   p	NIL	NIL	NIL	NIL	NIL
   d	¥	¥	¥	0	¥
   color	WHITE	WHITE	WHITE	GRAY	WHITE

    Q={D}

   	A	B	C	D	E
   p	NIL	D	NIL	NIL	D
   d	¥	1	¥	0	1
   color	WHITE	GRAY	WHITE	BLACK	GRAY

   Q={B,E}

   	A	B	C	D	E
   p	NIL	D	B	NIL	D
   d	¥	1	2	0	1
   color	WHITE	BLACK	GRAY	BLACK	GRAY

   Q={E,C}

   	A	B	C	D	E
   p	NIL	D	B	NIL	D
   d	¥	1	2	0	1
   color	WHITE	BLACK	GRAY	BLACK	BLACK

   Q={C}

   	A	B	C	D	E
   p	NIL	D	B	NIL	D
   d	¥	1	2	0	1
   color	WHITE	BLACK	BLACK	BLACK	BLACK

   Q={}

    

6. Draw the resulting breadth-first tree(s).

          D
        /    \
      B      E
      |
      C

7. We stated that is O(V+E). From Question e, is it also W(V+E)? No, if we had started at E, W(1).

 

Shortest paths

• BFS finds the shortest path from source vertex to all other reachable vertices in graph. The text gives a proof of correctness for the BFS algorithm.

Question - For the graph below.

1. Suppose we reran BFS with a different source, would the results be the same? No
2. What is the distance to s from y? 3
3. What is the shortest path to s from y? s-w-x-y
4. Give an undirected graph that has the shortest path length |V|, the path includes every vertex. Simplest is when no vertex is adjacent to no more than two vertices.
5. Give an algorithm to print the vertices in the shortest path from any vertex to the source.

   --  pre: BFS has been run on G with vertex s, vÎV[G] -- post: the shortest path from s to v is printed if a path exists Print-Path( v ) while v ¹ NIL do output v v ¬ p[v]

	r	s	t	u	v	w	x	y
p	s	NIL	w	t	r	s	w	x
d	1	0	2	3	2	1	2	3

 

DFS

Question

• Suppose V[G] taken in order of {u,v,w,x,y,z}. What is the next value of u of DFS used in calling DFS-Visit(u) at line 7? w
• Finish DFS.
• Where is the FIFO stack that maintains the discovered but not finished vertices? The stack is maintained by the recursion on DFS-Visit at line 7.

Question - Use graph at right.

1. Give the DFS solution visiting vertices in alphabetical order.

   A at DFS line 5.  B, C, B at DFS-Visit line 4.

   	A	B	C	D	E
   p	NIL	A	B	NIL	NIL
   d	1	2	3
   f	6	5	4
   color	BLACK	BLACK	BLACK	WHITE	WHITE

   D at DFS line 5. B, E at DFS-Visit line 4.

   	A	B	C	D	E
   p	NIL	A	B	NIL	D
   d	1	2	3	7	8
   f	6	5	4	10	9
   color	BLACK	BLACK	BLACK	BLACK	BLACK

2. Is every vertex visited for an undirected graph? Yes. a directed graph? Yes. Line 5 iterates over all vertices.
3. Is every path explored? Yes. Explain using graph. Line 5 iterates over all vertices and line 4 iterates over all adjacent vertices (i.e. paths).
4. BFS requires a queue to maintain a list of those vertices discovered but not yet visited, DFS does not. Why not? BFS discovers all new (WHITE) adjacent vertices first before exploring, queuing newly discovered vertices for later exploration. DFS discovers a new vertex and then recursively fully explores the vertex; recursion at line 7 of DFS-Visit maintains a LIFO list of adjacent vertices to discover and explore.

Predecessor subgraph p

G_p=(V, E_p)

E_p={(p[v], v) : v Î V  and p[v] ¹ NIL }

Example: (p[x], x) = (y, x)

E_p={(u, v), (v, y), (y, x), (w, z)} for above figure

	u	v	w	x	y	z
p	NIL	u	NIL	y	v	w
d	1	1	9	4	3	10
f	8	7	12	5	6	11

Question - For above graph.

1. Trace the path using the predecessor subgraph p starting at x. {(x,y), (y,v), (v,u)}
2. Draw the resulting depth-first tree(s).

        u             w
        |              |
        v             z
        |
        y
        |
        x  

3. With 10 vertices in a graph, what is the maximum finish time? 20
4. Do you agree or disagree with the statement "Depth first search is a good way of establishing the nature of the connectivity in a graph. You can build a table out of the results of a search showing which vertices are reachable from which other vertices."? Disagree for our implementation. DFS is guaranteed to fully explore all vertices in a graph but creates subgraphs when multiple paths to a vertex; the path connects to only one of the ancestors.

Classification of edges

Question - Classify each edge of the graph below left for the DFS results of below right.

A B C D E p NIL A B NIL D d 1 2 3 7 8 f 6 5 4 10 9 Tree - (A,B), (B,C), (D,E) Back - (C,B) Forward - none Cross - (D,B)

Parenthesis theorem

For all u and v, exactly one of the following holds: u and v are in different branches or trees, neither of u and v is a descendant of the other: d[u] < f [u] < d[v] < f [v] or d[v] < f [v] < d[u] < f [u] v is a descendant of u: d[u] < d[v] < f [v] < f [u] u is a descendant of v: d[v] < d[u] < f [u] < f [v] . So d[u] < d[v] < f [u] < f [v] cannot happen. Like parentheses: OK: ( ) [ ] ( [ ] ) [ ( ) ] Not OK: ( [ ) ] [ ( ] ) Question What is implied by: d[ s ] < d[ w ] < f[ w ] < f[ s ]    w is a descendant of s, (b) at left. f[ x ] < d[ w ]                            x and w are in different branches of DFS tree, not ancestor or descendant.

Topological sort

Question

• From this DAG could you reasonably convince yourself that C251 could be skipped? Yes.
• Is C201 ® C343 ® C251 valid? No.
• How many valid ways could you order courses starting with C201 to C343? 2.
• How many valid ways could you order courses starting with C201 to B490? 3.

 

Question - Which of the following are invalid orderings and why?

1. ADEBC Yes. No (A,D) or (D,A) path so either AD or DA order valid.
2. CBAED No. (B,C) and (E,C) path requires C come after both.
3. ABCDE No. (E,C) path requires C come after E.
4. DECAB No. (B,C) path requires C come after B.

Question

• List the items in topologically sorted order. Using f value from (b) is: socks, ..., jacket.
• What can you say about the relationship between finish time and topological ordering? The last finished is the first in the list.
• Must the professor put on his socks and undershorts in that order? That is could the order be switched? Yes, there is no connecting path.
• When can our professor (according to the sort) put on his pants? After putting on the undershorts.
• When can our professor (according to the sort) put on his watch? Anytime.
• What is the complexity of the Topological-Sort algorithm? That of DFS: Q(V + E).
• Compute the DFS of the DAG at right.

  	C1	C2	C3	C4	C5
  p	NIL	NIL	C1	C3	C4
  d	1	9	2	3	4
  f	8	10	7	6	5

• Give a topological sort for the DAG at right. Are other sorts possible? C2, C1, C3, C4, C5. Yes: C1, C2, C3, C4, C5.
• From the following DFS table, what is the topological order? w, z, u, v, y, x

	u	v	w	x	y	z
p	NIL	u	NIL	y	v	w
d	1	1	9	4	3	10
f	8	7	12	5	6	11

SCC

Example: Figures at right

    (a) G.    DFS trees:  

b        c
|       /   \
e     d     g
|           /  \
a         f     h

d[b] < d[e] < d[a] < f[a] < f[e] < f[b]

  (b       (e        (a       a)       e)       b)

Question: Give the parenthesization for DFS tree rooted at c.

(c         (g        (f        f)     (h       h)        g)     (d        d)      c)

d[c] < d[g] < d[f] < f[f]< d[h] < f[h]  < f[g]< d[d] < f[d] < f[c]

Question: Is f(gf) > f(cd)? yes.

                Can you tell from the DFS G^T table below? Yes, all finish times of cd < finish times of gf.

                What does that mean?  That cd and gf form SCC's.