Find Strongly Connected Components in a Directed Graph: Difference between revisions
| Line 17: | Line 17: | ||
1. Reverse all of the arcs of the given graph. Let G<sup>rev</sup> = G with all arcs revered. | 1. Reverse all of the arcs of the given graph. Let G<sup>rev</sup> = G with all arcs revered. | ||
2. Do the first [[Graph_Search#DFS_Recursive_Algorithm_Pseudocode|depth-first search]] pass on the reversed graph G<sup>rev</sup>. The practical implementation should run DFS on the original graph G but going in the opposite direction of the arcs, backwards. | 2. Do the first [[Graph_Search#DFS_Recursive_Algorithm_Pseudocode|depth-first search]] pass on the reversed graph G<sup>rev</sup>. The practical implementation should run DFS on the original graph G but going in the opposite direction of the arcs, backwards. This pass computes an ordering of nodes that allows the second pass, while starting in the given order, to discover the strongly connected components. | ||
3. Do the second [[Graph_Search#DFS_Recursive_Algorithm_Pseudocode|depth-first search]] pass again, on the original graph G. | 3. Do the second [[Graph_Search#DFS_Recursive_Algorithm_Pseudocode|depth-first search]] pass again, on the original graph G. In this pass we use the order computed by the first pass and we discover the strongly connected components one by one. | ||
Revision as of 22:16, 4 October 2021
External
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rng2S/computing-strong-components-the-algorithm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/QFOFt/computing-strong-components-the-analysis
Internal
Overview
Finding strongly connected components in a directed graph is a form of clustering heuristics: strongly connected components represent clusters where the objects represented by the vertices are clustered in some way.
Strongly connected components of a directed graph can be computed with Kosaraju's Two-Pass algorithm, which consists of two passes of depth-first search.
Kosaraju's Two-Pass Algorithm
The algorithm has three steps:
1. Reverse all of the arcs of the given graph. Let Grev = G with all arcs revered.
2. Do the first depth-first search pass on the reversed graph Grev. The practical implementation should run DFS on the original graph G but going in the opposite direction of the arcs, backwards. This pass computes an ordering of nodes that allows the second pass, while starting in the given order, to discover the strongly connected components.
3. Do the second depth-first search pass again, on the original graph G. In this pass we use the order computed by the first pass and we discover the strongly connected components one by one.