# 图论算法演示 - 最短路、最小生成树、拓扑排序、最大流在线

> 在线画图并逐步演示图论算法：BFS/DFS、Dijkstra、Bellman-Ford、Floyd、Prim、Kruskal、拓扑排序、强连通分量、二分图、欧拉路径和最大流最小割。

- 网址: https://qilingtools.com/zh/math/graph-theory
- 分类: 数学工具 (https://qilingtools.com/zh/math)
- 标签: [数学](https://qilingtools.com/zh/tags/math), [学习教育](https://qilingtools.com/zh/tags/education), [图表可视化](https://qilingtools.com/zh/tags/chart), [算法](https://qilingtools.com/zh/tags/algorithm)
- 最后更新: 2026-10-26
- 价格: 免费，无需注册
- 隐私: 在浏览器本地处理，文件不上传服务器

在画布上点击添加顶点，从一个顶点拖到另一个顶点连边，点击边可以修改权重，也可以切换有向图/无向图；或者直接粘贴边列表（每行“起点 终点 权重”），工具会自动布局。选好算法后点“运行”，图上会一步步动画演示：当前处理的顶点、已确定的顶点、队列中的顶点、选中的边和被拒绝的边用不同颜色标出，每一步都有文字说明，可以自动播放、调速，也可以前后单步。支持广度优先和深度优先搜索（含发现/完成时间）、Dijkstra 最短路、可处理负权并检测负权回路的 Bellman-Ford、逐个中转点更新距离矩阵的 Floyd–Warshall、Prim 和 Kruskal 最小生成树、Kahn 拓扑排序（有环时指出具体的环）、连通分量与 Tarjan 强连通分量、二分图判定（不是二分图时给出奇环）、欧拉路径/回路（Hierholzer 算法），以及 Edmonds–Karp 最大流，最后标出最小割。下方同步显示邻接矩阵，图可以导出为 PNG 或 SVG。

## 使用步骤

1. 在画布上点击添加顶点、拖动连边，或在下方粘贴边列表，也可以先选一个示例图
2. 选择算法和起点（最大流还要选汇点），点“运行”
3. 用播放、单步按钮观看每一步，查看结果表，需要时导出 PNG/SVG

## 功能特点

- 可视化编辑：点击加点、拖动连边、改权重、有向/无向切换
- 边列表导入导出，力导向布局与环形布局
- BFS、DFS（发现/完成时间）逐步动画
- Dijkstra、Bellman-Ford（负权回路检测）、Floyd–Warshall 距离矩阵
- Prim 与 Kruskal 最小生成树（不连通时给出生成森林）
- 拓扑排序与环检测、连通分量、Tarjan 强连通分量
- 二分图判定（给出奇环）、欧拉路径与回路
- Edmonds–Karp 最大流与最小割，邻接矩阵，导出 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 指向其余顶点的边就是最小割，它们都已满流。

## 相关工具

- [函数图像](https://qilingtools.com/zh/math/graph): 免费在线函数绘图工具：输入 sin(x)、x^2、1/x 等公式即可画出函数图像，支持多条曲线叠加、参数方程、极坐标、数据点散点图与最小二乘拟合，可拖动缩放并导出 PNG/SVG。
- [科学计算器](https://qilingtools.com/zh/math/calculator): 免费在线科学计算器：直接输入 2*(3+4)^2、sin(pi/6)、log(8,2) 这样的算式即可得到结果，支持角度/弧度切换、阶乘、组合数与历史记录，浏览器本地计算。
- [方程求解](https://qilingtools.com/zh/math/equation): 免费在线解方程：输入系数即可求一元一次方程、一元二次方程（含判别式、顶点、因式分解、复数根）、一元三次方程与二元一次方程组的解，并给出计算过程。
- [分数计算器](https://qilingtools.com/zh/math/fraction): 免费在线分数计算器：分数加减乘除并自动约分，化简最简分数，分数转小数（识别循环节）、小数转分数（支持 0.1(6) 这类循环小数），带分数一并给出。
- [百分比计算](https://qilingtools.com/zh/math/percentage): 免费在线百分比计算器：求某数的百分之几、一个数是另一个数的百分之几、增长率与下降率、增加/减少百分比后的值，以及已知百分比反推原值，并给出计算公式。
- [质因数分解](https://qilingtools.com/zh/math/prime): 免费在线质因数分解工具：把整数分解成质因数连乘并写成幂的形式，列出全部因数与因数之和，判断一个数是不是质数并给出相邻质数，还能列出任意区间内的质数表。
- [最大公约数](https://qilingtools.com/zh/math/gcd-lcm): 免费在线求最大公约数（GCD）与最小公倍数（LCM）：支持两个或多个整数，给出是否互质、乘积、各数的质因数分解，两个数时还会列出辗转相除法的每一步。
- [统计计算](https://qilingtools.com/zh/math/statistics): 免费在线统计计算器：粘贴一组数据即可得到平均数、中位数、众数、极差、四分位数、样本与总体的方差和标准差、标准误、变异系数与异常值，适合作业与实验数据处理。