$25
CS5800-Homework 10 Solved
1 Exercise 22.1-5
For the adjacency-matrix representation of a graph G = (V,E), we assume that the vertices are numbered 1,2,...,|V | in some arbitrary manner. Then the adjacencymatrix representation of a graph G consists of a |V | × |V | matrix A = (aij) such that
(
1, if (i,j) ∈ E f(n) =
0, otherwise n
We have algorithm: .
1: for i = 0 to V do
2: for j = 0 to V do
3: G2[i][j] ← 0
4: for k = 0 to V do
5: if G[i][k] == 1 and G[k][j] == 1 then
6: G2[i][j] = 1
7: end if
8: end for
9: end for
10: end for
11: return G2
The G2 may be computed in V 3 times, so the running time is O(V 3).
2 Exercise 22.2-6
Let G = (V,E) be the first graph and G′ = (V,Eπ) be the second graph, and let 1 be the source vertex.
Figure 1: first graph Figure 2: second graph
The breadth-first search systematically explores the edges of G to ”discover” every vertex that is reachable from 1. Suppose that 2 proceeds 5 in the adjacency list of 1.We could see that Eπ will never be produced by running breadth-first search on G.
• If 5 precedes 2 in the Adj[1]. We will dequeue 5 before 2, so 3.π and 4.π are both 5, which is not true.
• If 2 preceded 5 in the Adj[1]. We will dequeue 2 before 5, so 3.π and 4.π are both 2, which again is not true.
Therefore, the set of edges Eπ cannot be produced by running breadth-first search on G no matter how the vertices are ordered in each adjacency list.
3 Exercise 22.2-7
Color the vertices of graph of rivalries by two colors, ”babyface” and ”heel”. We use BFS of each connected component to get the distance value for each vertex. 1) Initialize graph G(V,E) source vertex’s color is ”babyface”.
2) Assign all wrestlers whose distance is even to be ”babyface” color, and all wrestlers whose distance is odd to be ”heel” color.
3) Verify each vertex’s color. If vertex doesn’t have any color, then its adjacency vertex will be colored by a different color. Otherwise, vertex has color and its color same with its adjacency vertex color, then it means that it is not possible to find a designation.
We have algorithm to verify each vertex’s color:
.
1: for each vertex u ∈ G.V − {s} do
2: if u.color == UNCOLORED then
3: u.color ← ”heel”
4: if adjacency vertex of u color is ”heel” then
5: adjacency vertex of u color ← ”babyface”
6: else
7: adjacency vertex of u color ← ”heel”
8: end if
9: for neighbor of adjacency vertex of u do
10: if neighbor.color == UNCOLORED then
11: neighbor.color = adjacency vertex of u color
12: else
13: if neighbor.color ̸= adjacency vertex of u color then
14: return FALSE
15: end if
16: end if
17: end for
18: end if
19: end for
20: return TRUE
Time analysis: this algorithm will take O(n + r) time for the BFS where n is the number of vertex and r is the number of edge in graph G.
4 Exercise 22.3-7
Algorithm 1 Rewrite DFS using a stack to eliminate recursion
1: function DFS(G)
2: for each vertex u ∈ G.V do
3: u.color = WHITE
4: u.π = NIL
5: end for
6: time ← 0
7: for each vertex u ∈ G.V do
8: if u.color == WHITE then
9: DFS-VISIT(G,u)
10: end if
11: end for
12: end function
13:
14:
15: function DFS-VISIT(G,u)
16: for each vertex u ∈ G.V do
17: u.color = WHITE
18: u.π = NIL
19: end for
20: stack.push(u)
21: while stack is not empty do
22: x = stack.top
23: flag = TRUE
24: for each v ∈ G : Adj[x] do ▷ explore edge (x, v)
25: if v.color == WHITE then
26: v.π = x
27: flag = FALSE
28: time = time + 1 29: v.d = time
30: v.color = GRAY
31: stack.push(v)
32: end if
33: end for
34: if flag == TRUE then ▷ if all neighboring vertex of the element at the top
35: y = stack.pop ▷ of stack are not white (all marked as GRAY or
36: y.color = BLACK ▷ BLACK), then the stack pop
37: time = time + 1
38: y.f = time
39: end if
40: end while
41: end function
5 Exercise 22.3-10
We can define four edge types in the depth-first forest Gπ produced by a depthfirst search on G : Tree edge, Back edge, Forward edge, and Cross edge. The DFS algorithm has enough information to classify some edges as it encounters them. The key idea is that when we first explore an edge (u,v), the color of vertex v tells us something about the edge:
• WHITE indicates a tree edge,
• GRAY indicates a back edge, and
• Black indicates a forward or cross edge
The first case is immediate form the specification of the algorithm. For the second case, observe that the GRAY vertices always from a linear chain of descendants corresponding to the stack of active. DFS-VISIT invocations. Exploration always proceeds from the deepest GRAY vertex, so an edge that reaches another GRAY vertex has reached an ancestor. The third case handles the remaining possibility: edge (u,v) is a forward edge if u.d < v.d and a cross edge if u.d > v.d.
Algorithm 2 Prints out every edge in the directed graph G with its type
1: function DFS(G)
2: for each vertex u ∈ G.V do
3: u.color = WHITE
4: u.π = NIL
5: end for
6: time ← 0
7: for each vertex u ∈ G.V do
8: if u.color == WHITE then
9: DFS-VISIT-PRINT(G,u)
10: end if
11: end for
12: end function
13:
14: function DFS-VISIT-PRINT(G,u)
15: time = time + 1 ▷ white vertex u has just been discovered 16: u.d = time
17: u.color = GRAY
18: for each v ∈ G.Adj[u] do ▷ explore edge (u, v)
19: if v.color == WHITE then
20: print ”(u, v) is a tree edge”
21: v.π = x
22: DFS-VISIT-PRINT(G,v)
23: else
24: if v.color == GRAY then
25: print ”(u, v) is a back edge”
26: else
27: if v.d > u.d then
28: print ”(u, v) is a forward edge”
29: else
30: print ”(u, v) is a cross edge”
31: end if
32: end if
33: end if
34: end for
35: end function
An undirected graph may entail some ambiguity in how we classify edges, since (u,v) and (v,u) are really the same edge. In such a case, we classify the edge as the first type in the classification list that applies. Equivalently, we classsify the edge according to whichever of (u,v) or (v,u) the search encounters first. For DFS-VISIT-PRINT algorithm, if G is undirected we don’t need to make any modifications.
6 Exercise 22.3-12
On the basic of DFS, we could add a numerical identifier cc of connected components to count how many connected components. The input graph G may be undirected or directed. The variable time is a global that used for time stamping and DFS-VISIT procedures to assign values to the cc attributes of vertices.
Algorithm 3 Identify the connected components of G
1: function DFS(G)
2: for each vertex u ∈ G.V do
3: u.color = WHITE
4: u.π = NIL
5: end for
6: time ← 0
7: k ← 1
8: for each vertex u ∈ G.V do
9: if u.color == WHITE then
10: u.cc = k
11: k = k + 1
12: DFS-VISIT(G,u)
13: end if
14: end for
15: end function
16:
17: function DFS-VISIT(G,u)
18: time = time + 1
▷ white vertex u has just been discovered
19: u.d = time
20: u.color = GRAY
21: for each v ∈ G.Adj[u] do
▷ explore edge (u, v)
22: v.cc = u.cc
23: if v.color == WHITE then
24: v.π = x
25: DFS-VISIT(G,v)
26: end if
27: end for
28: u.color = BLACK
29: time = time + 1
30: u.f = time
31: end function
▷ blacken u; it is finished
7 Exercise 22.4-5
Algorithm 4 Topological sorting to find a vertex of in-degree 0
1: function Topological-Sort(G)
2: for each vertex u ∈ G.V do
▷ initialize in-degree
3:
u.in − degree = 0
4:
end for
5:
for each vertex u ∈ G.V do
▷ compute in-degree
6:
for each vertex v ∈ G.Adj[u] do
7:
v.in − degree = v.in − degree + 1
8:
end for
9:
end for
10:
Q ← ∅
▷ initialize queue
11:
for each vertex u ∈ G.V do
12:
if u.in − degree == 0 then
13:
ENQUEUE(Q,u)
14:
end if
15:
end for
16:
while Q is not ∅ do
17:
u = DEQUEUE(Q)
18:
Output u
19:
for each vertex v ∈ G.Adj[u] do
20:
v.in − degree = v.in − degree − 1
21:
if v.in − degree == 0 then
22:
ENQUEUE(Q,v)
23:
end if
24:
end for
25:
end while
26:
for each vertex u ∈ G.V do
▷ check for cycles
27:
if u.in − degree ̸= 0 then
28:
report there is a cycle
29:
end if
30: end for
31: end function
To find and output vertices of in-degree 0, we compute all vertices in-degree by making pass through all the edges and incrementing the in-degree of each vertex an edge enters. If there are no cycles, all vertices are output. Otherwise, not all vertices will be output because some in-degree never become 0.
8 All paths from s to t must have a common vertex
Thinking of any breadth-first spanning tree T of graph G with s as the root. In T, each node v has a level, which is the number of edges in a shortest path from s to v. Since every path from s to t has at least , node t occurs at a level ≥ l. Thinking of level 1 through , the total number of nodes in level 1 through is at most |v| − 2 (Since node s and t doesn’t in these level). If each of these level has 2 or more nodes, then total number of nodes in G will exceed |V |. Therefore, there must be a level in the range 1 through containing just one node v which is a common vertex of s to t. We have algorithm:
• Construct a BFS of G, run it starting from node s. For each level i, construct the list L[i] of the node
• Find a level j where 1 such that L[j] has only one node v
• Output node v
For the running time, the step 1 takes O(V +E) time since we construct a BFS of G. Step 2 takes O(V ) time and step 3 takes O(1) time. Therefore, the algorithm runs in O(V + E) time.
9 Exercise 23.1-3
Algorithm 5 Growing a minimum spanning tree
1: function CENTRIC-MST(G,w)
2: A ← ∅
3: while A does not from a spanning tree do
4: find an edge(u,v) that is safe for A
5: A = A ∪ {(u,v)}
6: end while 7: return A
8: end function
In this CENTRIC-MST, prior to each iteration, A is a subset of some minimum spanning tree. At each step, we determine an edge (u, v) that we can add to A without violating this invariant, and we can add it safely to A while maintaining the invariant. Assume we’ve already get a set of edges A, let’s get rid of an edge (u, v), then draw a cut. In this case, our strategy is to choose a light edge because the cut respects A and (u, v) is a light edge for this cut.
10 Exercise 23.2-2
Algorithm 6 Prim’s algorithm runs in O(v2) time
1: function MST-Prim(G,w,r) 2: for each vertex u ∈ G.V do
3:
u.key = ∞
4:
u.π = NIL
5:
end for
6:
r.key = 0
7:
Q = G.V
8:
while Q is not ∅ do
9:
u = EXTRACT-MIN(Q)
10:
for each vertex v ∈ G.Adj[u] do
11:
if MATRIX[u][v] == 1 and v ∈ Q and w(u,v) < v.key then
12:
v.π = u
13:
v.key = w(u,v)
14:
end if
15:
end for
16: end while
17: end function
11 Exercise 23.2-4
The running time of Kruskal’s algorithm for a graph G = (u,v) depends on how we implement the disjoint-set data structure. We assume that we use the disjoint-set-forest implementation of Book Section 21.3 with the union-by-rank and path-compression heuristic, since it is the asymptotically fastest implementation known. The total running time is O((V + E)α(V )) where α is very slowly growing function defined in Book Section 21.4. Assume graph G is connected, we have |E| ≤ |V | − 1, and so the disjoint-set operations take O(Eα(V )) time. Moreover, since α(|V |) = O(lgV ) = O(lgE), the total running time of Kruskal’s algorithm is O(ElgE).
If alledge weights are integers in the range from 1 to |V |, then we could sort the edges in O(V + E) time using counting sort. Since we assume the graph G is connected, V = O(E) and so the sorting time is reduced to O(E). The total running time would be O(V + E + Eα(V )) = O(Wα(V )) since V = O(E) and E = O(Eα(V )).
If the edge weights are integers in the range from 1 to w for some constant w, then we still apply counting sort to sort edges. The sorting time would take O(E +w) = O(E) time since w is a constant. The total running time is O(Eα(V )).
12 Exercise 23.2-5
The running time of Prim’s algorithm depends on how we implement the minpriority queue Q. We can improve the asymptotic running time of Prim’s algorithm by using Fibonacci heaps. Book Chapter 19 shows that if a Fibonacci heap holds |V | elements, an EXTRACT-MIN operation takes O(lgV ) amortized time and a DECREASE-KEY operation takes O(1) amortized time. Therefore, if we use a Fibonacci heap to implement the min-priority queue Q, the running time of Prim’s algorithm improves to O(E + V lgV ).
If the edge weights are integers in the range from 1 to w for some constant w, we can implement the queue as an array Q[0...w + 1]. EXTRACT-MIN scan the array and find the first non-empty slot in O(1) time, and DECREASE-MIN also takes O(1) time. The total running time is O(E).
