最小生成树之Prim算法

Prim算法Java朴素版

//Prim算法求最小生成树,使用Java语言的简单实现
// 图用邻接矩阵存储
import java.util.*;
public class PrimMST 
{
	private static int MAX = Integer.MAX_VALUE;

	public static int prim(int graph[][], int n)
	{
		//最小权值和
		int sumcost = 0;

		// lowcost[i]记录以i为终点的边的权值，当lowcost[i]=0时表示终点i加入生成树 
		int lowcost[]=new int[n+1];
		// mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树
		int mst[]=new int[n+1];

		//默认选择1号节点加入生成树
		mst[1] = 0;
		lowcost[1] = 0;
		for (int i = 2; i <= n; i++)
		{
			lowcost[i] = graph[1][i];
			mst[i] = 1;
		}

		// n个节点需要n-1条边构成最小生成树
		for (int i = 2; i <= n; i++)
		{
			int min = MAX;
			int minId = 0;

			for (int j = 2; j <= n; j++)
			{
				if (lowcost[j] < min && lowcost[j] != 0)
				{
					min = lowcost[j];
					minId = j;
				}
			}
			sumcost += min;
			//点midId加入生成树
			lowcost[minId] = 0;
			//输出: 起点 终点 权值
			System.out.println(mst[minId] + " " + minId + " " + min);

			// 更新当前节点minid到其他节点的权值
			for (int j = 2; j <= n; j++)
			{
				if (lowcost[j] > graph[minId][j])
				{
					lowcost[j] = graph[minId][j];
					mst[j] = minId;
				}
			}
			
		}
		return sumcost;


		
	}
	public static void main(String[] args) 
	{
		Scanner in = new Scanner(System.in);
		
		//读取节点和边的数目
		int vertex = in.nextInt();
		int arc = in.nextInt();

		int[][] graph = new int[vertex + 1][vertex + 1];
		//初始化图, 所有节点间距离为无穷大
		for (int i = 1; i <= vertex; i++)
		{
			for (int j = 1; j <= vertex; j++)
			{
				graph[i][j] = MAX;
			}
		}

		//读取边的信息
		for (int i = 1; i <= arc; i++)
		{
			int x = in.nextInt();
			int y = in.nextInt();
			int cost = in.nextInt();
			graph[x][y] = cost;
		}

		//求最小生成树
		System.out.println("-------------");
		int sumcost = prim(graph, vertex);

		System.out.println("最小权值和为: " + sumcost);
	}
}

输入（起点   终点   权值）：

5 8
1 2 2
2 4 3
1 4 4
3 5 5
2 5 6
2 3 6
3 4 10
4 5 15

输出：

1 2 2
2 4 3
2 3 6
3 5 5

注：5 顶点个数  8 边数