【資料結構】【圖論】【最小生成樹】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. 預設有可能出現輸入相同邊兩次的情況，這時候取最小值