【数据结构】（Python）第六章：图

数据结构（Python）第六章：图

---

6.1 图的定义和基本概念

图是由顶点（Vertex）和边（Edge）组成的非线性数据结构，分为无向图和有向图。
基本术语：

• 顶点（Vertex）：图中的基本元素（节点）。
• 边（Edge）：连接两个顶点的线，可带权重。
• 路径：顶点间边的序列。
• 环：起点和终点相同的路径。
• 连通图：任意两顶点间都存在路径。

---

6.2 图的存储结构

6.2.1 邻接矩阵（Adjacency Matrix）

用二维数组存储顶点间的邻接关系，适合稠密图。

class GraphAdjMatrix: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] = weightself.matrix[v][u] = weight  # 若为有向图，注释此行def remove_edge(self, u, v):"""删除边"""self.matrix[u][v] = 0self.matrix[v][u] = 0def has_edge(self, u, v):"""检查是否存在边"""return self.matrix[u][v] != 0def __str__(self):"""打印邻接矩阵"""return "\n".join([" ".join(map(str, row)) for row in self.matrix])

6.2.2 邻接表（Adjacency List）

用链表存储每个顶点的邻接顶点，适合稀疏图。

class GraphNode:def __init__(self, vertex):self.vertex = vertex       # 邻接顶点self.next = None           # 下一邻接节点指针class GraphAdjList:def __init__(self, num_vertices):self.num_vertices = num_verticesself.adj_list = [None] * num_vertices  # 初始化邻接表def add_edge(self, u, v, weight=1):"""添加边（无向图需添加两次）"""# 添加 u -> v 的边new_node = GraphNode(v)new_node.next = self.adj_list[u]self.adj_list[u] = new_node# 添加 v -> u 的边（若为有向图，注释此部分）new_node = GraphNode(u)new_node.next = self.adj_list[v]self.adj_list[v] = new_nodedef remove_edge(self, u, v):"""删除边（需处理双向）"""# 删除 u -> v 的边current = self.adj_list[u]prev = Nonewhile current and current.vertex != v:prev = currentcurrent = current.nextif current:if prev:prev.next = current.nextelse:self.adj_list[u] = current.next# 删除 v -> u 的边（若为有向图，注释此部分）current = self.adj_list[v]prev = Nonewhile current and current.vertex != u:prev = currentcurrent = current.nextif current:if prev:prev.next = current.nextelse:self.adj_list[v] = current.nextdef has_edge(self, u, v):"""检查是否存在边 u->v"""current = self.adj_list[u]while current:if current.vertex == v:return Truecurrent = current.nextreturn Falsedef print_graph(self):"""打印邻接表"""for i in range(self.num_vertices):print(f"顶点 {i}: ", end="")current = self.adj_list[i]while current:print(f"-> {current.vertex}", end="")current = current.nextprint()

---

6.3 图的遍历算法

6.3.1 深度优先搜索（DFS）

递归实现：优先深入访问未探索的路径。

def dfs(graph, start, visited=None):"""深度优先搜索（递归）"""if visited is None:visited = set()  # 记录已访问顶点visited.add(start)print(f"访问顶点: {start}")current = graph.adj_list[start]while current:neighbor = current.vertexif neighbor not in visited:dfs(graph, neighbor, visited)  # 递归访问未探索邻接点current = current.next

6.3.2 广度优先搜索（BFS）

队列实现：按层级逐层访问。

from collections import dequedef bfs(graph, start):"""广度优先搜索（队列）"""visited = set()queue = deque([start])  # 初始化队列visited.add(start)while queue:vertex = queue.popleft()print(f"访问顶点: {vertex}")current = graph.adj_list[vertex]while current:neighbor = current.vertexif neighbor not in visited:visited.add(neighbor)queue.append(neighbor)  # 邻接点入队current = current.next

---

6.4 最小生成树算法

6.4.1 Prim 算法

贪心策略：从顶点出发，逐步扩展最小边。

import heapqdef prim_mst(graph):"""Prim算法求最小生成树（返回边列表）"""num_vertices = graph.num_verticesvisited = [False] * num_verticesmin_heap = []  # 优先队列存储 (权重, u, v)mst_edges = []# 从顶点0开始visited[0] = Truecurrent = graph.adj_list[0]while current:heapq.heappush(min_heap, (1, 0, current.vertex))  # 假设权重为1current = current.nextwhile min_heap and len(mst_edges) < num_vertices - 1:weight, u, v = heapq.heappop(min_heap)if not visited[v]:visited[v] = Truemst_edges.append((u, v, weight))# 将v的邻接边加入堆current = graph.adj_list[v]while current:if not visited[current.vertex]:heapq.heappush(min_heap, (1, v, current.vertex))current = current.nextreturn mst_edges

