Python图论可视化源码实战：从BFS到Dijkstra算法演示

简介这是一套面向计算机与数学相关专业学生、教师及图论自学者的离散数学可视化认知系统源码聚焦图论方向通过图形界面把抽象概念转化为可交互的直观展示适合课程设计、教学演示与算法学习等场景。资源包共63个文件约2.57MB以23个Python脚本为核心承担数据处理、算法实现与界面逻辑配套18个PNG与4个BMP图像、1个GIF动画用于可视化展示5个UI界面文件与qrc、ts等资源构成完整图形界面另有2个C源文件及头文件用于性能相关模块并附readme、许可证与批处理脚本目录结构清晰。目前已有348人学习下载。读者可据此获得一套可直接运行和二次开发的图论可视化工具理解节点、边、权重、矩阵展示等模块的组织方式并借鉴Python与C混合开发的工程结构用于教学辅助或项目实践。1. 从一堆抽象定义到能跑起来的图论可视化这套源码到底解决什么问题离散数学里的图论部分很多人学完一学期脑子里只有「顶点、边、度、连通、欧拉回路」这些词但真给一张图让他手动算个最短路径或者判断是不是二分图还是得在纸上画半天。这套基于 Python 的离散数学可视化认知系统——图论篇就是冲着这个痛点来的。它把图论里那些抽象概念变成屏幕上能拖拽、能高亮、能一步步看算法跑过程的交互界面适合正在学离散数学的学生、需要给学生演示图论算法的老师以及想用 Python 快速搭一个图论演示工具但不想从零造轮子的开发者。源码本身是完整的 Python 工程不是零散脚本拿到手配好环境就能跑起来看效果。2. 先搞清楚这套源码的技术底座为什么选 Python 可视化库而不是纯前端2.1 图论可视化的核心需求决定了技术选型图论可视化和普通数据可视化不一样。普通折线图、柱状图数据是静态的画出来就完事。但图论里你要展示的是结构关系——顶点怎么连、边怎么走、算法每一步选了哪条边、哪个顶点被访问了。这就要求可视化层能实时响应算法状态的变化而不是画一张死图。常见做法是用 Python 做算法逻辑用可视化库做渲染两者通过数据结构耦合。这套源码走的就是这条路。Python 在算法实现上的优势不用多说图论里经典的 BFS、DFS、Dijkstra、Prim、Kruskal用 Python 写出来逻辑清晰、调试方便。可视化层如果用纯前端 JavaScript 的 D3.js 或者 ECharts 的 graph 类型渲染效果确实好但算法逻辑得用 JS 重写一遍对于学离散数学的人来说多一层语言切换就是多一层认知负担。所以这套源码选 Python 做统一技术栈算法和可视化都在一个进程里改算法直接看效果不用前后端来回传数据。这个选型对教学场景特别友好——学生改一行代码界面上立刻能看到图的变化。2.2 源码工程结构拆解拿到源码包之后先别急着跑花五分钟把目录结构看清楚后面改代码或者排错会省很多时间。典型的工程结构大致是这样graph_visualization/ ├── main.py # 入口文件启动可视化界面 ├── algorithms/ # 图论算法模块 │ ├── traversal.py # BFS / DFS │ ├── shortest_path.py # Dijkstra / Floyd │ ├── mst.py # Prim / Kruskal │ └── connectivity.py # 连通性判断、二分图检测 ├── core/ │ ├── graph.py # 图的数据结构定义邻接表/邻接矩阵 │ └── event.py # 算法执行过程中的事件回调 ├── ui/ │ ├── canvas.py # 画布渲染逻辑 │ ├── controls.py # 交互控件添加顶点、连边、运行算法 │ └── styles.py # 颜色、字体、高亮样式 ├── data/ │ └── sample_graphs.json # 预置示例图数据 └── requirements.txt # 依赖清单这个结构里最值得关注的是core/event.py。它定义了一套事件机制算法每执行一步就触发一个事件UI 层监听事件并更新画面。这种设计的好处是算法逻辑和渲染逻辑解耦——你想加一个新算法只要在算法模块里按事件规范发消息就行不用动 UI 代码。2.3 环境配置与依赖安装源码依赖的库通常包括networkx图数据结构与算法参考、matplotlib或pyqt5界面渲染、numpy矩阵运算。具体以requirements.txt为准。安装步骤# 建议先建虚拟环境避免和系统 Python 包冲突 python -m venv venv # Windows 激活 venv\Scripts\activate # macOS / Linux 激活 source venv/bin/activate # 安装依赖 pip install -r requirements.txt这里有个参数要注意如果你用的是 Python 3.10 以上版本某些老版本的pyqt5可能装不上报错信息一般是No matching distribution found。解决办法是升级 pip 再试或者手动指定pyqt55.15.9这种较新的版本。虚拟环境这一步别省我见过太多人因为系统里装了几十个包版本冲突排查半天最后发现建个干净环境五分钟就解决了。依赖装完之后直接python main.py启动。如果界面正常弹出说明环境没问题。如果报ModuleNotFoundError检查一下是不是虚拟环境没激活或者requirements.txt里有包没装上。3. 图的数据结构怎么建邻接表还是邻接矩阵源码里怎么选的3.1 两种存储结构的适用场景对比图论算法的第一步永远是「图怎么存」。邻接矩阵和邻接表是最常见的两种源码里一般会同时支持但默认用哪种取决于要演示的算法类型。对比维度邻接矩阵邻接表空间复杂度O(V²)O(VE)判断两点是否相邻O(1)O(degree)遍历某点所有邻居O(V)O(degree)适合的图类型稠密图稀疏图适合的算法Floyd、矩阵运算类BFS、DFS、Dijkstra这套源码的core/graph.py里通常会用邻接表作为默认存储因为教学场景里演示的图大多是稀疏图——顶点几十个边不会多到 O(V²) 的程度。邻接表用字典实现结构大概是{顶点: [(邻居, 权重), ...]}增删顶点和边都方便。3.2 手动构建一张图并跑通第一个算法先不急着用预置数据自己手动建一张小图跑一遍 BFS把整个流程走通。在源码根目录下新建一个测试脚本from core.graph import Graph from algorithms.traversal import bfs # 创建无向图 g Graph(directedFalse) # 添加顶点参数是顶点标识 for node in [A, B, C, D, E]: g.add_vertex(node) # 添加边参数是 (起点, 终点, 权重) g.add_edge(A, B, 1) g.add_edge(A, C, 1) g.add_edge(B, D, 1) g.add_edge(C, D, 1) g.add_edge(D, E, 1) # 执行 BFS从 A 出发 visit_order bfs(g, startA) print(BFS 访问顺序:, visit_order)这段代码的逻辑很直白先建图再加点和边最后调算法。bfs函数返回的是访问顺序列表你可以拿这个结果和手动推演的结果对照验证算法实现是否正确。参数说明Graph(directedFalse)里的directed控制有向还是无向改成True就是有向图。add_edge的第三个参数是权重无权图统一传 1 就行但 Dijkstra 这类算法必须传真实权重。3.3 从 JSON 文件加载图数据手动建图适合小规模测试但演示复杂图的时候从文件加载更实际。源码的data/sample_graphs.json里预置了几张示例图格式一般是{ graph_1: { directed: false, vertices: [A, B, C, D, E, F], edges: [ {from: A, to: B, weight: 4}, {from: A, to: C, weight: 2}, {from: B, to: C, weight: 1}, {from: B, to: D, weight: 5}, {from: C, to: D, weight: 8}, {from: C, to: E, weight: 10}, {from: D, to: E, weight: 2}, {from: D, to: F, weight: 6}, {from: E, to: F, weight: 3} ] } }加载代码import json from core.graph import Graph def load_graph_from_json(filepath, graph_key): with open(filepath, r, encodingutf-8) as f: data json.load(f) graph_data data[graph_key] g Graph(directedgraph_data[directed]) for v in graph_data[vertices]: g.add_vertex(v) for edge in graph_data[edges]: g.add_edge(edge[from], edge[to], edge[weight]) return g # 使用 g load_graph_from_json(data/sample_graphs.json, graph_1) print(f顶点数: {g.vertex_count()}, 边数: {g.edge_count()})这个加载函数的逻辑是读 JSON → 取指定图 → 建 Graph 对象 → 批量加点加边。参数graph_key对应 JSON 里的图名称方便切换不同示例。注意encodingutf-8别漏Windows 上默认编码不是 UTF-8漏了会报UnicodeDecodeError。4. 核心算法怎么跑起来从 BFS 到 Dijkstra 的代码实操4.1 BFS 与 DFS遍历算法的可视化事件绑定BFS 和 DFS 是图论里最基础的两种遍历方式源码里它们的实现通常会绑定事件回调让 UI 能一步步展示访问过程。以 BFS 为例from collections import deque def bfs(graph, start, callbackNone): visited set() queue deque([start]) visited.add(start) order [] while queue: node queue.popleft() order.append(node) # 触发事件通知 UI 当前访问了哪个节点 if callback: callback(visit, node) for neighbor, weight in graph.neighbors(node): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) if callback: callback(enqueue, neighbor) return order这段代码的关键在callback参数。它是个函数算法每访问一个节点、每入队一个节点就调一次 callback把事件类型和节点信息传出去。UI 层注册这个 callback收到事件就更新画面——比如把当前访问的节点标红把入队的节点标黄。参数说明graph.neighbors(node)返回的是[(邻居, 权重), ...]列表BFS 里权重用不上但接口统一了换 Dijkstra 的时候不用改数据结构。deque是双向队列popleft()是 O(1) 操作比用 list 的pop(0)高效得多。DFS 的实现类似只是把队列换成栈def dfs(graph, start, callbackNone): visited set() stack [start] order [] while stack: node stack.pop() if node in visited: continue visited.add(node) order.append(node) if callback: callback(visit, node) # 逆序入栈保证访问顺序和递归版一致 for neighbor, weight in reversed(graph.neighbors(node)): if neighbor not in visited: stack.append(neighbor) return order这里有个细节reversed(graph.neighbors(node))是为了让迭代版 DFS 的访问顺序和递归版一致。如果不逆序访问顺序会反过来虽然结果都是合法的 DFS 序列但和教科书上的递归过程对不上教学演示时容易让人困惑。4.2 Dijkstra 最短路径优先队列与松弛操作Dijkstra 是图论里最常考也最常演示的算法之一。源码里的实现一般用优先队列堆来选当前距离最小的节点import heapq def dijkstra(graph, start, callbackNone): # 初始化距离表所有节点距离设为无穷大 dist {v: float(inf) for v in graph.vertices()} dist[start] 0 prev {v: None for v in graph.vertices()} # 优先队列元素是 (当前距离, 节点) pq [(0, start)] visited set() while pq: current_dist, node heapq.heappop(pq) if node in visited: continue visited.add(node) if callback: callback(visit, node, current_dist) for neighbor, weight in graph.neighbors(node): if neighbor in visited: continue new_dist current_dist weight if new_dist dist[neighbor]: dist[neighbor] new_dist prev[neighbor] node heapq.heappush(pq, (new_dist, neighbor)) if callback: callback(relax, node, neighbor, new_dist) return dist, prev逻辑说明dist存从起点到各点的最短距离prev存路径前驱用于回溯路径。每次从堆里弹出距离最小的未访问节点然后对它所有邻居做松弛操作——如果经过当前节点到邻居的距离比已知距离更短就更新距离并把邻居压入堆。参数说明callback(relax, node, neighbor, new_dist)这个事件是给 UI 用的用来高亮当前正在松弛的边。heapq是 Python 内置的堆实现注意它只支持最小堆Dijkstra 正好需要每次取最小值所以直接用就行。跑完之后回溯路径def get_path(prev, start, end): path [] current end while current is not None: path.append(current) current prev[current] path.reverse() return path if path[0] start else []4.3 最小生成树Prim 与 Kruskal 的对比演示Prim 和 Kruskal 都是求最小生成树的算法但思路完全不同。Prim 从一个点开始不断扩展Kruskal 按边权排序后逐条加入。源码里两个都实现的话可以对比演示帮学生理解两种贪心策略的差异。Prim 的核心代码def prim(graph, start, callbackNone): mst_edges [] visited {start} # 优先队列存 (边权, 起点, 终点) pq [] for neighbor, weight in graph.neighbors(start): heapq.heappush(pq, (weight, start, neighbor)) while pq: weight, from_node, to_node heapq.heappop(pq) if to_node in visited: continue visited.add(to_node) mst_edges.append((from_node, to_node, weight)) if callback: callback(add_edge, from_node, to_node, weight) for neighbor, w in graph.neighbors(to_node): if neighbor not in visited: heapq.heappush(pq, (w, to_node, neighbor)) return mst_edgesKruskal 的核心代码def kruskal(graph, callbackNone): # 并查集初始化 parent {v: v for v in graph.vertices()} def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路径压缩 x parent[x] return x def union(x, y): rx, ry find(x), find(y) if rx ry: return False parent[rx] ry return True # 所有边按权重排序 edges [] for u in graph.vertices(): for v, w in graph.neighbors(u): if u v: # 避免无向图重复加边 edges.append((w, u, v)) edges.sort() mst_edges [] for w, u, v in edges: if union(u, v): mst_edges.append((u, v, w)) if callback: callback(add_edge, u, v, w) return mst_edges两个算法的 callback 事件类型一样都是add_edgeUI 层可以用同一套高亮逻辑。区别在于 Prim 每次加的是与当前树相连的最小边Kruskal 加的是全局最小且不构成环的边。演示的时候把两个算法的执行过程并排跑学生一眼就能看出差异。5. 避坑与排查跑这套源码时最容易翻车的五个地方5.1 中文乱码JSON 文件读取报 UnicodeDecodeError现象加载sample_graphs.json时直接抛异常提示gbk codec cant decode byte...。原因Windows 系统默认编码是 GBKopen()不指定encoding参数时会用系统默认编码去读 UTF-8 文件。解决所有文件读取操作强制加encodingutf-8。如果源码里有些地方漏了全局搜一下open(逐个补上。另外可以在脚本开头加import sys; sys.setdefaultencoding(utf-8)但 Python 3 已经移除了这个函数更稳妥的做法还是显式指定编码。5.2 递归深度超限DFS 递归版跑大图直接崩现象用递归实现的 DFS 跑一个几百个节点的图报RecursionError: maximum recursion depth exceeded。原因Python 默认递归深度限制是 1000 层图稍微大一点或者退化成链状递归深度就超了。解决两个方案。一是改成迭代版 DFS用栈模拟递归源码里如果两种都提供了就直接换迭代版。二是临时调高递归限制import sys; sys.setrecursionlimit(10000)。但调高限制有栈溢出风险生产环境不推荐教学演示小图够用。5.3 可视化界面卡死算法在主线程跑导致 UI 无响应现象点击「运行算法」按钮后界面直接卡住算法跑完才恢复中间看不到任何动画效果。原因算法执行和 UI 渲染在同一个线程里算法跑的时候 UI 线程被占住没法刷新画面。解决常见做法是把算法放到单独线程里跑通过队列或者信号槽机制把事件传回 UI 线程。如果源码用的是 PyQt可以用QThread加pyqtSignal如果是 tkinter用threading.Thread加queue.Queue。改的时候注意 UI 更新必须在主线程做子线程只负责发事件。5.4 边权为负时 Dijkstra 结果错误现象图里有负权边Dijkstra 跑出来的最短路径明显不对。原因Dijkstra 的贪心策略假设所有边权非负有负权边时优先队列弹出的「当前最小距离」可能不是最终最短距离。解决有负权边就换 Bellman-Ford 或者 SPFA。如果源码只实现了 Dijkstra教学演示时注意别用带负权的图。实在要演示负权手动在算法入口加个检查遍历所有边发现负权就抛异常提示用户换算法。5.5 邻接表里重复加边导致算法结果异常现象同一对顶点之间加了两次边Kruskal 跑出来生成树里出现了重复边或者环。原因add_edge没有去重逻辑无向图里add_edge(A, B)和add_edge(B, A)会存成两条边。解决在add_edge里加判断如果边已存在就更新权重而不是追加。或者在 Kruskal 的边收集阶段用if u v过滤掉重复方向。源码里如果没处理自己补上这几行后面省很多事。6. 进阶玩法把静态源码改成能交互演示的教学工具源码跑通之后如果只是看看效果其实有点浪费。这套东西最大的价值在于可改造——你可以把它变成一个真正能用来上课或者自学的交互工具。我一般会从三个方向动手。第一个方向是加「单步执行」功能。现在的算法是一口气跑完中间过程虽然通过 callback 发了事件但 UI 刷新太快人眼跟不上。改造思路是在 callback 里加一个time.sleep(0.5)让每步之间停顿半秒同时把当前访问的节点、正在松弛的边用不同颜色标出来。这样学生能看清楚算法每一步在干什么比看静态结果图强十倍。import time def slow_callback(event_type, *args): if event_type visit: node args[0] highlight_node(node, colorred) elif event_type relax: from_node, to_node, new_dist args highlight_edge(from_node, to_node, colororange) update_distance_label(to_node, new_dist) time.sleep(0.5) # 控制演示速度第二个方向是加「算法对比」模式。同一张图左边跑 Prim右边跑 Kruskal同时开始看谁先出结果、生成的树是不是一样。这个功能对理解贪心策略的差异特别有用。实现上就是把两个算法的 callback 分别绑到左右两个画布上用一个共享的时钟控制步进节奏。第三个方向是加「自定义图编辑器」。现在加顶点加边得改代码或者改 JSON对不写代码的人来说门槛太高。可以在 UI 上加几个按钮点击画布空白处添加顶点点击两个顶点连线右键删除。底层调用的还是add_vertex和add_edge只是把入口从代码变成了鼠标操作。这个改造工作量稍大但一旦做出来这套源码就从「演示工具」变成了「教学平台」。验证改造是否成功的方法很简单找一张教材上的例题图手动输入进去跑一遍算法看结果和书上答案是否一致。如果一致说明数据结构和算法逻辑没问题如果不一致先检查图建得对不对再检查算法实现有没有边界 bug。从那以后我每次拿到这类教学源码都强制自己先跑通一个最小示例再改一个参数看输出变化最后才动结构。这套流程走下来基本不会出现「改了半天发现方向错了」的情况。希望帮到你。本文还有配套的精品资源点击获取