最小生成树总结

最近在学习算法，在学习最小生成树的过程中，感觉算法思想很简单，但实现起来对于我这样的菜鸟来说有些困难，后来上网搜了一些文章，发现这篇讲得很清楚，与大家分享一下http://blog.csdn.net/fengchaokobe/article/details/7521780。我着重研究了一下克鲁斯卡尔算法。

克鲁斯卡尔算法


克鲁斯卡尔算法的思想如下：

克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。

       克鲁斯卡尔算法的执行步骤：
       第一步：在带权连通图中，将边的权值排序；
       第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。
       第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。

在一条新边加入时，要判断是否形成环路（其实前两条边不用判断，大家明白的哈），那么该如何判断呢？

1.如果没有形成回路，那么直接将其连通。此时，对于边的集合又要做一次判断：这两个点是否在已找到点的集合中出现过？
          ①.如果两个点都没有出现过，那么将这两个点都加入已找到点的集合中；
          ②.如果其中一个点在集合中出现过，那么将另一个没有出现过的点加入到集合中；
          ③.如果这两个点都出现过，则不用加入到集合中。
      2.如果形成回路，不符合要求，直接进行下一次操作。

 通过生成的过程可以看出，能否得到最小生成树的核心问题就是上面所描述的判断法则。那么，我们如何用算法来描述判断法则呢？我认为只需要三个步骤即可：
      ⒈将某次操作选择的边XY的两个顶点X和Y和已找到点的集合作比较，如果
             ①.这两个点都在已找到点的集合中，那么return 2；
             ②.这两个点有一个在已找到点的集合中，那么return 1；
             ③这两个点都不在一找到点的集合中，那么return 0；
      ⒉当返回值为0或1时，可判定不会形成回路；
      ⒊当返回值为2时，判定能形成回路的依据是：假如能形成回路，设能形成回路的点的集合中有A,B,C,D四个点，那么以点A为起始点，绕环路一周后必能回到点A。如果能回到，则形成回路；如果不能，则不能形成回路。

具体的流程在我给出的链接中英讲得很好了，在这里我就不赘述了。

在判断是否出现环路时，我采用了如下方法：

转自http://blog.csdn.net/lyflower/archive/2008/03/01/2137710.aspx。   
如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。  
n算法：  
     第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。  
     第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。  
     如果最后还有未删除顶点，则存在环，否则没有环。  
n算法分析：  
     由于有m条边，n个顶点。如果m>=n，则根据图论知识可直接判断存在环路。  
    （证明：如果没有环路，则该图必然是k棵树 k>=1。根据树的性质，边的数目m = n-k。k>=1，所以：m<n）  
     如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。这两种操作的总数不会超过m+n。由于m<n，所以算法复杂度为O(n)   

（这种判断环路的方法很简单吧）

下面我贴出我的代码，希望大牛们不要喷我，我只是实现了找出最小生成树的功能，具体效率方面没有考虑（ps:只针对于无向图）

import java.util.Scanner;
//存储边，及边的结点
class dataType{
	int value;
	String startNode;
	String endNode;
}
//存储结点，flag用于标记结点是否已经加入到最小生成树中
class dataType1{
	String node;
	int flag;
}
public class KruskalAlgorithm {
	//对边进行排序
	static void sort(dataType[] arr,int n)
	{
		int temp;
		String temp1;
		
		for(int i=0;i<n;i++)
		{
			int flag=0;
			for(int j = 0;j<n-i-1;j++)
			{
				if(arr[j].value>arr[j+1].value)
				{
					temp = arr[j].value;
					arr[j].value = arr[j+1].value;
					arr[j+1].value = temp;
					temp1=arr[j].startNode;
					arr[j].startNode=arr[j+1].startNode;
					arr[j+1].startNode=temp1;
					temp1=arr[j].endNode;
					arr[j].endNode=arr[j+1].endNode;
					arr[j+1].endNode=temp1;
					flag++;
				}
			}
			if(flag==0)
				break;
		}
		
	}

	//判断能否出现回路
	static int isLoop(dataType1 arr1[],int num, int edgeNum)
	{
		int nodeFlag=0;
		for(int i=0;i<num;i++)
		{
			if(arr1[i].flag==1)
			{
				nodeFlag++;
			}
		}
		if(nodeFlag>(edgeNum+1))
			return 0;
		else
			return 1;
	}
	//判断选择的一条边中有几个顶点已经出现过
	static int isEmerge(String startNode,String endNode,dataType1[] arr1,int num)
	{
		int loop = 0;
		for(int i = 0;i<num;i++)
		{
			if(arr1[i].node.compareTo(startNode)==0)
			{
				if(arr1[i].flag==1)
				{
					loop++;
				}
				else
				{
					arr1[i].flag=1;
				}
			}
			if(arr1[i].node.compareTo(endNode)==0)
			{
				if(arr1[i].flag==1)
				{
					loop++;
				}
				else
				{
					arr1[i].flag=1;
				}
			}
		}
		/*for(int i=0;i<num;i++)
		{
			System.out.print("("+arr1[i].node+","+arr1[i].flag+")  ");
		}
		System.out.println();*/
		return loop;
	}
	
	public static void main(String[] args) {
		int sum=0;
		int edgeNum = 0;
		System.out.print("请输入图中边的条数：");
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		System.out.print("请输入图中点的个数：");
		int num = input.nextInt();
		dataType1[] arr1 = new dataType1[num];
		System.out.print("请输入图中的点：");
		for(int j = 0;j<num;j++)
		{
			arr1[j] = new dataType1();
			arr1[j].node=input.next();
			arr1[j].flag = 0;
		}
		int i=0;
		int j;
		dataType[] arr = new dataType[n];
		while(true)
		{
			if(i<n)
			{
				System.out.print("请输入边的长度，以及边的两个顶点");
				arr[i] = new dataType();
				j = input.nextInt();
				if(j==0)
				{
					break;
				}else
				{
					arr[i].value = j;
					arr[i].startNode = input.next();
					arr[i].endNode = input.next();
					i++;
				}
			}
			else
			{
				break;
			}
		}
		System.out.println("开始对边进行排序：");
		sort(arr,n);
		System.out.println("完成排序：");
		for(i = 0;i<n;i++)
		{
			System.out.print("("+arr[i].value+","+arr[i].startNode+","+arr[i].endNode+")  ");
		}
		System.out.println();
		for(int k =0;k<n;k++)
		{
			if(edgeNum<num)
			{
				if(k<2)//加入的第一条边、第二条边不用判断是否形成环路
				{
					int loop = isEmerge(arr[k].startNode,arr[k].endNode,arr1,num);//将边的结点加入到已选集合
					sum=sum+arr[k].value;
					edgeNum++;
					System.out.print("("+arr[k].startNode+","+arr[k].endNode+")  ");
				}else{
					int loop = isEmerge(arr[k].startNode,arr[k].endNode,arr1,num);
					if(loop==0)
					{
						sum = sum+arr[k].value;
						edgeNum++;
						System.out.print("("+arr[k].startNode+","+arr[k].endNode+")  ");
					}
					if(loop==1)
					{
						sum = sum+arr[k].value;
						edgeNum++;
						System.out.print("("+arr[k].startNode+","+arr[k].endNode+")  ");
					}
					if(loop==2)
					{
						if(isLoop(arr1,num,edgeNum)==0)
						{
							sum = sum+arr[k].value;
							edgeNum++;
							System.out.print("("+arr[k].startNode+","+arr[k].endNode+")  ");
						}
					}
				}
			}else
			{
				break;
			}
		}
		System.out.print("最小生成树的长度为："+sum);
		
	}

}