贪心策略之求解稀疏边的最小生成树-Kruskal算法

最小生成树问题是贪心策略的经典应用，其中Kruskal算法用来求解边数不是特别多的（例如完全图）图的最小生成树。这里我们以无向连通图为例。

 

Kruskal算法的核心思想是按照边的从小到大的顺序依次加入到点集中，直到加入n-1条边，设无向连通图有n个顶点。

 

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

 

1. 边集按照权值由小到大的顺序排序--时间复杂度是 O(e*log(e) ) （e为边数）

 

2. 检查待加入的边是否和当前求得的点集构成回路--时间复杂度是 O(n) （n为当前求得点集的顶点数）

 

3. 点集的合并-如果用数组形式，时间复杂度是 O(n) （待加入的点所在点集合的顶点数）

 

由此看出，Kruskal算法总的时间复杂度主要由排序决定，所以为 O(e*log(e) ) （e为边数）。

显然，对于稀疏边的图，Kruskal算法是很适合的。

 

在实现算法的时候，数据结构的设计是十分重要的，特别是对于检查回路和点集的合并。合理的设计数据结构并充分利用Java的集合类将大大简化实现的难度。

 

主体类：

 

import greedyProgramming.SimpleGraphics.Edge;
import java.util.List;

/**
 * 稀疏边图的最小生成树的Kruskal算法实现
 * @author ql_math
 *
 */
public class KruskalForMinimumSpanningTree implements MinimumSpanningTreeGeneration{
	
	public double generateMinimumSpanningTree(double[][] graphicArray)
	{
		SimpleGraphics graph=new SimpleGraphics(graphicArray);
		List<Edge> sortedEdges = graph.sortGraphicEdges();//按照边的长度排序（短的在前）
		
		int n=graph.getPSize();//顶点数目
		int i=0,j=0;
		double shortestLength=0;
		
		while(i<sortedEdges.size())//贪心思想加入当前权值最小的边并检查是否含有回路
		{
			Edge e=sortedEdges.get(i++);
			
			Point stP=e.startPoint;
			Point edP=e.endPoint;
			
			if(stP.getBelongToList().contains(edP))//当前待加入的边加入后形成回路
				continue;
			
			stP.getBelongToList().addAll(edP.getBelongToList());//合并两个不同的点集
			edP.setBelongToList(stP.getBelongToList());//保持所属集合一致性

			j++;//合服要求的边数+1
			shortestLength+=e.length;
			
			if(j==n-1)
				break;

		}
	
		return shortestLength;
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MinimumSpanningTreeGeneration st=new KruskalForMinimumSpanningTree();
		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));
	}

}

 

 

 数据结构类：

SimpleGraphics类

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class SimpleGraphics {
	
	public final static double ERROR=1e-3;
	
	/**无向图的邻接矩阵表示*/
	private int[][] adjArray;
	
	/**无向图的数组表示*/
	private double[][] graphArray;
	
	/**点集合*/
	private Point[] points;

	/**点个数*/
	private int pSize;
	
	static class Edge implements Comparable<Edge>
	{
		Point startPoint;
		Point endPoint;
		
		double length;
		
		Edge(Point point1,Point point2, double value)
		{
			startPoint=point1;
			endPoint=point2;
			length=value;
		}

		@Override
		public int compareTo(Edge o) {
			if(length-o.length>ERROR)
				return 1;
			if(o.length>ERROR)
				return -1;
			
			return 0;
		}
	}

	
	/**
	 * 无向图的二维数组表示
	 * @param graphArray
	 */
	public SimpleGraphics(double[][] graphArray)
	{
		this.graphArray=graphArray;
		pSize=graphArray.length;
		points=new Point[pSize];
		for(int i=0; i<pSize;i++)
			points[i]=new Point(i);
	}
	
	/**
	 * 
	 * @return
	 */
	public List<Edge> sortGraphicEdges()
	{
		
		List<Edge> eList=new LinkedList<Edge>();
		
		for(int i=0;i<pSize;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(graphArray[i][j]>0)
				{
					eList.add(new Edge(points[i],points[j],graphArray[i][j]));
				}
			}
		}
		
		Collections.sort(eList);
		
		return new ArrayList<Edge>(eList);
	}
	
	public Point[] getPoints()
	{
		return points;
	}
	
	public void setPoints(Point[] points) {
		this.points = points;
	}

	
	
	public void updateGraphicArray(int i, int j, double value)
	{
		graphArray[i][j]=value;
	}
	
	public void updateAdjacencyArray(int i, int j, int status)
	{
		adjArray[i][j]=status;
	}
	
	public void setGraphicArray(double[][] graphArray)
	{
		this.graphArray=graphArray;
	}
	
	public double[][] getGraphicArray()
	{
		return graphArray;
	}
	
	public int getConnectionStatus(int i, int j)
	{
		return adjArray[i][j];
	}
	
	public void setAdjacencyArray(int[][] adjArray)
	{
		this.adjArray=adjArray;
	}
	
	public int[][] getAdjacencyArray()
	{
		return adjArray;
	}
	
	public int getPSize() {
		return pSize;
	}

	public void setPSize(int size) {
		pSize = size;
	}

	/**
	 * 获得与当前点连接的点集合
	 * @param start_point
	 * @return
	 */
	public double[] getAdjacencyPoints(int start_point) {
		return graphArray[start_point];
	}


}

 

 

Point类

import java.util.ArrayList;
import java.util.List;

public class Point {
	
	private int index;
	
	/**和该点相连的点集*/
	private List<Point> connectedToList;
	
	/**该点属于的点集*/
	private List<Point> belongToList=new ArrayList<Point>();
	

	public Point(int index)
	{
		this.index=index;
		belongToList.add(this);	
	}

	
	public int getIndex() {
		return index;
	}


	public void setIndex(int index) {
		this.index = index;
	}


	public List<Point> getBelongToList() {
		return belongToList;
	}


	public void setBelongToList(List<Point> belongToList) {
		this.belongToList = belongToList;
	}
	

	public void setConnectedToList(List<Point> connectedToList) {
		this.connectedToList = connectedToList;
	}


	public List<Point> getConnectedToList() {
		return connectedToList;
	}

}