05-高频算法题精讲-图与拓扑排序
本章概述
图是最复杂也是最强大的数据结构之一，在实际应用中无处不在：社交网络、地图导航、任务调度、依赖分析等。本章将系统讲解图的表示方法、遍历算法、最短路径算法、拓扑排序以及并查集，并通过15+道经典题目深入理解图算法。
本章涵盖：
- 图的表示方法（邻接表、邻接矩阵）
- 图的遍历（DFS、BFS）
- 最短路径算法（Dijkstra、Floyd）
- 拓扑排序及其应用
- 并查集的原理与优化
- 15+道LeetCode高频真题详解
第一节：图的基础知识
1.1 图的基本概念
图的定义： 图G = (V, E)，其中V是顶点集合，E是边集合。
图的分类：
- 有向图 vs 无向图：边是否有方向
- 有权图 vs 无权图：边是否有权重
- 连通图：任意两个顶点之间都有路径
- 有环图 vs 无环图（DAG）：是否存在环
1.2 图的表示方法
方法一：邻接矩阵
class GraphMatrix:
"""使用邻接矩阵表示图"""
def __init__(self, n: int):
self.n = n
self.matrix = [[0] * n for _ in range(n)]
def add_edge(self, u: int, v: int, weight: int = 1):
"""添加边"""
self.matrix[u][v] = weight
def add_undirected_edge(self, u: int, v: int, weight: int = 1):
"""添加无向边"""
self.matrix[u][v] = weight
self.matrix[v][u] = weight
# 优点：查询两个节点之间是否有边的时间复杂度为O(1)
# 缺点：空间复杂度为O(V^2)，不适合稀疏图
方法二：邻接表
from collections import defaultdict
class GraphList:
"""使用邻接表表示图"""
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u: int, v: int, weight: int = 1):
"""添加边"""
self.graph[u].append((v, weight))
def add_undirected_edge(self, u: int, v: int, weight: int = 1):
"""添加无向边"""
self.graph[u].append((v, weight))
self.graph[v].append((u, weight))
# 优点：空间复杂度为O(V+E)，适合稀疏图
# 缺点：查询两个节点之间是否有边需要O(degree)
Go语言实现：
// 邻接表表示
type Graph struct {
vertices int
edges map[int][]Edge
}
type Edge struct {
to int
weight int
}
func NewGraph(n int) *Graph {
return &Graph{
vertices: n,
edges: make(map[int][]Edge),
}
}
func (g *Graph) AddEdge(from, to, weight int) {
g.edges[from] = append(g.edges[from], Edge{to, weight})
}
1.3 图的遍历框架
DFS模板：
def dfs_graph(graph: dict, start: int):
"""图的深度优先遍历"""
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
print(f"访问节点: {node}")
for neighbor, _ in graph[node]:
dfs(neighbor)
dfs(start)
# 时间复杂度: O(V + E)
# 空间复杂度: O(V)
BFS模板：
from collections import deque
def bfs_graph(graph: dict, start: int):
"""图的广度优先遍历"""
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(f"访问节点: {node}")
for neighbor, _ in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 时间复杂度: O(V + E)
# 空间复杂度: O(V)
第二节：图的遍历问题
2.1 LeetCode 200. 岛屿数量（中等）
题目描述： 给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。
解题思路： 使用DFS或BFS遍历每个岛屿，标记访问过的陆地。
def numIslands(grid: list[list[str]]) -> int:
"""
统计岛屿数量
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
count = 0
def dfs(i, j):
"""深度优先遍历，标记连通的陆地"""
if (i < 0 or i >= m or j < 0 or j >= n or
grid[i][j] != '1'):
return
# 标记为已访问
grid[i][j] = '0'
# 遍历四个方向
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return count
# 测试
print(numIslands([
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
])) # 1
# 时间复杂度: O(m × n)
# 空间复杂度: O(m × n)递归栈
BFS实现：
def numIslands(grid: list[list[str]]) -> int:
"""
使用BFS统计岛屿数量
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
count = 0
def bfs(i, j):
queue = deque([(i, j)])
grid[i][j] = '0'
while queue:
x, y = queue.popleft()
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
grid[nx][ny] = '0'
queue.append((nx, ny))
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
bfs(i, j)
return count
# 时间复杂度: O(m × n)
# 空间复杂度: O(min(m, n))队列空间
2.2 LeetCode 695. 岛屿的最大面积（中等）
题目描述： 给定一个包含0和1的二维网格，计算其中最大的岛屿面积。
解题思路： DFS遍历每个岛屿，统计面积。
def maxAreaOfIsland(grid: list[list[int]]) -> int:
"""
计算最大岛屿面积
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
max_area = 0
def dfs(i, j):
"""返回从(i,j)开始的岛屿面积"""
if (i < 0 or i >= m or j < 0 or j >= n or
grid[i][j] != 1):
return 0
grid[i][j] = 0 # 标记为已访问
area = 1
area += dfs(i + 1, j)
area += dfs(i - 1, j)
area += dfs(i, j + 1)
area += dfs(i, j - 1)
return area
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
max_area = max(max_area, dfs(i, j))
return max_area
# 时间复杂度: O(m × n)
# 空间复杂度: O(m × n)
2.3 LeetCode 133. 克隆图（中等）
题目描述： 给定无向连通图中一个节点的引用，返回该图的深拷贝。
解题思路： 使用哈希表记录已克隆的节点，DFS或BFS遍历图。
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node: Node) -> Node:
"""
克隆图
"""
if not node:
return None
# 哈希表：原节点 -> 克隆节点
cloned = {}
def dfs(node):
if node in cloned:
return cloned[node]
# 克隆当前节点
clone = Node(node.val)
cloned[node] = clone
# 克隆邻居节点
for neighbor in node.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
# 时间复杂度: O(V + E)
# 空间复杂度: O(V)
BFS实现：
def cloneGraph(node: Node) -> Node:
"""
使用BFS克隆图
"""
if not node:
return None
cloned = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in cloned:
cloned[neighbor] = Node(neighbor.val)
queue.append(neighbor)
cloned[curr].neighbors.append(cloned[neighbor])
return cloned[node]
# 时间复杂度: O(V + E)
# 空间复杂度: O(V)
2.4 LeetCode 207. 课程表（中等）
题目描述： 现在总共有 numCourses 门课程。有些课程可能有先修课程，例如要学习课程 0 需要先学习课程 1，表示为 [0,1]。给定课程总量以及它们的先修关系，判断是否可能完成所有课程的学习。
解题思路： 检测有向图中是否存在环，使用DFS或拓扑排序。
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
"""
判断是否能完成所有课程（检测有向图是否有环）
"""
# 构建邻接表
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[prereq].append(course)
# 0: 未访问, 1: 正在访问, 2: 已完成
visited = [0] * numCourses
def has_cycle(course):
"""检测从course开始是否有环"""
if visited[course] == 1: # 正在访问，发现环
return True
if visited[course] == 2: # 已完成，无需再检查
return False
visited[course] = 1 # 标记为正在访问
for next_course in graph[course]:
if has_cycle(next_course):
return True
visited[course] = 2 # 标记为已完成
return False
# 检查每门课程
for course in range(numCourses):
if has_cycle(course):
return False
return True
# 测试
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False
# 时间复杂度: O(V + E)
# 空间复杂度: O(V + E)
2.5 LeetCode 210. 课程表 II（中等）
题目描述： 返回完成所有课程所需的学习顺序，如果不可能完成所有课程，返回空数组。
解题思路： 使用拓扑排序（Kahn算法或DFS）。
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
"""
拓扑排序求课程顺序（Kahn算法）
"""
# 构建邻接表和入度数组
graph = defaultdict(list)
indegree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
# 将所有入度为0的节点加入队列
queue = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while queue:
course = queue.popleft()
order.append(course)
# 移除该课程，更新后续课程的入度
for next_course in graph[course]:
indegree[next_course] -= 1
if indegree[next_course] == 0:
queue.append(next_course)
# 如果所有课程都被访问，则返回顺序；否则有环
return order if len(order) == numCourses else []
# 测试
print(findOrder(2, [[1,0]])) # [0, 1]
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]])) # [0,1,2,3] 或 [0,2,1,3]
# 时间复杂度: O(V + E)
# 空间复杂度: O(V + E)
DFS实现拓扑排序：
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
"""
使用DFS进行拓扑排序
"""
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[prereq].append(course)
visited = [0] * numCourses
order = []
def dfs(course):
if visited[course] == 1: # 发现环
return False
if visited[course] == 2: # 已处理
return True
visited[course] = 1
for next_course in graph[course]:
if not dfs(next_course):
return False
visited[course] = 2
order.append(course) # 后序位置添加
return True
for course in range(numCourses):
if not dfs(course):
return []
return order[::-1] # 反转得到拓扑排序
# 时间复杂度: O(V + E)
# 空间复杂度: O(V + E)
第三节：最短路径算法
3.1 单源最短路径：Dijkstra算法
算法原理： 从起点开始，每次选择距离最小的未访问节点，更新其邻居的距离。
import heapq
def dijkstra(graph: dict, start: int, n: int) -> list[int]:
"""
Dijkstra算法求单源最短路径
graph: 邻接表，graph[u] = [(v, weight), ...]
start: 起点
n: 节点总数
返回: 从start到各节点的最短距离
"""
# 初始化距离数组
dist = [float('inf')] * n
dist[start] = 0
# 优先队列：(距离, 节点)
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
# 如果当前距离大于已知最短距离，跳过
if d > dist[u]:
continue
# 更新邻居节点的距离
for v, weight in graph[u]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
# 时间复杂度: O((V + E) log V)
# 空间复杂度: O(V)
3.2 LeetCode 743. 网络延迟时间（中等）
题目描述： 有 n 个网络节点，标记为 1 到 n。给定一个列表 times，表示信号经过有向边的传递时间。计算从给定节点 k 发出一个信号，需要多久才能使所有节点都收到信号。
解题思路： 使用Dijkstra算法求单源最短路径，返回最大距离。
def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
"""
计算网络延迟时间
"""
# 构建邻接表
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
# Dijkstra算法
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]:
new_dist = dist[u] + w
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
# 找最大延迟
max_delay = max(dist[1:])
return max_delay if max_delay != float('inf') else -1
# 测试
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2
# 时间复杂度: O((V + E) log V)
# 空间复杂度: O(V + E)
3.3 LeetCode 787. K站中转内最便宜的航班（中等）
题目描述： 有 n 个城市，通过航班连接。给定出发城市 src，目的地 dst，最多经过 k 站中转，找到从 src 到 dst 的最便宜价格。
解题思路： 使用修改的Dijkstra算法，记录经过的站数。
def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
"""
查找最便宜的航班价格
"""
# 构建邻接表
graph = defaultdict(list)
for u, v, price in flights:
graph[u].append((v, price))
# (价格, 当前城市, 剩余中转次数)
pq = [(0, src, k + 1)]
# 记录到达每个城市的最少剩余次数
visited = {}
while pq:
price, city, stops = heapq.heappop(pq)
if city == dst:
return price
if stops > 0:
for next_city, next_price in graph[city]:
new_price = price + next_price
# 只有在剩余次数更多或者首次访问时才继续
if next_city not in visited or stops - 1 > visited[next_city]:
visited[next_city] = stops - 1
heapq.heappush(pq, (new_price, next_city, stops - 1))
return -1
# 测试
print(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)) # 200
# 时间复杂度: O(E × K log(E × K))
# 空间复杂度: O(V + E)
3.4 多源最短路径：Floyd-Warshall算法
算法原理： 动态规划求任意两点之间的最短路径。
def floyd_warshall(n: int, edges: list[list[int]]) -> list[list[int]]:
"""
Floyd-Warshall算法求所有点对之间的最短路径
n: 节点数量
edges: [u, v, weight]
返回: dist[i][j]表示i到j的最短距离
"""
# 初始化距离矩阵
dist = [[float('inf')] * n for _ in range(n)]
# 自己到自己的距离为0
for i in range(n):
dist[i][i] = 0
# 填入已知边的距离
for u, v, w in edges:
dist[u][v] = w
# Floyd-Warshall核心算法
for k in range(n): # 中间节点
for i in range(n): # 起点
for j in range(n): # 终点
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# 时间复杂度: O(V^3)
# 空间复杂度: O(V^2)
3.5 LeetCode 1334. 阈值距离内邻居最少的城市（中等）
题目描述： 有 n 个城市，给定一个边数组和距离阈值。找到邻居数量最少的城市，如果有多个则返回编号最大的。
解题思路： 使用Floyd-Warshall算法求所有点对最短路径，然后统计每个城市的邻居数。
def findTheCity(n: int, edges: list[list[int]], distanceThreshold: int) -> int:
"""
查找阈值距离内邻居最少的城市
"""
# 初始化距离矩阵
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
dist[v][u] = w
# Floyd-Warshall
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 统计每个城市的邻居数
min_neighbors = float('inf')
result = -1
for i in range(n):
count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
if count <= min_neighbors:
min_neighbors = count
result = i
return result
# 测试
print(findTheCity(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)) # 3
# 时间复杂度: O(V^3)
# 空间复杂度: O(V^2)
第四节：并查集（Union-Find）
4.1 并查集的实现
并查集用于处理不相交集合的合并与查询问题。
class UnionFind:
"""并查集"""
def __init__(self, n: int):
self.parent = list(range(n)) # 父节点数组
self.rank = [0] * n # 秩（树的高度）
self.count = n # 连通分量数量
def find(self, x: int) -> int:
"""查找x的根节点（带路径压缩）"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
"""合并x和y所在的集合（按秩合并）"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
# 按秩合并
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.count -= 1
return True
def connected(self, x: int, y: int) -> bool:
"""判断x和y是否连通"""
return self.find(x) == self.find(y)
# 时间复杂度: O(α(n))，α是反阿克曼函数，几乎为常数
# 空间复杂度: O(n)
Go语言实现：
type UnionFind struct {
parent []int
rank []int
count int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &UnionFind{parent, rank, n}
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) bool {
rootX, rootY := uf.Find(x), uf.Find(y)
if rootX == rootY {
return false
}
if uf.rank[rootX] < uf.rank[rootY] {
uf.parent[rootX] = rootY
} else if uf.rank[rootX] > uf.rank[rootY] {
uf.parent[rootY] = rootX
} else {
uf.parent[rootY] = rootX
uf.rank[rootX]++
}
uf.count--
return true
}
4.2 LeetCode 547. 省份数量（中等）
题目描述： 有 n 个城市，给定一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示城市 i 和城市 j 直接相连。找出省份的数量。
解题思路： 使用并查集，连通的城市合并到同一集合。
def findCircleNum(isConnected: list[list[int]]) -> int:
"""
查找省份数量
"""
n = len(isConnected)
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
uf.union(i, j)
return uf.count
# 测试
print(findCircleNum([[1,1,0],[1,1,0],[0,0,1]])) # 2
# 时间复杂度: O(n^2 × α(n))
# 空间复杂度: O(n)
4.3 LeetCode 684. 冗余连接（中等）
题目描述： 在一个无向图中，有一条附加的边使得图中存在环。找出一条边，移除它之后，图就可以变成一棵树。
解题思路： 使用并查集，遇到的第一条连接已连通节点的边就是冗余边。
def findRedundantConnection(edges: list[list[int]]) -> list[int]:
"""
查找冗余连接
"""
n = len(edges)
uf = UnionFind(n + 1)
for u, v in edges:
if not uf.union(u, v):
return [u, v]
return []
# 测试
print(findRedundantConnection([[1,2],[1,3],[2,3]])) # [2, 3]
# 时间复杂度: O(n × α(n))
# 空间复杂度: O(n)
4.4 LeetCode 721. 账户合并（中等）
题目描述： 给定一个账户列表，每个账户包含姓名和邮箱列表。合并属于同一人的账户。
解题思路： 使用并查集，将相同人的邮箱合并到同一集合。
def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
"""
合并账户
"""
# 邮箱到ID的映射
email_to_id = {}
# 邮箱到姓名的映射
email_to_name = {}
# 为每个邮箱分配ID
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = len(email_to_id)
email_to_name[email] = name
# 初始化并查集
uf = UnionFind(len(email_to_id))
# 合并同一账户下的邮箱
for account in accounts:
first_email_id = email_to_id[account[1]]
for email in account[2:]:
uf.union(first_email_id, email_to_id[email])
# 收集结果
groups = defaultdict(list)
for email, email_id in email_to_id.items():
root = uf.find(email_id)
groups[root].append(email)
result = []
for emails in groups.values():
name = email_to_name[emails[0]]
result.append([name] + sorted(emails))
return result
# 测试
accounts = [
["John","johnsmith@mail.com","john_newyork@mail.com"],
["John","johnsmith@mail.com","john00@mail.com"],
["Mary","mary@mail.com"],
["John","johnnybravo@mail.com"]
]
print(accountsMerge(accounts))
# [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
# ["Mary","mary@mail.com"],
# ["John","johnnybravo@mail.com"]]
# 时间复杂度: O(n × α(n) + n log n)，n是邮箱总数
# 空间复杂度: O(n)
4.5 LeetCode 990. 等式方程的可满足性（中等）
题目描述： 给定一个由表示变量之间关系的字符串方程组成的数组，判断方程组是否可满足。
解题思路： 先处理所有相等关系（union），再检查不等关系是否冲突。
def equationsPossible(equations: list[str]) -> bool:
"""
判断等式方程是否可满足
"""
uf = UnionFind(26) # 26个字母
# 处理所有相等关系
for eq in equations:
if eq[1] == '=':
x = ord(eq[0]) - ord('a')
y = ord(eq[3]) - ord('a')
uf.union(x, y)
# 检查所有不等关系
for eq in equations:
if eq[1] == '!':
x = ord(eq[0]) - ord('a')
y = ord(eq[3]) - ord('a')
if uf.connected(x, y):
return False
return True
# 测试
print(equationsPossible(["a==b","b!=a"])) # False
print(equationsPossible(["a==b","b==c","a==c"])) # True
# 时间复杂度: O(n × α(26)) = O(n)
# 空间复杂度: O(26) = O(1)
第五节：最小生成树
5.1 Kruskal算法
算法原理： 将所有边按权重排序，使用并查集逐个加入不形成环的边。
def kruskal(n: int, edges: list[list[int]]) -> tuple[int, list[list[int]]]:
"""
Kruskal算法求最小生成树
n: 节点数
edges: [u, v, weight]
返回: (最小权重和, 选中的边)
"""
# 按权重排序
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
mst_edges = []
total_weight = 0
for u, v, weight in edges:
if uf.union(u, v):
mst_edges.append([u, v, weight])
total_weight += weight
# 已选n-1条边，构成树
if len(mst_edges) == n - 1:
break
return total_weight, mst_edges
# 时间复杂度: O(E log E)
# 空间复杂度: O(V)
5.2 LeetCode 1584. 连接所有点的最小费用（中等）
题目描述： 给定一些点的坐标，连接所有点需要的最小费用。两点之间的费用是它们的曼哈顿距离。
解题思路： 构建完全图，使用Kruskal算法求最小生成树。
def minCostConnectPoints(points: list[list[int]]) -> int:
"""
连接所有点的最小费用
"""
n = len(points)
# 计算所有边
edges = []
for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((dist, i, j))
# 按距离排序
edges.sort()
uf = UnionFind(n)
total_cost = 0
edges_used = 0
for dist, u, v in edges:
if uf.union(u, v):
total_cost += dist
edges_used += 1
if edges_used == n - 1:
break
return total_cost
# 测试
print(minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]])) # 20
# 时间复杂度: O(n^2 log n)
# 空间复杂度: O(n^2)
第六节：其他图算法问题
6.1 LeetCode 127. 单词接龙（困难）
题目描述： 给定两个单词 beginWord 和 endWord，以及一个字典 wordList。找到从 beginWord 到 endWord 的最短转换序列的长度。
解题思路： 使用BFS，每次转换一个字母。
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
"""
单词接龙
"""
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
# 尝试改变每个位置的字母
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word == endWord:
return steps + 1
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, steps + 1))
return 0
# 测试
print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"])) # 5
# 时间复杂度: O(n × 26 × L)，n是单词数，L是单词长度
# 空间复杂度: O(n × L)
双向BFS优化：
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
"""
双向BFS优化
"""
word_set = set(wordList)
if endWord not in word_set:
return 0
# 从两端同时搜索
begin_set = {beginWord}
end_set = {endWord}
visited = set()
steps = 1
while begin_set and end_set:
# 优化：总是从较小的集合开始扩展
if len(begin_set) > len(end_set):
begin_set, end_set = end_set, begin_set
next_set = set()
for word in begin_set:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in end_set:
return steps + 1
if next_word in word_set and next_word not in visited:
visited.add(next_word)
next_set.add(next_word)
begin_set = next_set
steps += 1
return 0
# 时间复杂度: O(n × 26 × L)，但实际更快
# 空间复杂度: O(n × L)
6.2 LeetCode 1091. 二进制矩阵中的最短路径（中等）
题目描述： 给定一个 n x n 的二进制矩阵 grid，返回矩阵中最短畅通路径的长度。
解题思路： 使用BFS，可以往8个方向移动。
def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
"""
二进制矩阵中的最短路径
"""
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
# 8个方向
directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
queue = deque([(0, 0, 1)]) # (x, y, 距离)
grid[0][0] = 1 # 标记为已访问
while queue:
x, y, dist = queue.popleft()
if x == n - 1 and y == n - 1:
return dist
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
grid[nx][ny] = 1 # 标记为已访问
queue.append((nx, ny, dist + 1))
return -1
# 时间复杂度: O(n^2)
# 空间复杂度: O(n^2)
本章总结
本章系统讲解了图算法的核心知识：
图的表示：
- 邻接矩阵：适合稠密图，查询快，空间O(V²)
- 邻接表：适合稀疏图，节省空间，空间O(V+E)
图的遍历：
- DFS：使用栈（递归），适合检测环、拓扑排序
- BFS：使用队列，适合最短路径、层次遍历
最短路径算法：
| 算法 | 适用场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| Dijkstra | 单源、非负权 | O((V+E)logV) | O(V) |
| Bellman-Ford | 单源、有负权 | O(VE) | O(V) |
| Floyd-Warshall | 多源 | O(V³) | O(V²) |
| BFS | 无权图 | O(V+E) | O(V) |
拓扑排序：
- Kahn算法：基于BFS，使用入度数组
- DFS：后序遍历结果反转
并查集应用：
- 连通性问题（岛屿、省份）
- 最小生成树（Kruskal）
- 动态连通性
- 等价关系判断
优化技巧：
- 路径压缩：find操作时压缩路径
- 按秩合并：union时将小树接到大树下
- 双向BFS：从两端同时搜索，减少搜索空间
- 优先队列：Dijkstra中快速获取最小距离
常见题型：
- 岛屿问题（DFS/BFS遍历）
- 课程表问题（拓扑排序、环检测）
- 最短路径（Dijkstra、BFS）
- 连通性（并查集）
- 最小生成树（Kruskal、Prim）
下一章讲解动态规划算法，包括背包问题、最长子序列、股票问题和状态机DP。