Find Strongly Connected Components in a Directed Graph: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
=Internal= | =Internal= | ||
* [[ | * [[Graph_Concepts#Directed_Graph_Connectivity|Directed Graph Connectivity]] | ||
* [[Graph_Search#Depth-First_Search_.28DFS.29|Graph Search | Depth-First Search]] | * [[Graph_Search#Depth-First_Search_.28DFS.29|Graph Search | Depth-First Search]] | ||
| Line 10: | Line 10: | ||
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. | 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. | ||
[[ | [[Graph_Concepts#Strongly_Connected_Component|Strongly connected components]] of a directed graph can be computed with two passes of [[Graph_Search#DFS_and_Directed_Connectivity_-_Compute_Strong_Components|depth-first search]]. This is the Kosaraju's Two-Pass Algorithms. | ||
<font color=darkkhaki>TODO</font> | <font color=darkkhaki>TODO</font> | ||
Revision as of 23:41, 1 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 two passes of depth-first search. This is the Kosaraju's Two-Pass Algorithms.
TODO