Java实现Prim算法
package com.java;
import java.util.*; /**
* 普里姆算法—Prim算法
* 算法思路：将图中所有的顶点分为两类：树顶点（已被选入生成树的顶点）和非树顶点（还未被选入生成树的顶点）。
* 1）首先选择任意一个顶点加入生成树；
* 2）接下来要找出一条边添加到生成树，这需要枚举每一个树顶点到每一个非树顶点所有的边，然后找到最短边加入到生成树；
* 3）按照此方法重复n-1次，直到将所有顶点都加入到生成树中。
*/ public class Prim {
static int MAX = Integer.MAX_VALUE; public static void main(String[] args) {
int[][] map = new int[][] {
{ 0, 2, 14, 1},
{ 2, 0, 5, MAX},
{ 14, 5, 0, 8},
{ 1, MAX, 8, 0}};
prim(map, map.length);
}
public static void prim(int[][] graph, int n){ char[] c = new char[]{'A','B','C','D'};
int[] lowcost = new int[n]; //到新集合的最小权
int[] mid= new int[n];//存取前驱结点的下标
List<Character> list=new ArrayList<Character>();//用来存储加入到生成树结点
int i, j, min, minid , sum = 0;
//初始化辅助数组
for(i=1;i<n;i++)
{
lowcost[i]=graph[0][i];
mid[i]=0;
}
//加入第一个根节点
list.add(c[0]);
//加入其他的n-1个节点
for(i=1;i<n;i++)
{
min=MAX;
minid=0;
//每次找到距离集合最近的点
for(j=1;j<n;j++)
{
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j];
minid=j;
}
}
if(minid==0) return;
//将找到的最小值的节点加入到生成树
list.add(c[minid]);
//加入生成树后的节点值设为0
lowcost[minid]=0;
sum+=min;
System.out.println(c[mid[minid]] + "到" + c[minid] + " 权值：" + min);
//加入该点后，更新其它点到集合的距离
for(j=1;j<n;j++)
{
if(lowcost[j]!=0&&lowcost[j]>graph[minid][j])
{
lowcost[j]=graph[minid][j];
mid[j]=minid;
}
}
}
System.out.println("最小生成树的权值为sum=" + sum); }
}