图论算法 (Graph Algorithms)
图论算法 (Graph Algorithms)
图是一种由节点(顶点)和边组成的非线性数据结构,可以表示各种复杂的关系和网络。
基础概念
图的表示
- 邻接表
顶点 -> 邻居列表
0 -> [1, 2]
1 -> [0, 2, 3]
2 -> [0, 1]
3 -> [1]
- 邻接矩阵
0 1 2 3
0 0 1 1 0
1 1 0 1 1
2 1 1 0 0
3 0 1 0 0
图的类型
- 有向图 vs 无向图
无向图: 有向图:
A --- B A --→ B
| | ↑ |
C --- D C ←-- D
- 带权图
A --3-- B
| |
4 5
| |
C --2-- D
- 连通性
连通图: 非连通图:
A --- B A --- B C
| | |
C --- D D
基本算法
1. 深度优先搜索 (DFS)
1
/ \
2 3
/ \ / \
4 5 6 7
访问顺序: 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
2. 广度优先搜索 (BFS)
1
/ \
2 3
/ \ / \
4 5 6 7
访问顺序: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
3. 拓扑排序
依赖关系:
A --> B --> D
| ↑
└--> C -----┘
拓扑序: A -> B -> C -> D
经典问题
1. 岛屿数量
LeetCode 200 - Number of Islands
使用DFS标记连通区域:
输入网格:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
DFS访问过程:
# # 0 0 0 (#表示已访问)
# # 0 0 0
0 0 1 0 0
0 0 0 1 1
发现岛屿数: 3
def numIslands(grid):
if not grid:
return 0
def dfs(i, j):
if (i < 0 or i >= len(grid) or
j < 0 or j >= len(grid[0]) or
grid[i][j] != '1'):
return
grid[i][j] = '#' # 标记已访问
dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
2. 课程表 (拓扑排序)
LeetCode 207 - Course Schedule
检测课程依赖中是否有环:
课程依赖:
0 <- 1 <- 3
↓ ↑
2 ---┘
入度统计:
课程 0: 1
课程 1: 1
课程 2: 1
课程 3: 1
拓扑排序:
3 -> 1 -> 2 -> 0
def canFinish(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
# 建图并统计入度
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
# 将所有入度为0的课程加入队列
from collections import deque
queue = deque([i for i in range(numCourses) if indegree[i] == 0])
count = 0
while queue:
prereq = queue.popleft()
count += 1
for course in graph[prereq]:
indegree[course] -= 1
if indegree[course] == 0:
queue.append(course)
return count == numCourses
3. 网络延迟时间 (Dijkstra算法)
LeetCode 743 - Network Delay Time
使用Dijkstra算法找最短路径:
网络拓扑:
2
1 --→ 2
| ↗ ↓
4 3 --→ 3
1
距离更新过程:
节点1: 0
节点2: 2
节点3: 3
节点4: 4
def networkDelayTime(times, n, k):
from collections import defaultdict
import heapq
# 建图
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
# 距离数组
dist = [float('inf')] * (n + 1)
dist[k] = 0
# 优先队列
pq = [(0, k)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
max_dist = max(dist[1:])
return max_dist if max_dist < float('inf') else -1
4. 冗余连接 (并查集)
LeetCode 684 - Redundant Connection
使用并查集检测环:
输入边:
1 -- 2
| |
4 -- 3
添加边 4-1 时检测到环:
1 -- 2
| |
4 -- 3
def findRedundantConnection(edges):
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
parent[find(x)] = find(y)
n = len(edges)
parent = list(range(n + 1))
for x, y in edges:
if find(x) == find(y):
return [x, y]
union(x, y)
return []
高级算法
1. 最小生成树
- Kruskal算法:按边权重排序,使用并查集
- Prim算法:从点出发,使用优先队列
2. 最短路径
- Dijkstra:单源最短路径(无负权)
- Bellman-Ford:单源最短路径(可负权)
- Floyd-Warshall:多源最短路径
3. 强连通分量
- Kosaraju算法
- Tarjan算法
常见技巧
- DFS解决连通性问题
- BFS解决最短路径问题
- 拓扑排序解决依赖问题
- 并查集处理动态连通性
- 双向BFS优化搜索