Prim算法

发表于 更新于 分类于

Prim算法用来解决在一个无向图中找一棵最小生成树的问题，在这之前需要了解一些概念

  • 连通图：在一个无向图中，任意两个顶点都有一条路径连通，那么称该无向图是连通图
  • 强连通图：在一个有向图中，任意两个顶点都有路径相通，那么该有向图是强连通图
  • 连通网：即带权连通图，图的每条边都对应一个权值，权是连接两个顶点的代价。
  • 生成树：能连接图中所有顶点而又不产生回路的任何子图都是该图的生成树。
  • 连通图：代价最小的生成树，即边上的权值之和最小

如果之前看过求最短路径的Dijkstra算法，那么prim算法是相当容易理解的，两者差距很小。
Prim算法和Dijkstra算法一样，对每个顶点保留一个dv和pv以及一个flag，标识该顶点是已知的还是未知的。dv是连接当前顶点v到已知顶点的最短边的权，pv是导致dv改变的最后的顶点。算法的其余部分一模一样，只有一点不同，因为dv的定义不同，因此它的更新法则也不同，它的法则更简单了。

举个栗子

我们以1-1中图为例，寻找它的最小生成树 。（应当注意，最小生成树不是唯一的）

图1-2就是详细的算法过程，放大仔细看，应当很明了，绿色标记的顶点就是已知的顶点，图看不懂，下面还有文字叙述

** 算法过程 **

  1. 我们以 a 作为起点，将 a 顶点添加到树中并且标记为已知
  2. 找到与 a 相接的所有顶点中权值最小的，也就是 d ，将 d 添加到树中并标为已知
  3. 在与顶点 a 和 d 相接的所有未知顶点中，b 和 c 是权值最小的，为2，这里我们选择 b ，当然也可以选择 c 。将 b 添加到树中并标记为已知
  4. 在与a、b、d相接的未知顶点中，c 最小，添加到树中并标记已知
  5. 剩下的未知顶点中，g 和 d 的距离最小，为4,将 g 添加的树中并标记为已知
  6. 之后是 f 和 g 的距离是最小的，只有1,将 f 添加到树中并标记已知
  7. 最后一个顶点 e 离 g 最近，选择，结束

我们仍需要用一张表格来记录每一阶段的情况变化，而且能从这张表中获取我们想要的任何信息

代码实现

1-1的图的邻接表也非常简单，稍微瞄一眼就行了。

1
2
3
4
5
6
7
8
/**
 * 邻接表节点模型
 */
class Node<T>{
    T data;         //顶点中的数据
    int weight;    //到next顶点的权值
    Node<T>next;   //下一个顶点
}
1
2
3
4
5
6
7
8
/**
 * 算法所需用到的盒子模型，就是表格
 */
class Box<T>{
    boolean known=false;
    int dv=Integer.MAX_VALUE;
    T pv;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static <T> Map<T,Box<T>> prim(T s,Map<T,Node<T>> graph){
        //初始化盒子
        Map<T,Box<T>> boxMap=initBox(s,graph);
        if (boxMap==null){
            System.out.println("图中没有这个顶点，算法结束");
            return null;
        }

        int cnt=0;   //阶段次数（打印数据使用的）
        while (true){
            int min=Integer.MAX_VALUE;
            // v 是此阶段找到的最小的未知的顶点
            T v=s;
            //寻找最小的未知顶点
            for(Map.Entry<T, Box<T>> entry:boxMap.entrySet()){
                if(!entry.getValue().known&&entry.getValue().dv<min){
                    min=entry.getValue().dv;
                    v=entry.getKey();
                }
            }
            //打印相关信息
            System.out.println();System.out.println();System.out.println();System.out.println();System.out.println("第"+(++cnt)+"个阶段：");
            for(Map.Entry<T, Box<T>> entry:boxMap.entrySet()){
                System.out.println(entry.getKey()+"\t\tknown:"+entry.getValue().known+"\t\tdv:"+entry.getValue().dv+"\tpv:"+entry.getValue().pv);
            }
            //如果min没变 说明所有点都是known 的了 算法结束
            if(min==Integer.MAX_VALUE){
                return boxMap;
            }
            //将最小的顶点置为已知
            boxMap.get(v).known=true;
            //遍历与此顶点相邻的点
            Node<T> n=graph.get(v);
            while (n!=null){
                if(!boxMap.get(n.data).known && n.weight<boxMap.get(n.data).dv){
                    //更新dv
                    boxMap.get(n.data).dv=n.weight;
                    //更新pv
                    boxMap.get(n.data).pv=v;
                }
                n=n.next;
            }
        }
    }

打印出来的最后一个阶段的情况，是我们预期的结果

** 完整代码 **