Graph – Strongly Connected Component
What is Strongly Connected Component?
A Graph is Strongly Connected Component if there is a PATH (not edge) between every pair of nodes.
[Undirected Graph]
For undirected graph, start at any vertex and do a DFS traversal, if every other vertices are reachable, then the graph is strongly connected.
[Directed Graph]
For directed graph, things become a little bit complicated. Because whether all other vertices are reachable is determined by the starting point.
For example, in the following example, which is not a strongly connected component. If we start from vertex 2, then every other vertices are reachable through one DFS traversal, but if we start at 4, we can not reach all other vertices.
[Algorithm] – Directed Graph
So a single DFS is not enough to check whether a Directed Graph is strongly connected.
Pseudo-Code
1. DFS from v, if any vertex is not reachable, return false
2. Reversed all arcs in the graph
3. DFS from the same v, if any vertex is not reachable, return false
Read full article from Graph – Strongly Connected Component
No comments:
Post a Comment