22.5. Strongly Connected Components in Directed Graphs

Try these first

1. 1.

   What does it mean for two vertices to be strongly connected?

   Hint

   Think about both directions of travel.

2. 2.

   What type of search algorithm is primarily used to find SCCs?

   Hint

   Recall the deep exploration technique.

3. 3.

   What does it mean for a graph to have strongly connected components?

   • Every vertex can reach every other vertex.
   • There are no edges.
   • The graph is acyclic.

   Hint

   Consider the definition of strong connectivity.

4. 4.

   Is a back edge in DFS indicative of a cycle in a graph?

   • True
   • False

   Hint

   Think about the directionality of edges.

5. 5.

   Given a directed graph with vertices A, B, C, and edges (A -> B), (B -> C), (C -> A), identify all SCCs and classify edges.

   Hint

   Visualize or draw the graph to better understand the connections.

6. 6.

   For a directed graph example: A -> B, B -> C, C -> D, and D -> B, analyze the edges and determine the presence of SCC.

   Hint

   Trace the paths to verify strong connectivity in the graph.