Consider the graph shown on the right. Find the strongly connected components of the graph. Whenever...

 

Transcribed Image Text:

Consider the graph shown on the right. Find the strongly connected components of the graph. Whenever you use DFS and there is a choice of nodes to explore, always pick the one that is alphabetically first. a) (6 points) Run DFS on the reverse graph starting at node A. Show the discovery and finish times of each vertex. b) (6 points) Run DFS again, to discover the strongly connected components. What is the order the components are discovered? c) (3 points) Draw the DAG of the components. Identify all source and sink components. What is the minimum number of edges that can be added to make the entire graph strongly connected? B E H Consider the graph shown on the right. Find the strongly connected components of the graph. Whenever you use DFS and there is a choice of nodes to explore, always pick the one that is alphabetically first. a) (6 points) Run DFS on the reverse graph starting at node A. Show the discovery and finish times of each vertex. b) (6 points) Run DFS again, to discover the strongly connected components. What is the order the components are discovered? c) (3 points) Draw the DAG of the components. Identify all source and sink components. What is the minimum number of edges that can be added to make the entire graph strongly connected? B E H

Answer rating: 100% (QA)

a Discovery and finish times for each vertex in the reverse graph star... View the full answer