Graph  5. Strongly Connected Component
#5. Strongly Connected Component
What is connected graph ?
 A graph is
connected
if there is a path between each pair of vertices.
 A graph is
What is strongly connected graph ?
 A
directed graph
isstrongly connected
iff there is a path between each pair of vertices.  Strongly connected的概念只存在于Directed Graph
 A
[Notes]
Strongly connected components in G are the same as they are in reversed G!
#5.1 Kosaraju’s Algorithm
 Algorithm:
 Topological sort on reversed G!
 Run DFS based on the order from step 1
#Proof of Kosaraju’s Algorithm:
What is
Kernel DAG
? Kernel DAG是将一个graph里的每个strongly connected component变成一个vertex, 然后把所有这些SCCs给连起来. 得到的结果一定是一个DAG. 比如Tushar视频里的这个图:
 Reference: Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm from Tushar Roy
 4个SCCs连起来的一定是一个DAG. 假设有一条边从(DEF)到(ABC)，那么很容易证明(ABCDEF)是一个SCC而不是两个.
Why Kernal DAG ?
Kernel DAG解释了为什么我们要先把G到倒过来求topological order.
 用上图的例子来看, 这个order保证了在第二遍找SCCs的DFS的时候我们会从(DEF)中任何一个结点或者(K)来开始DFS, 假设从(DEF)中任何一个结点开始, 根据上面的图很显然我们没有办法走到ABC或者GHIJ. 假设从K开始也很显然没有办法走到GHIJ.
 这样就能找到(DEF)和(K)两个strongly connected component. 接下来无论从(ABC)还是(GHIJ)中任意一个结点开始都能顺利找到自己的strongly connected component. 这样就证明了这个算法的可行性.
Java Kosaraju’a Algorithm


Python Kosaraju’s Algorithm


#5.2 Tarjan’s Algorithm
What is lowlink value?
Lowlink value
: lowlink value of a node is the smallest node id reachable from that node when doing a dfs, including itself.
How to update lowlink value to find Strongly Connected Component?
 If there is an edge from v to w in the graph, to update the lowlink value of v by
lowlink[v] = min(lowlink[v], lowlink[w])
, the following 2 conditions must be met in order to find the strongly connected component: there is a path from v to w
 w must be on the stack
 If a node v is the starting point of a strongly connected component, then it’s
id(v) == lowlink(v)
 If there is an edge from v to w in the graph, to update the lowlink value of v by
Algorithms:
 Maintains a stack, node is added to the stack when they’re visited the first time
 Nodes are removed from the stack when a complete SCC is found
 If (v, w) is an edge in the graph, to update lowlink value of v, w must be on the stack.
 If a node is the starting point the a SCC, it’s value (or id) must be equal to it’s lowlink value
Python Tarjan’s Algorithm

