【数据结构】【图论】【最小生成树】Prime算法

一、问题

最小生成树解决的问题如下所示：

       假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？

       使用Prime算法构造最小生成树，将生成树上的边的权值累加即可得到最小值。

二、Prime算法核心思想

       取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。

       动态图演示：

三、算法实现（Java）

import java.util.Scanner;

public class Prime
{
	private final static int maxNodeValue=(1<<31)-1;
	public static void main(String[] args){
		Scanner scanner=new Scanner(System.in);
		int[][] map=new int[101][101];
		while(scanner.hasNext()){
			init(map);
			int nodeCount=scanner.nextInt();
			int edgeCount=scanner.nextInt();
			for(int i=0;i<edgeCount;i++){
				int node1=scanner.nextInt();
				int node2=scanner.nextInt();
				int edgeValue=scanner.nextInt();
				map[node1][node2]=edgeValue;
				map[node2][node1]=edgeValue;
			}
			int cost=prime(nodeCount,map);
			System.out.println(cost);
		}
	}
	public static int prime(int nodeCount,int[][] map){
		int[] lowcost=new int[101];
		int cost=0;
		lowcost[1]=-1;
		for(int i=2;i<=nodeCount;i++){
			lowcost[i]=map[1][i];
		}
		for(int i=1;i<=nodeCount-1;i++){
			int min=maxNodeValue;
			int k=0;
			for(int j=1;j<=nodeCount;j++){
				if(min>lowcost[j]&&lowcost[j]!=-1){
					min=lowcost[j];
					k=j;
				}
			}
			cost+=min;
			lowcost[k]=-1;
			for(int j=1;j<=nodeCount;j++){
				if(lowcost[j]!=-1&&lowcost[j]>map[k][j]){
					lowcost[j]=map[k][j];
				}
			}
		}
		return cost;
	}
	public static void init(int[][] map){
		for(int i=0;i<map.length;i++){
			for(int j=0;j<map[i].length;j++){
				map[i][j]=maxNodeValue;
			}
		}
	}
}
           

      这里使用lowcost数组保存非生成树上的节点到生成树的最小值，每次添加一个节点到生成树，都需要刷新lowcost数组。

四、测试数据

输入

6 10

1 2 6

2 5 3

5 6 6

6 4 2

4 1 5

3 1 1

3 2 5

3 5 6

3 6 4

3 4 5

输出

15

 五、ACM

题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2144

AC代码：

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main
{
	private final static int maxNodeValue=(1<<31)-1;
	public static void main(String[] args){
		Scanner scanner=new Scanner(System.in);
		int[][] map=new int[101][101];
		while(scanner.hasNext()){
			init(map);
			int nodeCount=scanner.nextInt();
			int edgeCount=scanner.nextInt();
			for(int i=0;i<edgeCount;i++){
				int node1=scanner.nextInt();
				int node2=scanner.nextInt();
				int edgeValue=scanner.nextInt();
				if(map[node1][node2]>edgeValue){
					map[node1][node2]=edgeValue;
					map[node2][node1]=edgeValue;
				}
			}
			int cost=prime(nodeCount,map);
			System.out.println(cost);
		}
	}
	public static int prime(int nodeCount,int[][] map){
		int[] lowcost=new int[101];
		int cost=0;
		lowcost[1]=-1;
		for(int i=2;i<=nodeCount;i++){
			lowcost[i]=map[1][i];
		}
		for(int i=1;i<=nodeCount-1;i++){
			int min=maxNodeValue;
			int k=0;
			for(int j=1;j<=nodeCount;j++){
				if(min>lowcost[j]&&lowcost[j]!=-1){
					min=lowcost[j];
					k=j;
				}
			}
			cost+=min;
			lowcost[k]=-1;
			for(int j=1;j<=nodeCount;j++){
				if(lowcost[j]!=-1&&lowcost[j]>map[k][j]){
					lowcost[j]=map[k][j];
				}
			}
		}
		return cost;
	}
	public static void init(int[][] map){
		for(int i=0;i<map.length;i++){
			for(int j=0;j<map[i].length;j++){
				map[i][j]=maxNodeValue;
			}
		}
	}
}
           

   这道题目出的实际上并不好，有默认的规则：

1. 顶点的个数=最大值，顶点值一定从0开始，依次递增到最大值（顶点的个数）
2. 默认从0开始加入生成树
3. 默认有可能出现输入相同边两次的情况，这时候取最小值