有向图的强联通分量-SCC-Tarjan算法

**有向图的强联通分量-SCC-Tarjan算法**

在计算机科学中，强联通分量（Strongly Connected Component, SCC）是指一个有向图中的一组顶点，它们之间存在一条从任意两个顶点到达任意其他顶点的路径。Tarjan算法是一种常用的用于求解SCC的问题的算法。

**Tarjan算法原理**

Tarjan算法基于以下几个关键观察：

1.一个有向图中，如果两个顶点之间存在一条从第一个顶点到达第二个顶点的路径，则一定存在一条从第二个顶点到达第一个顶点的路径。
2.一个有向图中，如果两个顶点都可以到达某个第三个顶点，则这两个顶点一定是强联通分量的一部分。

**Tarjan算法步骤**

1. 初始化一个栈，用于存储当前正在访问的顶点。
2. 遍历有向图中的每个顶点，并对其进行深度优先搜索（DFS）。
3. 在DFS过程中，对于每个访问到的顶点，将其压入栈中。
4. 当访问到一个顶点时，如果它已经被访问过，则直接跳过，不再进行DFS操作。
5. 当访问到一个顶点时，如果它没有被访问过，则对其进行DFS操作，并将其压入栈中。
6. 在DFS过程中，当访问到一个顶点时，如果它的下标小于当前栈顶元素的下标，则说明这个顶点是强联通分量的一部分，将其加入到当前SCC中。
7. 当访问到一个顶点时，如果它的下标大于或等于当前栈顶元素的下标，则说明这个顶点不是强联通分量的一部分，直接跳过，不再进行DFS操作。

**Tarjan算法示例代码**

from collections import defaultdictclass Graph:
 def __init__(self, vertices):
 self.graph = defaultdict(list)
 self.V = vertices def add_edge(self, u, v):
 self.graph[u].append(v)

 def DFSUtil(self, v, visited, stack):
 visited[v] = True for i in self.graph[v]:
 if not visited[i]:
 self.DFSUtil(i, visited, stack)
 stack.append(v)

 def fill_order(self, v, visited, stack):
 visited[v] = True for i in self.graph[v]:
 if not visited[i]:
 self.fill_order(i, visited, stack)
 stack.append(v)

 def SCCUtil(self, v, visited, stack, scc_count):
 visited[v] = True scc[scc_count].append(v)
 for i in self.graph[v]:
 if not visited[i]:
 self.SCCUtil(i, visited, stack, scc_count)

 def fill_stack(self, v, visited, stack):
 visited[v] = True for i in self.graph[v]:
 if not visited[i]:
 self.fill_stack(i, visited, stack)
 stack.append(v)

 def SCC(self):
 global scc scc = []
 visited = [False]*self.V stack = []

 for i in range(self.V):
 if not visited[i]:
 self.fill_order(i, visited, stack)

 visited = [False]*self.V scc_count =0 while stack:
 v = stack.pop()
 if not visited[v]:
 scc.append([])
 self.SCCUtil(v, visited, stack, scc_count)
 scc_count +=1 return scc# Test the codeg = Graph(5)
g.add_edge(1,0)
g.add_edge(0,2)
g.add_edge(2,1)
g.add_edge(0,3)
g.add_edge(3,4)

scc = g.SCC()
print("Strongly Connected Components:")
for i in range(len(scc)):
 print(f"SCC {i+1}: {scc[i]}")