图的应用算法详解
上一篇博客主要讲了数据结构中图的一些基础知识。（附上链接数据结构——图）
这篇博客重点讲解一下图的应用里几个算法的具体计算过程。
| 应用 | 算法 | 适用的图 | 备注 |
|---|---|---|---|
| 最小生成树 | Prim | 无向图 | 适合稠密图 |
| 最小生成树 | Kruskal | 无向图 | 适合稀疏图 |
| 最短路径 | Dijkstra | 有向图 | 单源点最短路径 |
| 最短路径 | Floyd | 有向图 | 每一对顶点之间的最短路径 |
| 拓扑排序 | / | 有向无环，AOV网 | |
| 关键路径 | / | 有向无环加权，AOE网 |
1. 最小生成树（MST）
- 对于一个带权连通无向图，生成树不同，每棵树的权也可能不同。其中权值之和最小的那棵树称为最小生成树。
- 最小生成树的特点：
（1）不唯一；
（2）边的权值之和唯一，而且是最小的；
（3）边数 = 顶点数 - 1；
（1）Prim算法
（2）Kruskal算法
2. 最短路径
- 带权路径长度：对于带权图，从一个点 v0 到 其余各点 vi 的一条路径上所经过边的权值之和；
- 最短路径：min 带权路径长度。