6.4.2 Kruskal 算法

并查集优化：按权重排序边，避免环。

class UnionFind:"""并查集（支持路径压缩和按秩合并）"""def __init__(self, size):self.parent = list(range(size))self.rank = [0] * sizedef 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_y] = root_xelse:self.parent[root_x] = root_yif self.rank[root_x] == self.rank[root_y]:self.rank[root_y] += 1return Truedef kruskal_mst(graph):"""Kruskal算法求最小生成树"""edges = []# 收集所有边（假设权重为1）for u in range(graph.num_vertices):current = graph.adj_list[u]while current:edges.append((1, u, current.vertex))  # (weight, u, v)current = current.nextedges.sort()  # 按权重排序uf = UnionFind(graph.num_vertices)mst_edges = []for edge in edges:weight, u, v = edgeif uf.union(u, v):mst_edges.append((u, v, weight))return mst_edges

---

6.5 最短路径算法

6.5.1 Dijkstra 算法（无负权边）

import heapqdef dijkstra(graph, start):"""Dijkstra算法求单源最短路径"""num_vertices = graph.num_verticesdistances = [float('inf')] * num_verticesdistances[start] = 0heap = [(0, start)]  # (distance, vertex)while heap:current_dist, u = heapq.heappop(heap)if current_dist > distances[u]:continue  # 已找到更优路径# 遍历邻接顶点current = graph.adj_list[u]while current:v = current.vertexweight = 1  # 假设边权重为1if distances[v] > distances[u] + weight:distances[v] = distances[u] + weightheapq.heappush(heap, (distances[v], v))current = current.nextreturn distances

6.5.2 Floyd-Warshall 算法（多源最短路径）

def floyd_warshall(graph):"""Floyd-Warshall算法求所有顶点对最短路径"""num_vertices = graph.num_verticesdist = [[float('inf')] * num_vertices for _ in range(num_vertices)]# 初始化邻接矩阵for u in range(num_vertices):dist[u][u] = 0current = graph.adj_list[u]while current:v = current.vertexdist[u][v] = 1  # 假设权重为1current = current.next# 动态规划更新最短路径for k in range(num_vertices):for i in range(num_vertices):for j in range(num_vertices):if dist[i][j] > dist[i][k] + dist[k][j]:dist[i][j] = dist[i][k] + dist[k][j]return dist

---

6.6 拓扑排序（针对有向无环图）

def topological_sort(graph):"""拓扑排序（返回顶点顺序）"""num_vertices = graph.num_verticesin_degree = [0] * num_vertices# 计算入度for u in range(num_vertices):current = graph.adj_list[u]while current:v = current.vertexin_degree[v] += 1current = current.next# 初始化队列（入度为0的顶点）queue = deque([u for u in range(num_vertices) if in_degree[u] == 0])result = []while queue:u = queue.popleft()result.append(u)# 更新邻接顶点的入度current = graph.adj_list[u]while current:v = current.vertexin_degree[v] -= 1if in_degree[v] == 0:queue.append(v)current = current.next# 检查是否存在环if len(result) != num_vertices:return None  # 存在环，无法拓扑排序return result

---

6.7 关键路径（AOE网）

def critical_path(graph):"""计算关键路径（返回关键活动列表）"""topo_order = topological_sort(graph)if not topo_order:return None  # 存在环，无法计算num_vertices = graph.num_verticesearliest = [0] * num_vertices# 正向计算最早发生时间for u in topo_order:current = graph.adj_list[u]while current:v = current.vertexweight = 1  # 假设活动时间为1if earliest[v] < earliest[u] + weight:earliest[v] = earliest[u] + weightcurrent = current.next# 反向计算最晚发生时间latest = [earliest[-1]] * num_verticesfor u in reversed(topo_order):current = graph.adj_list[u]while current:v = current.vertexweight = 1if latest[u] > latest[v] - weight:latest[u] = latest[v] - weightcurrent = current.next# 提取关键活动（最早时间 == 最晚时间）critical_edges = []for u in range(num_vertices):current = graph.adj_list[u]while current:v = current.vertexweight = 1if earliest[u] == latest[v] - weight:critical_edges.append((u, v, weight))current = current.nextreturn critical_edges

---

6.8 总结

本章详细实现了图的存储结构（邻接矩阵、邻接表）、遍历算法（DFS、BFS）、最小生成树（Prim、Kruskal）、最短路径（Dijkstra、Floyd-Warshall）、拓扑排序及关键路径，所有代码均添加详细注释。通过合理选择数据结构与算法，可高效解决路径规划、任务调度等实际问题。