Strongly Connected Components: Kosaraju u0026 Tarjan Algorithms Quiz Quiz

Explore key concepts of strongly connected components in directed graphs with a focus on Kosaraju’s and Tarjan’s algorithms. This quiz is designed to reinforce understanding of SCC definitions, algorithm steps, and practical examples in graph theory.

1. Definition of Strongly Connected Component

   What best describes a strongly connected component (SCC) in a directed graph?

   1. A maximal subgraph where every vertex is reachable from every other vertex within the subgraph
   2. A set of vertices with no incoming edges
   3. A subgraph that contains a cycle
   4. A subgraph where all outgoing edges leave the component

   Explanation: A strongly connected component is defined as a maximal set of vertices in a directed graph such that every vertex is reachable from every other vertex in this set. Option B incorrectly describes a sink, not an SCC. Option C refers to a source set, not to SCCs. Option D only requires a cycle but misses the maximal reachability property needed for SCCs.

2. Kosaraju's First Step

   What is the first major step in Kosaraju’s algorithm for finding SCCs in a directed graph?

   1. Sort the vertices by their degrees
   2. Perform a depth-first search (DFS) and record the order of completion
   3. Find all vertices with no incoming edges
   4. Reverse all edges of the graph

   Explanation: Kosaraju’s algorithm begins with a full DFS on the original graph, noting the finishing order of vertices. Reversing edges comes after this initial step. Finding vertices with no incoming edges and sorting by degree are not required in Kosaraju’s method.

3. Understanding Tarjan’s Low Link Value

   In Tarjan’s algorithm, what does the 'low-link' value of a node represent?

   1. The number of strongly connected components found so far
   2. The number of edges coming into the node
   3. The total degree of the node in the graph
   4. The smallest discovery time reachable from the node by traversing zero or more edges

   Explanation: Tarjan’s low-link value for each node indicates the earliest visited node reachable from the subtree rooted at that node, including itself, via DFS. Option B is the in-degree, not low-link. Option C defines an unrelated count. Option D references total degree but low-link is based on traversal, not connectivity degree.

4. Second Pass in Kosaraju's Algorithm

   What is the purpose of the second pass in Kosaraju's algorithm after reversing the graph’s edges?

   1. To discover and separate all the strongly connected components
   2. To find a minimum spanning tree
   3. To check for cycles in the graph
   4. To calculate shortest paths between all vertex pairs

   Explanation: The second pass runs DFS in the order determined by the finishing times, revealing distinct SCCs. Detecting cycles, finding minimum spanning trees, and shortest path calculations are not objectives of this step in Kosaraju’s algorithm.

5. Stack Usage in Tarjan’s Algorithm

   Why does Tarjan’s algorithm use a stack to keep track of nodes during traversal?

   1. It keeps only the leaf nodes for quick access
   2. It helps track the nodes currently in the current DFS path and SCC under consideration
   3. It is required only to save final SCC representatives
   4. It stores the nodes for topological sorting

   Explanation: Tarjan’s algorithm uses a stack to keep track of active nodes as it traverses the graph using DFS; this ensures it correctly groups nodes into SCCs when low-link values match. Storing for topological sorting or for final representatives are not the purposes in Tarjan’s context. Keeping leaf nodes alone does not track SCC paths.

6. Identifying SCCs in an Example Graph

   Given a directed graph with edges: 1→2, 2→3, 3→1, 4→5, which of the following is one of its SCCs?

   1. Vertices 1, 2, 3
   2. Vertices 3 and 5
   3. Vertices 2 and 4
   4. Vertices 4, 1, 5

   Explanation: Vertices 1, 2, and 3 form a cycle where each node is reachable from the others, creating an SCC. Option B contains disconnected nodes. Options C and D combine nodes with no mutual reachability, so they are not valid SCCs.

7. Algorithm Time Complexity

   What is the time complexity of both Kosaraju's and Tarjan's algorithms for finding all SCCs in a directed graph with V vertices and E edges?

   1. O(V+E)
   2. O(V*E)
   3. O(V^2)
   4. O(E^2)

   Explanation: Both Kosaraju's and Tarjan's algorithms operate in linear time relative to the size of the graph, O(V+E). The complexities O(V*E), O(E^2), and O(V^2) represent much slower algorithms, not suitable for SCC finding in practical cases.

8. Visited Marking in Kosaraju’s Algorithm

   In Kosaraju’s algorithm, why is it necessary to reset all nodes to 'unvisited' after the first DFS before starting the second DFS on the reversed graph?

   1. Because the memory would be corrupted otherwise
   2. So that nodes remain in their original order
   3. To ensure that the second DFS explores all SCCs correctly and independently
   4. To speed up the topological sorting phase

   Explanation: Resetting the visited state allows the second DFS to freshly explore each SCC as a separate entity. Memory corruption is unrelated, and topological sorting is not a focus here. Keeping the original order is also not achieved by resetting visited flags.

9. SCCs in Acyclic Graphs

   What can you say about the strongly connected components of a directed acyclic graph (DAG) with five vertices?

   1. All edges must form a cycle
   2. Each vertex forms its own SCC
   3. There is only one SCC containing all vertices
   4. There are no SCCs in a DAG

   Explanation: In a DAG, no cycles exist, so each vertex is only strongly connected to itself, forming single-vertex SCCs. Option B is incorrect since all nodes cannot reach each other. Cycles are absent in DAGs, so option C fails. Option D is incorrect because each vertex still forms an SCC, even if alone.

10. Choosing Between Kosaraju and Tarjan

    Why might someone choose Tarjan’s algorithm over Kosaraju’s algorithm for finding SCCs in large graphs?

    1. Tarjan’s algorithm is only suitable for undirected graphs
    2. Tarjan’s algorithm requires only one pass of DFS, making it more memory and time efficient
    3. Kosaraju’s algorithm fails on graphs with self-loops
    4. Tarjan’s algorithm finds minimum spanning trees

    Explanation: Tarjan achieves the SCC decomposition in a single DFS traversal, minimizing passes and often using less memory. It does not compute minimum spanning trees, and Kosaraju can handle self-loops. Both algorithms are designed for directed graphs, not strictly undirected as mislabeled in option D.