In a directed graph, u and v are strongly connected if there is a path from u to v and a path from v to u.
Being strongly connected is an equivalence relation. Strongly connected components are the equivalence classes of this relation. Thus, the set of verticies can be partitioned into strongly connected components (scc's).
How do we compute strongly connected components?
We begin by augmenting dfs to compute two quantities for each vertex:
Pseudo code for dfs:
d = 0; // counter for assigning dfsno e = 0; // counter for assigning exitno dfs(v) { mark v; d++; set dfsno[v] = d; for each neighbour w of v if w is unmarked dfs(w); e++; exitno[v] = e; }
Now, suppose we construct a new graph in which
This new graph is a dag. Observe that if c1→c2 in the scc dag, the max exit number in c1 is bigger than the max exit number in c2.
Suppose we reverse all the edges in the original graph. All the dfs tree edges are reversed.
Now, in the reversed graph, we start a dfs in an scc containing the highest exit number. This dfs cannot leave the scc—this scc has only outgoing edges in the original graph since it has the highest exit number, so in the reversed graph it has only incoming edges. On the other hand, since this is an scc, whether we follow reversed edges or original edges, all vertices in the scc will be reachable by dfs. In other words, the dfs will mark precisely the vertices of this scc.
Now, we look at unmarked vertex with highest exit number. This is in a different scc. Once again, if we start a dfs here, we cannot leave the scc—the only outgoing (reverse) edge can be to an scc before it in the original dag, but that scc is already visited.
In this way, if we start each time with the unmarked vertex that highest exit number, we identify its scc.
This gives the following algorithm for computing scc's:
Do a normal dfs and compute exit numbers.
For v1,v2,...,vn do if vi is not marked dfs(vi)
Let w1,w2,...,wn be list of vertices ordered by descending order of exit number.
Reverse the edges in G
For w1,w2,...,wn do if wi is not marked dfs(wi)
Video lecture on Applications of BFS and DFS, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)
©IARCS 2012–2016
PÄ›stujeme web | visit: Skluzavky