图的最小生成树prim算法总结

昨天刚刚把prim算法复习了一遍，现在把将自己的理解与总结写出来分享下，prim算法的思想通俗的讲就是：将连通网N={V，E}的顶点分为最小生成树集合U与非最小生成树集合V-U，然后从U中的顶点到V-U中的顶点的边中选出一条权值最小的边，然后把这条边对应的另一个顶点也加入最小生成树集合U中，反复的循环下去。。。

下面就一起看看prim算法的代码

1.用邻接矩阵存储图

public class Mgraph { int Max = Integer.MAX_VALUE; //代表两个顶点之间直接连通的边 String[] vetxs = {"V0","V1","V2","V3","V4","V5","V6","V7","V8"}; int weight[][]={ //邻接矩阵的权值 {0,10,Max,Max,Max,11,Max,Max,Max}, {10,0,18,Max,Max,Max,16,Max,12}, {Max,Max,0,22,Max,Max,Max,Max,8}, {Max,Max,22,0,20,Max,Max,16,21}, {Max,Max,Max,20,0,26,Max,7,Max}, {11,Max,Max,Max,26,0,17,Max,Max}, {Max,16,Max,Max,Max,17,0,19,Max}, {Max,Max,Max,16,7,Max,19,0,Max}, {Max,12,8,21,Max,Max,Max,Max,0} }; int numVetxs=9; //顶点个数 int numEdges=15; //边的个数 }

2.prim算法的具体实现

public class MiniSpanTree_prim { public void getMiniSpanTree_prim(Mgraph mgraph){ //--------------------------------第一部分：初始化----------------------------------- int adjvex[] = {0,0,0,0,0,0,0,0,0}; //数组元素表示对应的lowcost元素时属于哪个结点的路径权值 int lowcost[] = mgraph.weight[0]; //表示最小生成树结点可到达非最小生成树结点的路径的权值， //值为0的结点位最小生成树的结点 for(int j=1;j<mgraph.numVetxs;j++){ //--------------------------------第二部分：选出最小的权值，并将对应节点的索引存入k----------------------------------- int min = mgraph.Max; //将最小权值设为无穷大的权值 int k = 0; //权值最小的数组下标 for(int i=1;i<mgraph.numVetxs;i++){ if(lowcost[i]<min&&lowcost[i]!=0){ //不要漏了不等于0的判断 min = lowcost[i]; k = i; } } //--------------------------------第三部分：输出对应的边，并把对应的lowcost置0表示该节点已加入最小生成树集合----------------------------------- System.out.println(mgraph.vetxs[adjvex[k]]+"-->"+mgraph.vetxs[k]); lowcost[k] = 0; //不要忘记将已加入最小生成树结点的下标设为0 //--------------------------------第四部分：将最小生成树集合顶点对应的边整合到一起----------------------------------- for(int i=1;i<mgraph.numVetxs;i++){ if(mgraph.weight[k][i]<lowcost[i]&&lowcost[i]!=0){//不要漏了不等于0的判断 lowcost[i] = mgraph.weight[k][i]; adjvex[i] = k; } } } } }

为了便于理解，我把算法用解释分割为四部分。

第一部分分别初始化两个数组， lowcost[] 和 adjvex[] ，lowcost表示当前最小生成树集合U中的顶点所对应边的权值，因为我们是从V0节点开始，所以一开始最小生成树集合U中只有V0，所以lowcost的初始化的值为{0,10,Max,Max,Max,11,Max,Max,Max}，0表示该顶点已经在最小生成树中。adjvex表示lowcost中的权值（非Max）所对应的是最小生成树集合U中的哪个顶点，如一开始U中只有V0，所以lowcost中非Max都是对应的是U种的V0，其实lowcost中的值就是lowcost下标对应的顶点和adjvex中一样下标对应的值对应顶点之间的边，例如lowcost中下标为1的值是10，adjvex[1]的值是0，则10是指V0和V1之间的边，权值为10

第二部分是找出lowcost中权值最小的边，并将该边所对应非最小生成树V-U集合中的顶点的索引保存在k中

第三部分是输出该边，并把lowcost相应位置置0,表示该边对应的非最小生成树V-U集合中的顶点已加入最小生成树集合U中

第四部分为将最小生成树集合顶点对应的边整合到一起，如V1和V2有共同的边到达V3，假设这两条边分别为a1和a2，则比较a1和a2的大小，将权值较小的边加入lowcost中，并改变adjvex中相应的值