Question

Student Name: Q5-15 pts) Run the Depth First Search algorithm on the following directed acyclic graph (DAG) and determine a topological sort of the vertices as well as identify the tree edges, forward edges and cross edges 3 5 0 2 4 7

Answer 1

Source vertex:0

1. Try edge 0 ? 1
Vertex 1 is unvisited, we have a tree edge.

0 source 7 4

2.Try edge 1 ? 3
Vertex 3 is unvisited, we have a tree edge.

0 source 7 4

3. Try edge 3 ? 2
Vertex 2 is unvisited, we have a tree edge.

0 source 7 4

4. Try edge 2 ? 5
Vertex 5 is unvisited, we have a tree edge.

5 0 source 7 4

5. Finish DFS(5), backtrack to DFS(2).

0 source 7 4 2

6.Try edge 2 ? 6
Vertex 6 is unvisited, we have a tree edge.

0 source 7 4

7. Try edge 6 ? 7
Vertex 7 is unvisited, we have a tree edge.

0 source 7 4

8.Try edge 7 ? 4
Vertex 4 is unvisited, we have a tree edge.

0 source 7 4

9.Finish DFS(4), backtrack to DFS(7).

0 source 7 4

10. Finish DFS(7), backtrack to DFS(6).

0 source 4

11.Finish DFS(6), backtrack to DFS(2).

12. Finish DFS(2), backtrack to DFS(3).

13.Try edge 3 ? 5
Vertex 5 is visited, we have a forward/cross edge.

0 source 4 2

14.Try edge 3 ? 6
Vertex 6 is visited, we have a forward/cross edge.

0 source 7 4

15.Try edge 3 ? 7
Vertex 7 is visited, we have a forward/cross edge.

0 source 4

16.Finish DFS(3), backtrack to DFS(1).

17. Try edge 1 ? 7
Vertex 7 is visited, we have a forward/cross edge.

18 . Finish DFS(1), backtrack to DFS(0).

19. Try edge 0 ? 4
Vertex 4 is visited, we have a forward/cross edge.

20. Try edge 0 ? 7
Vertex 7 is visited, we have a forward/cross edge.

21.DFS(0) is completed. Red/grey/blue edge is tree/cross/forward/backedge of the DFS spanning tree, respectively.

0 1 3 source 7 4 2

Topological sort:

Vertex 0 has not been visited.

DFS(0).

Try edge 0 ? 1.
List = [].

Vertex 1 has not been visited, continue.
List = [].

DFS(1).

Try edge 1 ? 3.
List = [].

Vertex 3 has not been visited, continue.
List = [].

DFS(3).

Try edge 3 ? 2.
List = [].

Vertex 2 has not been visited, continue.
List = [].

DFS(2)

Try edge 2 ? 5.
List = [].

Vertex 5 has not been visited, continue.
List = [].

DFS(5)

DFS(5) is completed, add {u} to the back of the list.
List = [5].

Try edge 2 ? 6.
List = [5].

Vertex 6 has not been visited, continue.
List = [5].

DFS(6).

Try edge 6 ? 7.
List = [5].

Vertex 7 has not been visited, continue.
List = [5].

DFS(7).

Try edge 7 ? 4.
List = [5].

Vertex 4 has not been visited, continue.
List = [5].

DFS(4)

DFS(4) is completed, add {u} to the back of the list.
List = [5,4].

DFS(7) is completed, add {u} to the back of the list.
List = [5,4,7].

DFS(6) is completed, add {u} to the back of the list.
List = [5,4,7,6].

DFS(2) is completed, add {u} to the back of the list.
List = [5,4,7,6,2].

Try edge 3 ? 5.
List = [5,4,7,6,2].

Vertex 5 has been visited, ignore this edge.
List = [5,4,7,6,2].

Try edge 3 ? 6.
List = [5,4,7,6,2].

Vertex 6 has been visited, ignore this edge.
List = [5,4,7,6,2].

Try edge 3 ? 7.
List = [5,4,7,6,2].

Vertex 7 has been visited, ignore this edge.
List = [5,4,7,6,2].

DFS(3) is completed, add {u} to the back of the list.
List = [5,4,7,6,2,3].

Try edge 1 ? 7.
List = [5,4,7,6,2,3].

Vertex 7 has been visited, ignore this edge.
List = [5,4,7,6,2,3].

DFS(1) is completed, add {u} to the back of the list.
List = [5,4,7,6,2,3,1].

Try edge 0 ? 4.
List = [5,4,7,6,2,3,1].

Vertex 4 has been visited, ignore this edge.
List = [5,4,7,6,2,3,1].

Try edge 0 ? 7.
List = [5,4,7,6,2,3,1].

Vertex 7 has been visited, ignore this edge.
List = [5,4,7,6,2,3,1].

DFS(0) is completed, add {u} to the back of the list.
List = [5,4,7,6,2,3,1,0].

3 7 3 2 6 4 1-75

Topological Sort is completed after reversing the list.
List = [0,1,3,2,6,7,4,5]