图的最小生成树：Prim算法与Kruskal算法（Java实现）

最小生成树：构造连通网的最小代价生成树

有Prim和Kruskal两种算法

Prim算法

基本思想

1. 确定一个顶点集合U和一个边集合TE，确定初始顶点并放入U中，寻找其邻接边中的最小值边，并将这条边放入TE，将连着的另一个顶点也放入U中
2. 将U中的顶点看作一个整体(看作一个顶点)，寻找这个整体邻接边中的最小值边，并将这条边放入TE，将连着的另一个顶点也放入U中
3. 重复上述过程，直到U中存在该图中所有的顶点，TE就是最小生成树的各个边

算法实现
邻接矩阵的实现

	//Prim
	void prim(Graph<?> G)
	{
  
		int[] adjvex = new int[G.getNumOfVertexes()];   //保存相关顶点下标
		int[] lowcost = new int[G.getNumOfVertexes()];  //保存相关边的权值
		
		//将初始顶点加入生成树,这里的初始顶点为第一个顶点
		for(int i = 0; i < G.getNumOfVertexes(); i++)
		{
			lowcost[i] = G.edges[0][i]; //将初始顶点的邻接边的权值存入数组
			adjvex[i] = 0;              //初始化全为初始顶点的下标
		}
		
		//构造最小生成树,有n-1条边所以找n-1次
		for(int i = 0; i < G.getNumOfVertexes() - 1; i++)
		{
			int min = Graph.INFINITY;  //初始化最小权值为∞
			
			int k = 0;                 //用来存储最小权值的顶点下标
			
			//找到最小权值极其相关顶点
			for(int j = 0; j < G.getNumOfVertexes(); j++)
			{
				if(lowcost[j] != 0 && lowcost[j] < min)  //不是自身且有边
				{
					min = lowcost[j];
					k = j;
				}
			}
			//System.out.println(Arrays.toString(adjvex));
			//System.out.println(Arrays.toString(lowcost));
			//打印最小权值边
			System.out.println("("+adjvex[k]+", "+k+")");
			
			lowcost[k] = 0;     //表示此边已使用过
			
			
			//找到k的未被使用过的最小权值边
			for(int j = 0; j < G.getNumOfVertexes(); j++)
			{
				
				if(lowcost[j] != 0 && G.edges[k][j] < lowcost[j])
				{
					lowcost[j] = G.edges[k][j];
					adjvex[j] = k;
				}
			}
		}

	}

算法分析

• 由于嵌套循环的存在，邻接矩阵的实现的算法复杂度为O(n²)

Kruskal算法

基本思想

1. 将图写成边集数组的形式，将各个边按权值从小到大的顺序排列，选取第一个边（权值最小）和它的两个顶点加入最小生成树集合T
2. 选取下一个边，若不构成闭环，就加入T
3. 重复操作2，遍历所有边即可得到最小生成树
4. 构成闭环的判断与不相交集类思想类似，写一个参考数组，一条边的顶点为下标，另一个顶点为值。
   每加入一条边，就要判断该边的两个顶点是否在同一个不相交集中，若是，则构成闭环，舍去该边，不是则加入最小生成树
   算法实现

public static void kruskal(Graph<?> G)
	{
		//获取边集数组
		Edge[] edgesArray = toEdgesArray(G.edges, G.getNumOfEdges());
		
		int[] s = new int[G.getNumOfVertexes()];  //判断边与边是否形成环路的数组（不相交集的思想）
		Arrays.fill(s, 0);
		
		
		//选取边形成最小生成树
		for(int i = 0; i < edgesArray.length; i++)
		{
			//获取第i条边的起始顶点与结尾顶点
			int p1 = find(s, edgesArray[i].begin);
			int p2 = find(s, edgesArray[i].end);
			
			if(p1 != p2)
			{
				s[p1] = p2;//下标是起点，值是终点
				
				System.out.println("("+ edgesArray[i].begin+", "+edgesArray[i].end+", "+edgesArray[i].weight+")");
				
				//System.out.println(Arrays.toString(s));
			}
		}
		
	}
	
	//
	private static int find(int[] s, int x)
	{
		while(s[x] > 0)
			x = s[x];
		return x;
	}
	
	//将邻接矩阵转化为边集数组
	public static Edge[] toEdgesArray(int[][] edges, int numOfEdges)
	{
		Edge[] edgesArray = new Edge[numOfEdges];   //初始化边集数组
		
		int k = 0;
		while(k < edgesArray.length)  //遍历所有边，赋值
			for(int i = 0; i < edges.length; i++)
				for(int j = i + 1; j < edges[i].length; j++)//无向图一条边有两个位置
				{
					if(edges[i][j] != 0 && edges[i][j] < Graph.INFINITY)
						edgesArray[k++] = new Edge(i, j, edges[i][j]);
					
				}
		
		//将边集数组按从小到大排序
		Arrays.sort(edgesArray);		
		
		return edgesArray;
	}
	


}
//边集数组中的元素，实质上是一条边
class Edge implements Comparable<Edge>
{
	public int begin;
	public int end;
	public int weight; 
	Edge(int begin, int end, int weight)
	{
		this.begin = begin;
		this.end = end ;
		this.weight = weight;
	}

	@Override
	public int compareTo(Edge o) 
	{
		if(this.weight == o.weight)
			return 0;
		else if(this.weight < o.weight)
			return -1;
		else
			return 1;
	}

}

算法分析

• 时间复杂度为O(eloge)，e 为边数
• 对于稀疏图，Kruskal算法更好，对于稠密图，Prim算法更好