## #5. Strongly Connected Component

1. What is connected graph ?

• A graph is `connected` if there is a path between each pair of vertices.
2. What is strongly connected graph ?

• A `directed graph` is `strongly connected` iff there is a path between each pair of vertices.
• Strongly connected的概念只存在于Directed Graph

[Notes]

Strongly connected components in G are the same as they are in reversed G!

### #5.1 Kosaraju’s Algorithm

• Algorithm:
1. Topological sort on reversed G!
2. Run DFS based on the order from step 1

#### #Proof of Kosaraju’s Algorithm:

1. 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而不是两个.
2. 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

• `Low-link value`: low-link value of a node is the smallest node id reachable from that node when doing a dfs, including itself.

2. How to update low-link value to find Strongly Connected Component?

• If there is an edge from v to w in the graph, to update the low-link 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:
1. there is a path from v to w
2. 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)`
3. Algorithms:

1. Maintains a stack, node is added to the stack when they’re visited the first time
2. Nodes are removed from the stack when a complete SCC is found
3. If (v, w) is an edge in the graph, to update lowlink value of v, w must be on the stack.
4. 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