Find Strongly Connected Components in a Directed Graph: Difference between revisions
Jump to navigation
Jump to search
m (Ovidiu moved page Find Strongly Connected Components in an Directed Graph to Find Strongly Connected Components in a Directed Graph without leaving a redirect) |
No edit summary |
||
| Line 1: | Line 1: | ||
=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= | =Internal= | ||
* [[ | * [[Graph#Directed_Graph_Connectivity|Directed Graph Connectivity]] | ||
* [[Graph_Search#Depth-First_Search_.28DFS.29|Graph Search | Depth-First Search]] | |||
=Overview= | =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. | 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#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> | |||
Revision as of 23:22, 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