目录
1. 深度优先遍历（DFS）
1.1 DFS 的基本原理
深度优先搜索（DFS, Depth-First Search）是一种遍历或搜索图的算法，它采用 回溯 的思想，从起始节点开始沿着一条路径尽可能深入，直到无法继续时再回溯并尝试其他路径。
DFS 的特点：
- 时间复杂度：O(V+E)O(V + E)（邻接表），O(V2)O(V^2)（邻接矩阵）
- 空间复杂度：O(V)O(V)（递归深度或显式栈）
- 适用场景：
- 连通性检查（判断两个点是否连通）
- 连通分量计算
- 拓扑排序（DAG）
- 二分图检测
- 强连通分量（SCC）计算
1.2 DFS 的递归实现
无向图 DFS 递归版（Python）
class Graph:
def __init__(self, V):
self.V = V
self.adj = [[] for _ in range(V)]
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u) # 无向图
def dfs_recursive(self, v, visited):
visited[v] = True
print(v, end=" ")
for neighbor in self.adj[v]:
if not visited[neighbor]:
self.dfs_recursive(neighbor, visited)
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(3, 4)
visited = [False] * g.V
g.dfs_recursive(0, visited)
输出：
0 1 3 4 2
复杂度：
- 时间复杂度：O(V+E)O(V + E)
- 空间复杂度：O(V)O(V)（递归栈深度）
1.3 DFS 的非递归实现（显式栈）
递归 DFS 存在 栈溢出 风险，因此可以使用 显式栈 来实现非递归版本。
无向图 DFS 非递归版（Python）
def dfs_iterative(graph, start):
visited = [False] * len(graph)
stack = [start]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
print(v, end=" ")
stack.extend(reversed(graph[v])) # 逆序保证遍历顺序
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(3, 4)
dfs_iterative(g.adj, 0)
输出：
0 2 1 3 4
复杂度：
- 时间复杂度：O(V+E)O(V + E)
- 空间复杂度：O(V)O(V)（显式栈）
2. 连通分量
2.1 无向图的连通分量
定义：无向图的连通分量（Connected Component）指的是 顶点之间互相连通，且与其他部分不连通的极大子图。
计算连通分量（Python）
def count_components(graph, V):
visited = [False] * V
components = 0
def dfs(v):
visited[v] = True
for neighbor in graph[v]:
if not visited[neighbor]:
dfs(neighbor)
for v in range(V):
if not visited[v]: # 发现新连通分量
components += 1
dfs(v)
return components
g = Graph(6)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(3, 4)
print("连通分量个数:", count_components(g.adj, g.V))
输出：
连通分量个数: 3
复杂度：
- 时间复杂度：O(V+E)O(V + E)
2.2 有向图的强连通分量（SCC）
在 有向图 中，强连通分量（SCC, Strongly Connected Component）是指 任意两个顶点都可以互相到达的最大子图。
计算 SCC 常用 Kosaraju 算法 或 Tarjan 算法：
- Kosaraju：两次 DFS，复杂度 O(V+E)O(V + E)
- Tarjan：基于 Tarjan 的低链值，复杂度 O(V+E)O(V + E)
Kosaraju 算法计算 SCC（Python）
from collections import defaultdict
class Graph:
def __init__(self, V):
self.V = V
self.adj = defaultdict(list)
def add_edge(self, u, v):
self.adj[u].append(v)
def dfs(self, v, visited, stack):
visited[v] = True
for neighbor in self.adj[v]:
if not visited[neighbor]:
self.dfs(neighbor, visited, stack)
stack.append(v)
def transpose(self):
g = Graph(self.V)
for v in self.adj:
for neighbor in self.adj[v]:
g.add_edge(neighbor, v)
return g
def find_scc(self):
stack = []
visited = [False] * self.V
for v in range(self.V):
if not visited[v]:
self.dfs(v, visited, stack)
transposed = self.transpose()
visited = [False] * self.V
while stack:
v = stack.pop()
if not visited[v]:
transposed.dfs(v, visited, [])
print() # 输出 SCC
g = Graph(5)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(1, 0)
g.add_edge(1, 3)
g.add_edge(3, 4)
print("强连通分量:")
g.find_scc()
复杂度：
- 时间复杂度：O(V+E)O(V + E)
发表回复