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< | 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. | ||
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. | ||
Revision as of 22:14, 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.
3. Do the second depth-first search pass again, on the original graph G.