祈灵工具箱🪢图论算法演示 - 最短路、最小生成树、拓扑排序、最大流在线
在画布上点击添加顶点，从一个顶点拖到另一个顶点连边，点击边可以修改权重，也可以切换有向图/无向图；或者直接粘贴边列表（每行“起点 终点 权重”），工具会自动布局。选好算法后点“运行”，图上会一步步动画演示：当前处理的顶点、已确定的顶点、队列中的顶点、选中的边和被拒绝的边用不同颜色标出，每一步都有文字说明，可以自动播放、调速，也可以前后单步。支持广度优先和深度优先搜索（含发现/完成时间）、Dijkstra 最短路、可处理负权并检测负权回路的 Bellman-Ford、逐个中转点更新距离矩阵的 Floyd–Warshall、Prim 和 Kruskal 最小生成树、Kahn 拓扑排序（有环时指出具体的环）、连通分量与 Tarjan 强连通分量、二分图判定（不是二分图时给出奇环）、欧拉路径/回路（Hierholzer 算法），以及 Edmonds–Karp 最大流，最后标出最小割。下方同步显示邻接矩阵，图可以导出为 PNG 或 SVG。
免费 · 无需注册 · 浏览器本地处理最后更新：
正在加载工具...
如何使用图论算法可视化
- 1在画布上点击添加顶点、拖动连边，或在下方粘贴边列表，也可以先选一个示例图
- 2选择算法和起点（最大流还要选汇点），点“运行”
- 3用播放、单步按钮观看每一步，查看结果表，需要时导出 PNG/SVG
常见问题
- Dijkstra 和 Bellman-Ford 该用哪个？
- 边权都非负时用 Dijkstra，它每次取出距离最小的未确定顶点，速度快；有负权边时 Dijkstra 可能出错，要用 Bellman-Ford，它把所有边松弛 n − 1 轮，第 n 轮若还能变短就说明存在负权回路。注意无向图里一条负权边本身就构成负权回路。
- Prim 和 Kruskal 算法得到的最小生成树一样吗？
- 总权重一定相同，但当有相同权重的边时，选出的边可能不同，因为最小生成树不唯一。Kruskal 把边按权重从小到大排序，依次加入不形成环的边；Prim 从一个顶点出发，每次加入连接树内外的最小边。图不连通时得到的是最小生成森林。
- 怎么判断一个图能不能一笔画？
- 无向图能一笔画（存在欧拉路径）的条件是：有边的顶点都连通，且奇数度顶点的个数为 0 或 2；为 0 时可以回到起点（欧拉回路），为 2 时必须从一个奇数度顶点出发、到另一个结束。有向图要求每个顶点入度等于出度，或恰好一个顶点出度多 1、一个顶点入度多 1。工具会先检查条件，再用 Hierholzer 算法给出具体路线。
- 最大流和最小割有什么关系？
- 最大流最小割定理：从源点到汇点的最大流量等于所有割中容量最小的那个。Edmonds–Karp 算法每次用 BFS 找最短的增广路并推送瓶颈流量，直到找不到增广路；此时残量网络中从源点能到达的顶点构成 S 集合，从 S 指向其余顶点的边就是最小割，它们都已满流。