Strongly Connected Components Kosaraju Algorithm Flashcards
Front
Back
What is a Strongly Connected Component (SCC)?
A subset of vertices in a directed graph where every vertex is reachable from every other vertex in the subset.
What is a Maximal Strongly Connected Component (MSCC)?
An SCC that is not part of a larger SCC; it cannot be extended without losing strong connectivity.
What is the transpose of a graph (Gᵗ)?
A graph obtained by reversing the direction of every edge in the original graph.
What are discovery and finish times in DFS?
Discovery time is when a node is first visited; finish time is when all its descendants are fully explored.
What does the first DFS in Kosaraju’s algorithm do?
It computes discovery and finish times and orders nodes by descending finish time.
Why is finish time important in Kosaraju’s algorithm?
It helps sort nodes so that the DFS on the transposed graph discovers SCCs correctly.
What does the second DFS in Kosaraju’s algorithm do?
It performs DFS on the transposed graph in order of descending finish times to find each SCC.
What is the Super Graph in SCC context?
A graph where each node represents an SCC and the edges show inter-SCC connections.
Why does Kosaraju’s algorithm work?
Because the descending finish time order in DFS simulates a topological sort of the super graph.
What is the time complexity of Kosaraju’s algorithm?
O(V + E), where V is the number of vertices and E is the number of edges.
How do you reverse a graph in adjacency list form?
For every edge u → v, add v → u in the reversed graph.
What happens if you do DFS on the transposed graph in arbitrary order?
You may not isolate SCCs correctly; order must be descending by finish times from the first DFS.
How does Kosaraju’s algorithm isolate SCCs?
By performing DFS from unvisited nodes in descending order of original finish times on the transposed graph.
