# 用Python实现图论算法：邻接表和邻接矩阵的5个经典应用案例 如果你已经掌握了Python的基础语法，并且对数据结构有初步了解，那么图论可能是你下一个想要征服的领域。图论不仅仅是计算机科学中的抽象概念，它更是社交网络分析、路径规划、推荐系统乃至芯片设计的基石。然而，很多开发者在初次接触图论算法时，常常会卡在第一步：**如何高效地表示一个图？** 是选择直观但可能笨重的邻接矩阵，还是灵活但查询稍慢的邻接表？这个选择，往往直接决定了后续算法实现的效率和代码的优雅程度。 在实际项目中，我见过不少团队因为数据结构选型不当，导致算法在测试数据上运行良好，一上真实场景就性能“雪崩”。比如，用一个 `n x n` 的矩阵去存储一个数千万用户但平均好友只有几百的社交网络，内存瞬间就会被榨干。反过来，在一个几乎完全连接的电路板布线图中使用邻接表，又会因为遍历链表产生大量缓存未命中，拖慢计算速度。 本文将带你跳出单纯的概念对比，通过五个**紧密结合实际场景的Python案例**，深入剖析邻接表和邻接矩阵的应用。我们会从零开始，用原生Python实现这两种结构，并引入强大的`NetworkX`库作为对照和补充。更重要的是，我会分享如何根据**图密度**这一关键指标，在两者间做出明智的选择，并提供可复现的性能测试数据。无论你是要优化现有的图算法，还是为新的应用场景设计底层数据结构，这里都有你需要的实战经验。 ## 1. 基础构建：从零实现两种数据结构 在深入算法之前，我们必须拥有可靠的工具。用Python实现邻接矩阵和邻接表，远不止是学会使用列表的列表。我们需要考虑无权图与带权图、有向与无向、以及空间效率。 ### 1.1 邻接矩阵的Python实现 邻接矩阵的核心思想是用一个二维数组（在Python中常用列表的列表或NumPy数组）来记录顶点间的连接关系。对于n个顶点的图，矩阵大小为n×n。 ```python class AdjacencyMatrix: def __init__(self, num_vertices, directed=False, weighted=False): """ 初始化邻接矩阵。 :param num_vertices: 顶点数量 :param directed: 是否为有向图 :param weighted: 是否为带权图 """ self.n = num_vertices self.directed = directed self.weighted = weighted # 对于无权图，用0表示无边，1表示有边 # 对于带权图，用None或一个很大的数（如float('inf')）表示无边，具体数值表示权重 self.no_edge = 0 if not weighted else float('inf') self.matrix = [[self.no_edge] * num_vertices for _ in range(num_vertices)] # 如果是无向图，确保矩阵对称（在add_edge中处理） def add_edge(self, u, v, weight=1): """添加一条从u到v的边。""" if not 0 <= u < self.n or not 0 <= v < self.n: raise IndexError("顶点索引超出范围") self.matrix[u][v] = weight if not self.directed: self.matrix[v][u] = weight def has_edge(self, u, v): """判断是否存在从u到v的边。""" return self.matrix[u][v] != self.no_edge def get_weight(self, u, v): """获取边(u, v)的权重，无边则返回no_edge。""" return self.matrix[u][v] def neighbors(self, u): """返回顶点u的所有邻居顶点列表（对于带权图，只返回顶点索引）。""" if self.weighted: return [v for v in range(self.n) if self.matrix[u][v] != self.no_edge] else: return [v for v in range(self.n) if self.matrix[u][v] == 1] def __str__(self): return '\n'.join([' '.join([str(cell) for cell in row]) for row in self.matrix]) ``` > 注意：上述实现中，对于带权图，我们用 `float('inf')` 表示无边。这在最短路径算法中非常方便，因为任何实数权重加上无穷大仍然是无穷大。但在某些需要区分“零权重”和“无边”的场景下，可能需要改用 `None`。 这个实现简单直观，但存在一个明显问题：**空间浪费**。即使对于稀疏图（边数远小于顶点数的平方），我们也分配了 `n * n` 的空间。当n很大时（例如10万个顶点），即使每条边只占8字节（float），矩阵也将消耗近80GB内存，这显然是不可接受的。 ### 1.2 邻接表的Python实现 邻接表为每个顶点维护一个列表，只存储该顶点实际连接的邻居。这正好解决了稀疏图的空间问题。 ```python from collections import defaultdict class AdjacencyList: def __init__(self, num_vertices=None, directed=False, weighted=False): """ 初始化邻接表。 :param num_vertices: 可选的顶点数量（用于预分配，但Python中非必需） :param directed: 是否为有向图 :param weighted: 是否为带权图 """ self.directed = directed self.weighted = weighted # 使用defaultdict(list)可以动态添加顶点 # 对于带权图，列表中的元素是 (邻居, 权重) 元组 self.graph = defaultdict(list) self.vertices = set() def add_vertex(self, v): """添加一个顶点。""" self.vertices.add(v) if v not in self.graph: self.graph[v] = [] def add_edge(self, u, v, weight=1): """添加一条边。""" self.add_vertex(u) self.add_vertex(v) if self.weighted: self.graph[u].append((v, weight)) if not self.directed: self.graph[v].append((u, weight)) else: self.graph[u].append(v) # 对于无权图，只存储邻居顶点 if not self.directed: self.graph[v].append(u) def has_edge(self, u, v): """判断是否存在从u到v的边。时间复杂度O(deg(u))。""" if u not in self.graph: return False if self.weighted: return any(neighbor == v for neighbor, _ in self.graph[u]) else: return v in self.graph[u] def neighbors(self, u): """返回顶点u的所有邻居。对于带权图，返回(邻居, 权重)列表。""" return self.graph.get(u, []) def vertices(self): """返回图中所有顶点的集合。""" return self.vertices ``` 邻接表的优势立刻显现：添加新顶点非常廉价，存储空间与实际边数成正比。但代价是，判断任意两个顶点间是否有边，需要遍历其中一个顶点的邻居列表，平均时间复杂度为O(k)，其中k是该顶点的度（邻居数）。 ### 1.3 关键差异与选择时机 为了更清晰地展示两种数据结构的核心区别，我整理了下面的对比表格。这张表不是死记硬背的理论，而是你做出工程决策的速查指南。 | 特性维度 | 邻接矩阵 | 邻接表 | 工程启示 | | :--- | :--- | :--- | :--- | | **空间复杂度** | O(V²) | O(V + E) | 当E远小于V²时（稀疏图），邻接表优势巨大。 | | **查询边(u,v)** | **O(1)**，直接索引 | O(deg(u))，需遍历列表 | 如果需要频繁判断任意两点是否连通（如社交网络中的“是否为好友”），矩阵更优。 | | **遍历顶点u的所有邻居** | O(V)，需扫描整行 | **O(deg(u))**，仅遍历实际邻居 | 大多数图算法（BFS/DFS）需要频繁遍历邻居，此时邻接表效率更高。 | | **添加边** | O(1) | O(1)（摊销） | 两者都很快，但邻接表可能涉及列表扩容。 | | **添加顶点** | O(V²)，需要重建矩阵 | **O(1)**，只需添加新键 | 对于动态增长图（如实时添加用户的社交网络），邻接表是唯一选择。 | | **内存访问模式** | 连续内存，缓存友好 | 指针跳转，可能缓存不友好 | 矩阵的连续内存对CPU缓存和GPU计算更有利。 | | **适用图类型** | **稠密图** (E ≈ V²) | **稀疏图** (E << V²) | 选择的关键在于**图密度** = E / V²。 | 那么，如何量化“稀疏”和“稠密”呢？一个经验法则是：**当图密度小于 5% 时，通常认为图是稀疏的，应优先考虑邻接表**。例如，一个有1万个顶点的图，如果边数少于500万条，使用邻接表会更节省空间。当然，这个阈值并非绝对，还需要结合具体的查询和遍历模式来综合判断。 ## 2. 案例一：社交网络中的好友推荐（BFS应用） 社交网络是典型的稀疏图。每个用户（顶点）的好友数量（度）通常远小于总用户数。我们的任务是：给定一个用户，找出他可能认识的人（二度或三度好友），即实现一个简单的好友推荐。 广度优先搜索（BFS）是解决这类“层级扩散”问题的天然工具。它会逐层探索起点周围的顶点。 ### 2.1 使用邻接表实现BFS 由于社交网络中遍历邻居的操作远多于查询任意两人是否为好友，邻接表是更合适的选择。 ```python from collections import deque def bfs_adjacency_list(graph, start, max_depth=2): """ 使用邻接表实现的BFS，用于查找start顶点的max_depth度内的所有顶点。 :param graph: AdjacencyList 实例 :param start: 起始顶点 :param max_depth: 最大探索深度 :return: 字典，键为深度，值为该深度的顶点列表 """ if start not in graph.graph: return {} visited = {start} queue = deque([(start, 0)]) # (顶点, 当前深度) result = {i: [] for i in range(max_depth + 1)} result[0].append(start) while queue: current_vertex, depth = queue.popleft() if depth >= max_depth: continue # 遍历当前顶点的所有邻居 for neighbor_info in graph.neighbors(current_vertex): # 处理带权和不带权图的统一方式 neighbor = neighbor_info if not graph.weighted else neighbor_info[0] if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, depth + 1)) result[depth + 1].append(neighbor) return result # 模拟一个微型社交网络 social_graph = AdjacencyList(directed=False, weighted=False) relationships = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6)] for u, v in relationships: social_graph.add_edge(u, v) # 找出用户0的2度好友（朋友的朋友） recommendations = bfs_adjacency_list(social_graph, start=0, max_depth=2) print("一度好友（直接朋友）:", recommendations[1]) print("二度好友（朋友的朋友）:", recommendations[2]) ``` 输出将会是： ``` 一度好友（直接朋友）: [1, 2] 二度好友（朋友的朋友）: [3, 4, 5] ``` ### 2.2 使用邻接矩阵实现BFS 理论上也可以用邻接矩阵实现BFS，但每次获取邻居都需要扫描一整行（O(V)），在稀疏图上效率低下。 ```python def bfs_adjacency_matrix(graph, start, max_depth=2): """使用邻接矩阵实现的BFS。""" visited = [False] * graph.n visited[start] = True queue = deque([(start, 0)]) result = {i: [] for i in range(max_depth + 1)} result[0].append(start) while queue: u, depth = queue.popleft() if depth >= max_depth: continue # 关键区别：需要扫描整行来寻找邻居 for v in range(graph.n): if graph.has_edge(u, v) and not visited[v]: visited[v] = True queue.append((v, depth + 1)) result[depth + 1].append(v) return result ``` > 提示：在社交网络这种稀疏场景下，`bfs_adjacency_matrix` 的内层循环几乎总是在做无用功，因为它要检查所有V个顶点，即使当前顶点u只有几个好友。而邻接表的版本只检查实际存在的边。 ### 2.3 性能对比与NetworkX实践 为了量化差异，我们可以用`NetworkX`这个专业的图分析库来构建一个更大规模的网络，并进行性能测试。 ```python import networkx as nx import time import matplotlib.pyplot as plt # 生成一个具有小世界特性的随机图（模拟社交网络） # 1000个顶点，每个顶点平均连接10个邻居（稀疏图） G = nx.watts_strogatz_graph(n=1000, k=10, p=0.1) # 将NetworkX图转换为我们自己的数据结构（此处仅演示邻接表转换） def nx_to_adj_list(nx_graph): adj_list = AdjacencyList(directed=nx_graph.is_directed()) for u, v in nx_graph.edges(): adj_list.add_edge(u, v) return adj_list # 将NetworkX图转换为邻接矩阵（稠密矩阵，仅用于小图演示） def nx_to_adj_matrix(nx_graph): n = nx_graph.number_of_nodes() adj_matrix = AdjacencyMatrix(n, directed=nx_graph.is_directed()) for u, v in nx_graph.edges(): adj_matrix.add_edge(u, v) return adj_matrix # 性能测试 adj_list_sparse = nx_to_adj_list(G) # 注意：对于1000个顶点的图，邻接矩阵有100万个元素，内存占用约8MB（float），尚可接受 adj_matrix_sparse = nx_to_adj_matrix(G) start_time = time.time() _ = bfs_adjacency_list(adj_list_sparse, start=0, max_depth=3) list_time = time.time() - start_time start_time = time.time() _ = bfs_adjacency_matrix(adj_matrix_sparse, start=0, max_depth=3) matrix_time = time.time() - start_time print(f"稀疏图BFS - 邻接表耗时: {list_time:.4f} 秒") print(f"稀疏图BFS - 邻接矩阵耗时: {matrix_time:.4f} 秒") ``` 在我的测试环境中，对于1000个顶点、约5000条边的稀疏图，邻接表版本的BFS通常比邻接矩阵版本快**5到10倍**。这个差距随着图规模增大而急剧扩大。 ## 3. 案例二：网站爬虫的链接分析（DFS应用） 深度优先搜索（DFS）常用于探索所有可能路径，比如网络爬虫中递归地抓取网页链接，或者检测图中是否存在环。网页间的链接构成一个有向图，通常也是稀疏的（一个页面不会链接到所有其他页面）。 ### 3.1 使用递归和迭代实现DFS 我们将实现一个爬虫的简化模型：从种子URL开始，递归地抓取所有能通过超链接到达的页面，并检测是否陷入循环（遇到已访问的页面）。 ```python def dfs_recursive_adj_list(graph, node, visited, result): """使用邻接表和递归实现的DFS。""" if node in visited: return visited.add(node) result.append(node) # 模拟“抓取”该页面 for neighbor_info in graph.neighbors(node): neighbor = neighbor_info if not graph.weighted else neighbor_info[0] dfs_recursive_adj_list(graph, neighbor, visited, result) def dfs_iterative_adj_list(graph, start): """使用邻接表和栈实现的迭代DFS，避免递归深度限制。""" visited = set() stack = [start] result = [] while stack: node = stack.pop() if node in visited: continue visited.add(node) result.append(node) # 注意：为了与递归顺序一致（深度优先），需要将邻居逆序入栈 neighbors = graph.neighbors(node) # 处理带权图 neighbor_nodes = [n if not graph.weighted else n[0] for n in neighbors] # 逆序入栈，保证第一个邻居最后出栈（先访问） for neighbor in reversed(neighbor_nodes): if neighbor not in visited: stack.append(neighbor) return result # 模拟一个微型网站链接图 web_graph = AdjacencyList(directed=True) # 链接是有向的 links = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 2)] # 注意(4,2)形成了一个环 for u, v in links: web_graph.add_edge(u, v) print("递归DFS抓取顺序（从页面0开始）:") visited = set() crawl_order = [] dfs_recursive_adj_list(web_graph, 0, visited, crawl_order) print(crawl_order) print("\n迭代DFS抓取顺序:") print(dfs_iterative_adj_list(web_graph, 0)) ``` ### 3.2 检测有向图中的环 DFS的一个经典应用是检测有向图（DAG）中是否存在环，这对于任务调度等场景至关重要。我们可以通过DFS遍历时的状态标记来实现。 ```python def has_cycle_dfs(graph): """使用DFS检测有向图中是否存在环。""" UNVISITED, VISITING, VISITED = 0, 1, 2 state = {} def dfs(node): state[node] = VISITING for neighbor_info in graph.neighbors(node): neighbor = neighbor_info if not graph.weighted else neighbor_info[0] if neighbor not in state: if dfs(neighbor): return True elif state[neighbor] == VISITING: # 遇到正在访问中的节点，说明存在后向边，即环 return True state[node] = VISITED return False for node in graph.vertices: if node not in state: if dfs(node): return True return False print("网站链接图中是否存在环？", has_cycle_dfs(web_graph)) ``` 对于上面的`web_graph`，输出应为`True`，因为路径 2 -> 3 -> 4 -> 2 构成了一个环。一个优秀的爬虫需要识别这种环，避免陷入无限循环抓取。 ## 4. 案例三：城市道路导航（Dijkstra算法） Dijkstra算法是解决单源最短路径问题的基石，广泛应用于导航系统。道路网络通常也是稀疏图（一个十字路口只连接几条路），并且边带有权重（距离或时间）。 ### 4.1 邻接表实现Dijkstra（稀疏图标准方案） 对于稀疏图，Dijkstra算法通常使用**最小堆（优先队列）**来高效地选取当前距离最短的顶点。邻接表能让我们快速获取某个顶点的所有出边。 ```python import heapq def dijkstra_adj_list(graph, start): """ 使用邻接表和最小堆实现的Dijkstra算法。 假设graph是带权的AdjacencyList实例。 """ if not graph.weighted: raise ValueError("Dijkstra算法需要带权图。") # 初始化距离字典，所有顶点距离为无穷大 dist = {v: float('inf') for v in graph.vertices} dist[start] = 0 # 优先队列，元素为 (当前距离, 顶点) pq = [(0, start)] # 记录前驱节点，用于重构路径 prev = {v: None for v in graph.vertices} while pq: current_dist, u = heapq.heappop(pq) # 如果当前弹出的距离大于已知最短距离，跳过（延迟删除） if current_dist > dist[u]: continue # 遍历u的所有出边 for v, weight in graph.neighbors(u): new_dist = current_dist + weight if new_dist < dist[v]: dist[v] = new_dist prev[v] = u heapq.heappush(pq, (new_dist, v)) return dist, prev def reconstruct_path(prev, target): """根据前驱字典重构从起点到target的路径。""" path = [] while target is not None: path.append(target) target = prev.get(target) return path[::-1] # 反转得到从起点到终点的路径 # 构建一个简单的城市道路网（带权有向图） city_graph = AdjacencyList(directed=True, weighted=True) # 添加边：(起点, 终点, 距离/时间) edges = [ (0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 1, 1), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 3) ] for u, v, w in edges: city_graph.add_edge(u, v, w) start_node = 0 distances, predecessors = dijkstra_adj_list(city_graph, start_node) print(f"从节点 {start_node} 到各节点的最短距离:") for node in sorted(distances.keys()): print(f" 到节点 {node}: 距离 = {distances[node]}, 路径 = {reconstruct_path(predecessors, node)}") ``` ### 4.2 邻接矩阵实现Dijkstra（稠密图场景） 对于非常稠密的图（边数接近V²），使用邻接矩阵并配合简单的线性扫描寻找最小距离顶点，有时可能比维护堆更简单，但时间复杂度会上升为O(V²)。 ```python def dijkstra_adj_matrix(graph, start): """使用邻接矩阵实现的Dijkstra算法（适用于稠密图）。""" n = graph.n dist = [float('inf')] * n dist[start] = 0 visited = [False] * n prev = [None] * n for _ in range(n): # 线性扫描寻找未访问顶点中距离最小的 u = -1 min_dist = float('inf') for i in range(n): if not visited[i] and dist[i] < min_dist: min_dist = dist[i] u = i if u == -1: # 所有可达顶点都已处理 break visited[u] = True # 遍历所有顶点，检查是否为邻居 for v in range(n): if graph.has_edge(u, v): weight = graph.get_weight(u, v) new_dist = dist[u] + weight if new_dist < dist[v]: dist[v] = new_dist prev[v] = u return dist, prev ``` > 注意：`dijkstra_adj_matrix` 的内层循环总是O(V)，因为即使边不存在，也需要检查 `graph.has_edge(u, v)`。在稠密图中，大部分边都存在，这个开销可以接受。但在稀疏图中，`dijkstra_adj_list` 的堆优化版本（时间复杂度O((V+E) log V)）要高效得多。 ### 4.3 性能基准测试：稀疏 vs 稠密 让我们用数据说话，对比两种实现在不同密度图上的表现。 ```python import random def generate_random_graph(num_vertices, density, directed=True, weighted=True): """生成一个随机图，density表示边存在的概率（0到1之间）。""" adj_list = AdjacencyList(directed=directed, weighted=weighted) adj_matrix = AdjacencyMatrix(num_vertices, directed=directed, weighted=weighted) for u in range(num_vertices): for v in range(num_vertices): if u != v and random.random() < density: # 忽略自环 weight = random.randint(1, 100) adj_list.add_edge(u, v, weight) adj_matrix.add_edge(u, v, weight) return adj_list, adj_matrix # 测试1：稀疏图 (100顶点，密度0.05，期望边数约500) print("=== 稀疏图测试 (V=100, density=0.05) ===") sparse_list, sparse_matrix = generate_random_graph(100, 0.05) start = time.time() dijkstra_adj_list(sparse_list, 0) list_time_sparse = time.time() - start start = time.time() dijkstra_adj_matrix(sparse_matrix, 0) matrix_time_sparse = time.time() - start print(f"邻接表+堆 耗时: {list_time_sparse:.6f}秒") print(f"邻接矩阵+线性扫描 耗时: {matrix_time_sparse:.6f}秒") print(f"速度比 (矩阵/列表): {matrix_time_sparse/list_time_sparse:.2f}x") # 测试2：较稠密图 (50顶点，密度0.4，期望边数约1000) print("\n=== 较稠密图测试 (V=50, density=0.4) ===") dense_list, dense_matrix = generate_random_graph(50, 0.4) start = time.time() dijkstra_adj_list(dense_list, 0) list_time_dense = time.time() - start start = time.time() dijkstra_adj_matrix(dense_matrix, 0) matrix_time_dense = time.time() - start print(f"邻接表+堆 耗时: {list_time_dense:.6f}秒") print(f"邻接矩阵+线性扫描 耗时: {matrix_time_dense:.6f}秒") print(f"速度比 (矩阵/列表): {matrix_time_dense/list_time_dense:.2f}x") ``` 在我的多次运行中，典型结果是：在稀疏图上，邻接表实现比邻接矩阵实现快**几十到上百倍**；而在较稠密图上，两者的差距缩小到**几倍以内**，甚至在某些情况下（顶点数不多时），邻接矩阵的简单实现可能因为常数因子小而略微领先。这完美印证了我们的理论：**图密度是选择数据结构的关键**。 ## 5. 案例四：依赖管理与拓扑排序 在软件工程中，模块或任务间的依赖关系构成一个有向无环图（DAG）。拓扑排序能给出一个合理的执行顺序，确保每个任务都在其依赖项之后执行。这同样是稀疏图（一个模块不会依赖所有其他模块）。 ### 5.1 基于DFS的拓扑排序（邻接表） Kahn算法（基于入度）和基于DFS的算法是拓扑排序的两种主流方法。这里展示基于DFS的递归版本，它天然适合邻接表。 ```python def topological_sort_dfs(graph): """使用DFS进行拓扑排序。假设graph是有向无环图（DAG）。""" UNVISITED, VISITING, VISITED = 0, 1, 2 state = {} result = [] def dfs(node): state[node] = VISITING for neighbor_info in graph.neighbors(node): neighbor = neighbor_info if not graph.weighted else neighbor_info[0] if neighbor not in state: if not dfs(neighbor): return False elif state[neighbor] == VISITING: # 发现环，拓扑排序不可能 return False state[node] = VISITED result.append(node) return True for node in graph.vertices: if node not in state: if not dfs(node): raise ValueError("图中存在环，无法进行拓扑排序。") return result[::-1] # DFS完成后逆序，得到拓扑顺序 # 模拟一个任务依赖图 task_graph = AdjacencyList(directed=True) # 边A->B表示A依赖于B（或B必须在A之前完成） dependencies = [ ('编译', '预处理'), ('链接', '编译'), ('测试', '链接'), ('部署', '测试'), ('编译', '下载依赖'), # 编译还依赖下载依赖 ('预处理', '下载依赖') ] for dep, target in dependencies: task_graph.add_edge(dep, target) print("任务执行拓扑顺序（从后往前读）:") try: order = topological_sort_dfs(task_graph) for i, task in enumerate(order): print(f"{i+1}. {task}") except ValueError as e: print(e) ``` 输出应该是一个合理的任务顺序，例如 `下载依赖` 最先执行，`部署` 最后执行。 ### 5.2 使用NetworkX进行复杂依赖分析 对于更复杂的依赖分析，如计算关键路径或处理版本冲突，`NetworkX` 提供了更全面的工具。 ```python # 使用NetworkX完成同样的拓扑排序 G_dag = nx.DiGraph() G_dag.add_edges_from(dependencies) if nx.is_directed_acyclic_graph(G_dag): print("\nNetworkX 拓扑排序结果:") print(list(nx.topological_sort(G_dag))) else: print("图中有环！") ``` ## 6. 案例五：图嵌入与机器学习预处理 在图机器学习中，我们经常需要将图结构转换为特征向量或矩阵，以便输入到机器学习模型中。邻接矩阵在这里扮演着核心角色，因为它是图的天然数学表示。 ### 6.1 从邻接表生成邻接矩阵 即使原始数据以邻接表形式存储，在需要矩阵运算时（例如计算图的拉普拉斯矩阵用于谱聚类），我们也需要转换。 ```python def adj_list_to_matrix(adj_list): """将AdjacencyList转换为AdjacencyMatrix。""" vertices = list(adj_list.vertices) vertex_index = {v: i for i, v in enumerate(vertices)} n = len(vertices) is_weighted = adj_list.weighted adj_matrix = AdjacencyMatrix(n, directed=adj_list.directed, weighted=is_weighted) for u in adj_list.graph: u_idx = vertex_index[u] for neighbor_info in adj_list.graph[u]: if is_weighted: v, weight = neighbor_info else: v, weight = neighbor_info, 1 v_idx = vertex_index[v] adj_matrix.add_edge(u_idx, v_idx, weight) return adj_matrix, vertex_index # 示例：将之前的社交网络图转换为矩阵 social_matrix, idx_map = adj_list_to_matrix(social_graph) print("转换后的邻接矩阵（前5行）:") for i in range(min(5, social_matrix.n)): print(social_matrix.matrix[i][:5]) ``` ### 6.2 计算图的基本特征 有了邻接矩阵，我们可以方便地计算许多图论特征。 ```python import numpy as np def graph_features_from_matrix(adj_matrix): """从邻接矩阵计算一些基本的图特征。""" n = adj_matrix.n A = np.array(adj_matrix.matrix) # 将无穷大替换为0，便于计算 A_no_inf = np.where(A == float('inf'), 0, A) features = {} # 1. 图的密度 total_possible_edges = n * (n - 1) if adj_matrix.directed else n * (n - 1) / 2 actual_edges = np.count_nonzero(A_no_inf) - np.count_nonzero(np.diag(A_no_inf)) # 减去自环 features['density'] = actual_edges / total_possible_edges if total_possible_edges > 0 else 0 # 2. 平均度（对于有向图是平均出度） out_degrees = np.count_nonzero(A_no_inf, axis=1) features['avg_out_degree'] = np.mean(out_degrees) # 3. 是否对称（检查是否为无向图） features['is_symmetric'] = np.allclose(A_no_inf, A_no_inf.T) return features features = graph_features_from_matrix(social_matrix) print("\n图特征:") for key, val in features.items(): print(f" {key}: {val:.4f}") ``` ### 6.3 动态选择策略的实现 最后，结合我们所有的讨论，我们可以实现一个智能的图类，它能根据图密度动态选择最合适的内在表示，或者对外提供统一的接口，内部则根据操作类型进行优化。 ```python class SmartGraph: """ 一个智能图类，内部可能同时维护邻接表和邻接矩阵， 并根据操作类型和图的密度自动选择最优的实现。 """ def __init__(self, num_vertices=None, directed=False, weighted=False, auto_switch_threshold=0.1): self.directed = directed self.weighted = weighted self.threshold = auto_switch_threshold # 密度阈值，高于此值倾向于使用矩阵 self._adj_list = AdjacencyList(directed=directed, weighted=weighted) self._adj_matrix = None self._density = 0.0 self._vertices_set = set() def add_edge(self, u, v, weight=1): """添加边，并更新内部状态。""" self._adj_list.add_edge(u, v, weight) self._vertices_set.update([u, v]) # 动态决定是否创建/更新邻接矩阵 self._update_density() if self._density > self.threshold and self._adj_matrix is None: # 图变得足够稠密，创建邻接矩阵 self._convert_to_matrix() elif self._adj_matrix is not None: # 如果矩阵已存在，直接更新 self._update_matrix_edge(u, v, weight) def _update_density(self): V = len(self._vertices_set) if V <= 1: self._density = 0.0 return E = sum(len(neighbors) for neighbors in self._adj_list.graph.values()) if not self.directed: E = E // 2 # 无向图中每条边被记录了两次 max_edges = V * (V - 1) if self.directed else V * (V - 1) // 2 self._density = E / max_edges if max_edges > 0 else 0 def _convert_to_matrix(self): """将当前的邻接表转换为邻接矩阵。""" self._adj_matrix, _ = adj_list_to_matrix(self._adj_list) def _update_matrix_edge(self, u, v, weight): """更新邻接矩阵中的单条边（需要顶点映射，这里简化处理）。""" # 在实际实现中，需要维护顶点到索引的映射 pass def bfs(self, start, max_depth): """进行BFS，自动选择最优实现。""" if self._density < self.threshold or self._adj_matrix is None: # 稀疏图或矩阵不存在，使用邻接表 return bfs_adjacency_list(self._adj_list, start, max_depth) else: # 稠密图，使用邻接矩阵 return bfs_adjacency_matrix(self._adj_matrix, start, max_depth) def has_edge(self, u, v): """查询边，优先使用O(1)的矩阵查询（如果可用）。""" if self._adj_matrix is not None: return self._adj_matrix.has_edge(u, v) else: return self._adj_list.has_edge(u, v) def get_density(self): return self._density ``` 这个 `SmartGraph` 类是一个概念验证，展示了如何根据图密度和操作类型进行自适应优化。在真实系统中，你可能还需要考虑更多因素，比如内存限制、图的动态性（频繁添加/删除顶点）以及具体的工作负载模式。 回顾这五个案例，从社交网络到道路导航，从依赖管理到机器学习，我们看到了邻接表和邻接矩阵如何在不同场景下各展所长。没有一种数据结构是万能的，但理解它们的核心特质——邻接矩阵的快速查询与矩阵运算优势，邻接表的空间效率与高效遍历能力——能让你在面对具体问题时做出精准的选择。下次当你需要处理图数据时，不妨先问自己几个问题：我的图稠密还是稀疏？我需要频繁查询任意两点是否相连吗？我的算法主要操作是遍历邻居吗？图的结构是静态还是动态变化的？回答这些问题，答案自然就会浮现。