Python图的存储与遍历全解：三种存储方式 +BFS/DFS

图是计算机中非常重要的非线性数据结构由节点顶点和边组成广泛应用于社交网络、路径规划、推荐系统等场景。在Python中实现图算法第一步就是解决图的存储问题第二步是掌握图的遍历核心算法。本文结合实战代码详细讲解图的三种主流存储方式邻接矩阵、邻接表、边集数组以及最常用的深度优先遍历DFS、广度优先遍历BFS新手也能轻松上手。本文默认讲解无向带权图边没有方向边有权重代码可无缝适配有向图/无权图。一、前置知识我们先统一符号定义方便理解代码n图的节点总数节点编号默认从0开始m图的边总数u, v边的两个端点w边的权重无权图可省略inf无穷大代表两个节点不直接相连二、Python 中图的三种存储方式图的存储没有绝对最优解根据图的稀疏程度选择存储方式是核心原则。1. 邻接矩阵邻接矩阵是最直观的存储方式用二维列表表示图行和列对应图的节点矩阵中e[u][v]的值表示节点u到v的边权重无连接则为无穷大inf代码实现# 定义无穷大必须提前定义inffloat(inf)# 输入节点数n边数mn,mmap(int,input().split())# 初始化n*n的邻接矩阵默认值为inf不连通e[[inf]*nfor_inrange(n)]# 输入m条边填充矩阵for_inrange(m):u,v,wmap(int,input().split())e[u][v]w# 有向图只写这一行e[v][u]w# 无向图边双向连通e[u][u]0# 自己到自己的权重为0e[v][v]0# 测试打印邻接矩阵forrowine:print(row)优缺点✅ 优点查询两点是否连通O(1)时间复杂度简单直观❌ 缺点空间复杂度高O(n²)稀疏图会造成大量空间浪费 适用场景稠密图边数接近n²2. 邻接表邻接表是工程中最常用的存储方式用一维列表存储列表下标对应节点编号每个下标存储一个子列表存放相邻节点边权重python用list实现与下图链表有点不一致思想是一致的。代码实现# 输入节点数n边数mn,mmap(int,input().split())# 初始化n个空列表对应n个节点的邻接表e[[]for_inrange(n)]# 输入m条边填充邻接表for_inrange(m):u,v,wmap(int,input().split())e[u].append((v,w))# 无向图双向添加边e[v].append((u,w))# 测试打印邻接表foriinrange(n):print(f节点{i}的邻接节点{e[i]})优缺点✅ 优点空间利用率极高O(nm)适合绝大多数场景❌ 缺点查询两点是否连通需要遍历节点的邻接边 适用场景稀疏图日常开发90%的场景 关键本文的遍历算法基于邻接表实现3. 边集数组边集数组是最简单的存储方式直接用一维列表存储所有边的信息不关心节点关系。代码实现# 输入节点数n边数mn,mmap(int,input().split())# 初始化空列表存储所有边e[]# 输入m条边直接追加到列表for_inrange(m):u,v,wmap(int,input().split())e.append((u,v,w))# 直接输出所有边print(边集数组,e)优缺点✅ 优点代码极简适合存储所有边❌ 缺点查询两点连通性效率极低O(m) 适用场景仅用于需要遍历所有边的算法如最小生成树❌ 不适合图的遍历三、深度优先搜索DFS图的遍历是指依次访问图中所有节点且每个节点仅访问一次。深度优先搜索DFS是最经典的遍历方式核心思想一路走到底走不通再回溯。代码解析基于邻接表你提供的DFS代码是递归实现简洁易懂# 定义集合记录已访问的节点避免重复访问sset()defdfs(u): DFS遍历函数 :param u: 当前遍历的起始节点 # 1. 访问当前节点打印输出print(u,end )# 2. 标记当前节点为已访问s.add(u)# 3. 遍历当前节点的所有邻接节点forv,_ine[u]:# 4. 如果邻接节点未被访问递归遍历ifvnotins:dfs(v)完整可运行代码整合邻接表DFS直接复制运行# 完整示例邻接表存储 DFS遍历n,mmap(int,input().split())e[[]for_inrange(n)]for_inrange(m):u,v,wmap(int,input().split())e[u].append((v,w))e[v].append((u,w))# DFS遍历sset()defdfs(u):print(u,end )s.add(u)forv,_ine[u]:ifvnotins:dfs(v)# 从节点0开始遍历dfs(0)测试用例输入5 5 0 1 1 0 2 1 1 3 1 1 4 1 2 4 1输出0 1 3 4 2四、广度优先搜索BFS除了DFS**广度优先搜索BFS**也是常用遍历方式核心思想一层一层遍历类似树的层序遍历用队列实现fromcollectionsimportdequedefbfs(start):qdeque()q.append(start)s.add(start)whileq:uq.popleft()print(u,end )forv,_ine[u]:ifvnotins:s.add(v)q.append(v)# 调用sset()bfs(0)五、总结存储方式选择稠密图 → 邻接矩阵稀疏图/日常开发 → 邻接表首选仅需存储边 → 边集数组遍历算法DFS递归实现适合深度探索、路径查找BFS队列实现适合最短路径、层序遍历掌握这三种存储方式和两种遍历算法你就可以轻松入门图的所有基础算法最短路径、最小生成树等啦