图论基础与算法实践：从存储结构到遍历应用

1. 图论基础概念解析图论作为离散数学的重要分支研究由若干节点和连接这些节点的边组成的数学结构。这种抽象模型可以完美描述现实世界中各种复杂关系网络从社交网络的好友关系到城市间的交通路线再到计算机网络的数据传输路径。1.1 图的组成要素一个图G由两个集合构成顶点集VVertices表示实体或节点的集合边集EEdges表示顶点间关系的集合边可以分为无向边(v1, v2)表示v1和v2之间的双向连接有向边v1, v2表示从v1指向v2的单向连接实际应用中无向图适合表示对等关系如社交网络中的好友关系有向图适合表示非对称关系如网页间的超链接。1.2 图的常见类型根据边和顶点的特性图可以分为多种类型简单图无自环和平行边多重图允许平行边带权图边上有权重值完全图任意两顶点间都有边相连稀疏图与稠密图按边数与完全图边数的比例划分示意图展示从左到右依次为无向图、有向图、带权图、完全图2. 图的存储结构详解2.1 邻接矩阵存储法邻接矩阵是图最常见的存储方式之一用一个二维数组adj[][]表示顶点间的连接关系对于无向图adj[i][j] adj[j][i]对于有向图adj[i][j]表示i→j的边对于带权图矩阵元素存储权重值# 无向图的邻接矩阵表示示例 adj_matrix [ [0, 1, 1, 0], # 顶点0与1、2相连 [1, 0, 0, 1], # 顶点1与0、3相连 [1, 0, 0, 1], # 顶点2与0、3相连 [0, 1, 1, 0] # 顶点3与1、2相连 ]适用场景稠密图存储需要频繁判断两顶点是否相邻图规模不是特别大空间复杂度O(V²)2.2 邻接表存储法邻接表为每个顶点维护一个链表存储其相邻顶点节省空间空间复杂度O(VE)适合稀疏图查找效率略低于邻接矩阵# 邻接表表示示例使用字典列表 adj_list { 0: [1, 2], # 顶点0的邻居 1: [0, 3], # 顶点1的邻居 2: [0, 3], # 顶点2的邻居 3: [1, 2] # 顶点3的邻居 }2.3 其他存储方式对比存储方式空间复杂度查询相邻顶点判断两顶点相连适用场景邻接矩阵O(V²)O(V)O(1)稠密图邻接表O(VE)O(1)~O(V)O(V)稀疏图边列表O(E)O(E)O(E)特殊算法实际工程中邻接表因其灵活性成为最常用的存储方式特别是对于大规模稀疏图。3. 图的遍历算法精讲3.1 深度优先搜索(DFS)DFS采用一条路走到黑的策略使用栈结构递归或显式栈实现def dfs(graph, start): visited set() stack [start] while stack: vertex stack.pop() if vertex not in visited: visited.add(vertex) # 将未访问的邻居逆序压栈保证顺序 stack.extend(reversed([n for n in graph[vertex] if n not in visited])) return visited核心特性时间复杂度O(VE)空间复杂度O(V)应用场景拓扑排序、连通分量检测、路径查找3.2 广度优先搜索(BFS)BFS采用层层推进的策略使用队列结构实现from collections import deque def bfs(graph, start): visited set() queue deque([start]) while queue: vertex queue.popleft() if vertex not in visited: visited.add(vertex) # 将未访问的邻居加入队列 queue.extend([n for n in graph[vertex] if n not in visited]) return visited核心特性时间复杂度O(VE)空间复杂度O(V)应用场景最短路径无权图、社交网络的好友推荐3.3 遍历算法的选择策略考量因素DFS优先BFS优先内存限制更适合可能受限最短路径需求不适用最优选择图深度适合深而窄的图适合宽而浅的图环检测天然支持需要额外记录4. 图论算法应用实例4.1 社交网络好友推荐使用BFS的三度人脉推荐算法从用户节点出发进行BFS记录各层节点距离优先推荐第二层联系人共同好友最多def recommend_friends(graph, user, max_depth3): from collections import defaultdict visited {user: 0} queue deque([user]) recommendations defaultdict(int) while queue: current queue.popleft() for neighbor in graph[current]: if neighbor not in visited: visited[neighbor] visited[current] 1 if visited[neighbor] max_depth: queue.append(neighbor) if visited[neighbor] 2: # 二度人脉 # 统计共同好友数 common set(graph[user]) set(graph[neighbor]) recommendations[neighbor] len(common) return sorted(recommendations.items(), keylambda x: -x[1])4.2 路径规划与导航Dijkstra算法实现步骤初始化距离数组起点距离为0选择当前距离最小的未访问节点松弛操作更新邻居节点的最短距离重复直到所有节点访问完毕import heapq def dijkstra(graph, start): distances {vertex: float(infinity) for vertex in graph} distances[start] 0 pq [(0, start)] while pq: current_dist, current_vertex heapq.heappop(pq) if current_dist distances[current_vertex]: continue for neighbor, weight in graph[current_vertex].items(): distance current_dist weight if distance distances[neighbor]: distances[neighbor] distance heapq.heappush(pq, (distance, neighbor)) return distances5. 图论实战注意事项5.1 存储优化技巧对于超大规模图如社交网络使用压缩稀疏行(CSR)格式考虑分片存储使用专业图数据库如Neo4j# CSR格式示例 indptr [0, 2, 4, 6, 8] # 行指针 indices [1, 2, 0, 3, 0, 3, 1, 2] # 列索引 data [1, 1, 1, 1, 1, 1, 1, 1] # 边数据5.2 遍历常见问题内存溢出DFS递归过深改用显式栈实现BFS队列过大限制搜索深度或使用双向BFS性能优化预处理度数高的节点使用位图记录访问状态并行化遍历过程5.3 算法选择指南问题类型推荐算法时间复杂度连通性检测DFS/BFSO(VE)最短路径无权BFSO(VE)最短路径有权无负权DijkstraO(EVlogV)最短路径有权有负权Bellman-FordO(VE)最小生成树Prim/KruskalO(ElogV)6. 现代图论扩展应用6.1 图神经网络(GNN)GNN的基本处理流程节点特征初始化邻居信息聚合特征更新图级信息读出import torch import torch_geometric class GNNLayer(torch.nn.Module): def __init__(self, in_dim, out_dim): super().__init__() self.linear torch.nn.Linear(in_dim, out_dim) def forward(self, x, edge_index): row, col edge_index # 聚合邻居信息 neighbor_msg torch.zeros_like(x) neighbor_msg neighbor_msg.index_add_(0, row, x[col]) # 结合自身特征 return torch.relu(self.linear(x neighbor_msg))6.2 图数据库应用Neo4j的Cypher查询示例// 查找朋友的朋友二度人脉 MATCH (user:User)-[:FRIEND]-(friend)-[:FRIEND]-(fof) WHERE user.name Alice AND NOT (user)-[:FRIEND]-(fof) RETURN fof.name, count(*) as common_friends ORDER BY common_friends DESC LIMIT 106.3 计算机视觉中的图应用SLAM中的位姿图优化将相机位姿表示为节点将观测约束表示为边构建非线性最小二乘问题使用g2o等库进行优化// g2o位姿图优化示例 g2o::SparseOptimizer optimizer; // 添加顶点位姿节点 g2o::VertexSE3* v1 new g2o::VertexSE3(); v1-setId(0); optimizer.addVertex(v1); // 添加边位姿约束 g2o::EdgeSE3* e new g2o::EdgeSE3(); e-setVertex(0, v1); e-setMeasurement(relative_pose); optimizer.addEdge(e); // 优化 optimizer.initializeOptimization(); optimizer.optimize(10);