贪心策略之求解稠密边的最小生成树-Prim算法

在上一篇中，我们提到了用来求解边数不是特别多的（例如完全图）生成最小生成树的Kruskal算法。对于稠密图，Kruskal算法的效率不高，这时候我们可以用同样经典的Prim算法求解最小生成树问题。

 

Prim算法的核心思想是按照当前点集到还未加入的点集的最短边来加入新的点，直到加入n个点来得到最小生成树，设无向连通图有n个顶点。

 

Prim算法一般包含如下重要步骤：

 

1. 任意选定一个初始点作为当前点集 

 

2. 求当前点集到还未加入的点集的最短边，并把对应的点加入到当前点集--时间复杂度是 O(n^2) 

 

由此看出，Prim算法总的时间复杂度主要由求点集间最短边决定，所以为 O(n^2) 。

 

 

同样，合理的数据结构对于算法的实现十分重要。

 

主体类：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 稠密边图的最小生成树的Prim算法实现
 * @author ql_math
 *
 */
public class PrimForMinimumSpanningTree implements MinimumSpanningTreeGeneration{
	
	/**最小生成树的边的连接*/
	private int[][] connectionSatus;

	public double generateMinimumSpanningTree(double[][] graphicArray) {
		int start_point=1;//可以任意选择一个初始点，这里选择第一个点
		
		SimpleGraphics graph=new SimpleGraphics(graphicArray);
		List<Integer> current_set=new LinkedList<Integer>();//当前点集合
		current_set.add(start_point);
		initPointsConnectionSatus(graph.getPSize(),start_point);//初始化最小生成树的边的连接
		
		int i=1;
		double shortestLength=0;
		while(i<graph.getPSize())//贪心思想加入和当前点集合最近距离的某个点p
		{
			shortestLength+=getShortestPointsPair(connectionSatus, current_set,graph);
		    i++;
		}
		
		return shortestLength;
	}
	
	public int[][] getConnectionSatus() {
		return connectionSatus;
	}

	
	/**
	 * 获得和当前点集合最近距离的某个点p，返回对应的距离
	 * @param connectionSatus
	 * @param current_set
	 * @param graph
	 * @return
	 */
	private double getShortestPointsPair(int[][] connectionSatus, List<Integer> current_set, SimpleGraphics graph) {
		double minLength=Double.MAX_VALUE;
		int[] pair=new int[2];
		for(Integer i:current_set)
		{
			double[] arr=graph.getAdjacencyPoints(i);//获得与当前点连接的点集合
			for(int j=0; j<graph.getPSize();j++)
			{
				if(arr[j]>graph.ERROR&&!current_set.contains(j))
				{
					if(arr[j]<minLength)
					{
						minLength=arr[j];
						pair[1]=j;
						pair[0]=i;
					}
				}
			}
		}
		current_set.add(pair[1]);//加入新的点
		connectionSatus[pair[1]][1]=pair[0];//更新最小生成树的边的连接
		
		return minLength;
	}

	
	/**
	 * 初始化最小生成树的边的连接(所有点都与初始选择点连接)
	 * @param graph
	 * @param start_point
	 * @return
	 */
	private int[][] initPointsConnectionSatus(int pSize,
			int start_point) {
		connectionSatus=new int[pSize][2];
		for(int i=0;i<pSize;i++)
			connectionSatus[i]=new int[]{i,start_point};
		
		return connectionSatus;
	}
	
	public String toString()
	{
		StringBuffer stf=new StringBuffer();
		for(int[] i: connectionSatus)
		{
			stf.append(Arrays.toString(i)+"\r\n");
		}
		return stf.toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MinimumSpanningTreeGeneration st=new PrimForMinimumSpanningTree();
		double[][] graphicArray={{0,0,300,80,50},{0,0,70,75,200},
				{300,70,0,60,0},{80,75,60,0,90},{50,200,0,90,0}};
		System.out.println("最小生成树的权值和是："+st.generateMinimumSpanningTree(graphicArray));
		System.out.println("最小生成树的连接情况是：\r\n"+st.toString());
		
	}

}