最小代价生成树

1、Prim算法
设G＝（V，E）是带权的连通图，T＝（V’，E’）是正在构造中的最小代价生成树。初始状态下，该树只有一个顶点，没有边，即V’={u0}，E’={ }，u0是任意选择的顶点。

从初始状态开始，重复以下操作：
寻找一条权值最小的边（u’,v’），u’端点在构造中的生成树上，而v’不在该生成树上，然后将此最小边加入生成树。重复以上操作，直至V＝V’。

代码如下：

/*** Prim最小代价生成树 O(n2)* * @param graph* @param k:起点* @param nearest:保存最小权值边的起点* @param lowcost:保存最小权值*/public void Prim(Graph graph, int k, int[] nearest, int[] lowcost) {// 初始化for (int i = 0; i < nodeNum; i++) {nearest[i] = -1;lowcost[i] = Integer.MAX_VALUE;mark[i] = false;}// 将源点k加入生成树lowcost[k] = 0;nearest[k] = k;mark[k] = true;for (int i = 0; i < nodeNum; i++) {// 找出最小邻接点for (Node node = vertex[k].next; node != null; node = node.next) {if (!mark[node.id] && lowcost[node.id] > node.weight) {lowcost[node.id] = node.weight;nearest[node.id] = k;// nearest[end] = start}}int min = Integer.MAX_VALUE;for (int j = 0; j < nodeNum; j++) {if (!mark[j] && lowcost[j] < min) {min = lowcost[j];k = j;// 重新定义起点为该最小邻接点}}mark[k] = true;// 将该最小邻接点加入生成树}}

2、Kruskal算法
设G＝（V，E）是带权的连通图，T＝（V’，E’）是正在构造中的最小代价生成树。初始状态下，该生成树包含n棵只有根节点的树，即V＝V’，E’={ }。

从初始状态，重复以下操作：
在E中选择一条代价最小的边（u,v），若u、v分属于两颗不同的树（若属于同一棵树，则会形成回路），则将边（u,v）加入生成树，否则继续下一条边，直至E’包含n-1条边为止。

借助优先权队列保存所有的边，每次出队列的总是权值最小的边；
借助并查集判断一条边的两个顶点u、v是否分属于两棵不同的子树。

代码如下：

/*** Kruskal最小代价生成树 O(elbe)* * @param queue* @param n*/public void Kruskal(PriorityQueue queue, int n) {int k = 0, u, v;UFset ufset = new UFset();ufset.createUFset(n);System.out.println("最小代价生成树：");while (k < n - 1 && !queue.isEmpty()) {EdgeNode eNode = queue.poll();u = ufset.Find(eNode.u);v = ufset.Find(eNode.v);if (u != v) {ufset.Union(u, v);k++;System.out.println(eNode.u + "," + eNode.v + "," + eNode.weight);}}if (k < n - 2)System.out.println("This graph is not connected!");}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！