Notes - DAA HT23, Strongly connected components
Flashcards
What a strongly connected component of a graph $G$?
A maximal set of vertices $C \subseteq V$ such that for every pair of vertices $u \leadsto v$ and $v \leadsto u$.
Can you give the very high-level pseudocode for the strongly connected components algorithm on a graph $G$?
STRONGLY-CONNECTED-COMPONENTS(G):
call DFS(G) to compute the finish times u.f for each vertex u
create G^T
call DFS(G^T), but in the main loop of DFS consider the vertices in order of decreasing u.f
output the vertices of each tree in the depth-first forest formed in the second DFS as seperate strongly connected components
When running the strongly connected components algorithm on a graph $G$, in what order do you consider the vertices after the initial depth-first search?
In order of decreasing finishing time, i.e. topological order.
When constructing a topological sort of a DAG, what order do you consider vertices in?
Reverse finishing time.