Deciphering connected components in a directed graph is a bit more difficult than it is in undirected graphs. A strongly connected component is a subsection of a directed graph in which there is a directed path from every vertex to every other vertex. The rather convoluted graph below demonstrates the concept.
If each strongly connected component is treated as a single node, the graph becomes a directed acyclic graph. Just like nodes in a directed graph, a strongly connected components with no incoming edges is known as a source and one without any outgoing edges is known as a sink.
Finding the strongly connected components of a directed graph is the most complex of the algorithms shown here. This algorithm (often referred to as the Kosaraju or Kosaraju-Sharir algorithm) performs DFS twice. The first time it derives an ordering in which to process the vertices that guarantees the second pass of DFS will start with a sink component. In other words, the goal is to identify the reverse topological ordering of all strongly connected components. The second discovers the strongly connected components.
Applications
- Collapse a complicated graph into a more manageable graph.
Asymptotic Complexity
\(O(m + n)\)
Pseudo Code
strong-connected-components:
G = input graph
S = stack to hold ordering
magic-ordering(G, S)
set all vertices to NOT conquered
while S is not empty:
v = S->pop
if v is NOT conquered:
scc-dfs(G, v)
scc-dfs:
G = input graph
v = starting vertex
scc_id = strongly connected component id to mark all vertices with
side effects: marks all reachable vertices with a strongly connected
component id
s = new stack data structure
s->push(v)
while s is not empty:
v = s->pop
if v is NOT conquered:
conquer(v)
v->scc_id = scc_id
for each edge in v:
w = edge->head
s->push(w)
// equivalent to a topological sort with the direction of the edges reversed
magic-ordering:
G = input graph
S = stack to hold ordering
for every vertex in G:
if vertex is NOT conquered:
reverse-topo-sort(G, S, vertex)
reverse-topo-sort:
G = input graph
S = stack to hold ordering
v = starting vertex
side effect: places vertices on the stack in the "magic order"
conquer(v)
for each incoming edge in V:
w = edge->tail
if w is NOT conquered:
reverse-topo-sort(G, S, w)
S->push(v)
Source Code
Relevant Files:
Click here for build and run instructions