图
图（Graph）是一种复杂的非线性数据结构，由节点（顶点）和边组成。图广泛应用于社交网络、路由算法、依赖关系等领域。掌握图的算法对于解决许多实际问题至关重要。
图的基础
图的定义
图 G = (V, E) 由顶点集合 V 和边集合 E 组成。
图的类型
1. 有向图 vs 无向图
- 有向图：边有方向，从 u 到 v
- 无向图：边无方向，u 和 v 相互连接
2. 加权图 vs 无权图
- 加权图：边有权重（距离、成本等）
- 无权图：边没有权重
3. 连通图 vs 非连通图
- 连通图：任意两个顶点之间都有路径
- 非连通图：存在不连通的顶点
图的表示方法
1. 邻接矩阵（Adjacency Matrix）
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
self.matrix[u][v] = weight
# 如果是无向图，还需要：
# self.matrix[v][u] = weight
def has_edge(self, u, v):
return self.matrix[u][v] != 0
优点：
- 查找边的时间复杂度 O(1)
- 适合稠密图
缺点：
- 空间复杂度 O(V²)
- 不适合稀疏图
2. 邻接表（Adjacency List）
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v, weight=1):
self.graph[u].append((v, weight))
# 如果是无向图，还需要：
# self.graph[v].append((u, weight))
def get_neighbors(self, u):
return self.graph[u]
优点：
- 空间复杂度 O(V + E)
- 适合稀疏图
- 遍历邻接节点高效
缺点：
- 查找边的时间复杂度 O(degree)
图的遍历
1. 深度优先搜索（DFS）
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor, _ in graph.get_neighbors(start):
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 迭代实现
def dfs_iterative(graph, start):
stack = [start]
visited = set()
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
for neighbor, _ in graph.get_neighbors(node):
if neighbor not in visited:
stack.append(neighbor)
2. 广度优先搜索（BFS）
from collections import deque
def bfs(graph, start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
print(node)
for neighbor, _ in graph.get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
最短路径算法
1. Dijkstra 算法（单源最短路径，非负权重）
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph.graph}
distances[start] = 0
pq = [(0, start)]
visited = set()
while pq:
dist, node = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph.get_neighbors(node):
if neighbor not in visited:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances
2. Bellman-Ford 算法（单源最短路径，可处理负权重）
def bellman_ford(graph, start, num_vertices):
distances = {i: float('inf') for i in range(num_vertices)}
distances[start] = 0
# 松弛操作
for _ in range(num_vertices - 1):
for u in graph.graph:
for v, weight in graph.get_neighbors(u):
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# 检测负权环
for u in graph.graph:
for v, weight in graph.get_neighbors(u):
if distances[u] + weight < distances[v]:
return None # 存在负权环
return distances
3. Floyd-Warshall 算法（全源最短路径）
def floyd_warshall(graph, num_vertices):
dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]
# 初始化
for i in range(num_vertices):
dist[i][i] = 0
for u in graph.graph:
for v, weight in graph.get_neighbors(u):
dist[u][v] = weight
# 动态规划
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
拓扑排序
拓扑排序用于有向无环图（DAG），常用于任务调度、依赖关系等。
def topological_sort(graph, num_vertices):
in_degree = [0] * num_vertices
# 计算入度
for u in graph.graph:
for v, _ in graph.get_neighbors(u):
in_degree[v] += 1
# 找到所有入度为 0 的节点
queue = deque([i for i in range(num_vertices) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor, _ in graph.get_neighbors(node):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != num_vertices:
return None # 存在环
return result
最小生成树
1. Kruskal 算法
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, 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
return True
def kruskal(edges, num_vertices):
edges.sort(key=lambda x: x[2]) # 按权重排序
uf = UnionFind(num_vertices)
mst = []
for u, v, weight in edges:
if uf.union(u, v):
mst.append((u, v, weight))
if len(mst) == num_vertices - 1:
break
return mst
2. Prim 算法
import heapq
def prim(graph, start, num_vertices):
mst = []
visited = {start}
pq = []
for neighbor, weight in graph.get_neighbors(start):
heapq.heappush(pq, (weight, start, neighbor))
while pq and len(visited) < num_vertices:
weight, u, v = heapq.heappop(pq)
if v in visited:
continue
visited.add(v)
mst.append((u, v, weight))
for neighbor, w in graph.get_neighbors(v):
if neighbor not in visited:
heapq.heappush(pq, (w, v, neighbor))
return mst
常见题目
1. 课程表（拓扑排序）
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == num_courses
2. 岛屿数量（DFS/BFS）
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
总结
图是算法面试中的高级数据结构：
- 表示方法：邻接矩阵、邻接表
- 遍历算法：DFS、BFS
- 最短路径：Dijkstra、Bellman-Ford、Floyd-Warshall
- 拓扑排序：用于 DAG 的排序
- 最小生成树：Kruskal、Prim
掌握图的算法能够帮助你解决许多复杂的实际问题。
数据结构部分的学习就到这里了！接下来，让我们进入算法部分，学习各种高效的算法技巧。