图——最小生成树

tuan_liu

2018-05-01

data-structure

由一个图按照某种规则导出的一个树，叫生成树。最小生成树：构成这个生成树的所有分支的权值和最小。

prime算法
求最小生成树的代码：

void Prim(int n ,float MGraph[][n],int v0,float &sum)  //顶点个数，带权图，构造生成树的起始顶点，存储最小权值和（代价）
{
	int lowCost[n],vSet[n];  
	int v,k,min;
	for(int i=0;i<n;++i)
	{
		lowCost[i]=MGraph[v0][i];  //lowCost[]指向vo初始点的同一行的不同列的顶点
		vSet[i]=0;
	}
	v=v0;  //v指向第一个结点，
	vSet[v]=1;  //已经并入，所以标记设置为1
	sum=0;  //初始化
	for(int i=0;i<n-1;++i)
	{
		min=INF; //min初始化为无穷大
		for(int j=0;j<n,++j)
			if(vSet[j]==0&&lowCost[j]<min)
			{
				min=lowCost[j];
				k=j;
			}
			vSet[k]=1;
			v=k;  //v指向如今刚进入的结点
			sum+=min;  //min的值累加到sum
			for(int j=0;j<n;++j)  //更新lowCost数组
				if(vSet[j]==0&&MGraph[v][j]<lowCost[j])
					lowCost[j]=MGraph[v][j];
	}
}

lowCost[]数组是用来存储当前生成树到图中其余顶点的边的最小权值。vSet[i]为1时就说明已经被并入生成树中，为0就没有并入。
v指向刚并入的顶点。

v0是最小生成树的初始结点，所以v=v0

kruskal算法

把当前未被并入的，且并入后不会产生环的最小边进行并入。
如何检测并入后到底会不会产生环呢？就用到了“并查集”。所谓的并查集，就是通过这些图中的点构造出来的树，每一个结点在相连的时候，要一直查到根结点，如果根结点不相同，说明图中选取边之后不会产生环，所以可以选择这个这个结点的边。