Prim算法用来解决在一个无向图中找一棵最小生成树的问题,在这之前需要了解一些概念
- 连通图:在一个无向图中,任意两个顶点都有一条路径连通,那么称该无向图是连通图
- 强连通图:在一个有向图中,任意两个顶点都有路径相通,那么该有向图是强连通图
- 连通网:即带权连通图,图的每条边都对应一个权值,权是连接两个顶点的代价。
- 生成树:能连接图中所有顶点而又不产生回路的任何子图都是该图的生成树。
- 连通图:代价最小的生成树,即边上的权值之和最小
如果之前看过求最短路径的Dijkstra算法,那么prim算法是相当容易理解的,两者差距很小。
Prim算法和Dijkstra算法一样,对每个顶点保留一个dv和pv以及一个flag,标识该顶点是已知的还是未知的。dv是连接当前顶点v到已知顶点的最短边的权,pv是导致dv改变的最后的顶点。算法的其余部分一模一样,只有一点不同,因为dv的定义不同,因此它的更新法则也不同,它的法则更简单了。
举个栗子
我们以1-1中图为例,寻找它的最小生成树 。(应当注意,最小生成树不是唯一的)
图1-2就是详细的算法过程,放大仔细看,应当很明了,绿色标记的顶点就是已知的顶点,图看不懂,下面还有文字叙述
** 算法过程 **
- 我们以 a 作为起点,将 a 顶点添加到树中并且标记为已知
- 找到与 a 相接的所有顶点中权值最小的,也就是 d ,将 d 添加到树中并标为已知
- 在与顶点 a 和 d 相接的所有未知顶点中,b 和 c 是权值最小的,为2,这里我们选择 b ,当然也可以选择 c 。将 b 添加到树中并标记为已知
- 在与a、b、d相接的未知顶点中,c 最小,添加到树中并标记已知
- 剩下的未知顶点中,g 和 d 的距离最小,为4,将 g 添加的树中并标记为已知
- 之后是 f 和 g 的距离是最小的,只有1,将 f 添加到树中并标记已知
- 最后一个顶点 e 离 g 最近,选择,结束
我们仍需要用一张表格来记录每一阶段的情况变化,而且能从这张表中获取我们想要的任何信息
代码实现
1-1的图的邻接表也非常简单,稍微瞄一眼就行了。
1 | /** |
1 | /** |
1 | public static <T> Map<T,Box<T>> prim(T s,Map<T,Node<T>> graph){ |
打印出来的最后一个阶段的情况,是我们预期的结果