最小生成树.cpp

算法分析中的贪心算法的实现

/*
最小生成树性质：
设G=(V,E)是一个连通带权图，U是V的一个真子集。如果(u,v)属于E，且u属于U,
v属于V-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵
最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。

证明：
假设G的任何一棵最小生成树都不含边(u,v)。将边(u,v)添加到G的一棵最小生成树
T上，将产生一个含有边(u,v)的圈，并且在这个圈上有一条不同于(u,v)的边(u',v'),
使得u'属于U,v'属于V-U。
将边(u',v')删去，得到G的另一棵生成树T'。由于c[u][v]<=c[u'][v']，所以T'的
耗费<=T的耗费。于是T'是一棵含有边(u,v)的最小生成树，这与假设矛盾。
*/

/*
设G=(V,E)是一个连通带权图，V={1,2,...,n}
*/
/*
Prim算法的思想是：
首先设置S={1},然后，只要S是V的真子集,就做如下贪心选择：
选取满足条件i属于S，j属于V-S，且c[i][j]最小的边，逼供内将顶点j添加到S中。
这个过程一直进行到S=V时候为止。在这个过程中选取到的所有边恰好构成C的一棵
最小生成树。
*/
/*
设置两个数组closest和lowcost。对于每一个j属于V-S，closest[j]是j在S中的一个
邻接点，它与j在S中的其他邻接顶点k相比较有c[j][closest[j]]<=c[j][k]。
lowcost[j]的值就是c[j][closest[j]]。
*/
template< class Type >
void Prim( int n, Type **c )
{
	Type lowcost[maxint];
	int closest[maxint];
	bool s[maxint];

	s[1] = true;
	for( int i = 2; i <= n; ++i )
	{
		lowcost[i] = c[1][i];
		closest[i] = 1;
		s[i] = false;
	}

	for( int i = 1; i < n; ++i )
	{
		Type min = inf;
		int j = 1;
		for( int k = 2; k <= n; ++k )
		{
			if ( (lowcost[k] < min) && (!s[k]) )
			{
				min = lowcost[k];
				j = k;
			}
		}
		cout<<j<<' '<<closest[j]<<endl;
		s[j] = true;
		for( int k = 2; k <= n; ++k )
		{
			if ( (c[j][k] < lowcost[k]) && (!s[k]) )
			{
				lowcost[k] = c[j][k];
				closest[k] = j;
			}
		}
	}
}

/*
Kruskal算法
算法的基本思想是：
首先将G的n个顶点看成n个孤立的连通分支，将所有的边权从小到大排序。
然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接
两个不同的连通分支：
（1）当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和
T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第K+1条边；
（2）如果v和w在当前的同一个连通分支中，就直接查看第k+1条边。这个过程一直进行
到只剩下一个连通分支时为止。
此时这个连通分支就是G的一棵最小生成树

另外，在kruskal算法中，还要对一个由连通分支组成的集合不断进行修改。将这个由连通
分支组成的集合记为U，则需要用到的集合的基本运算有：
（1）Union(a,b)：将U中两个连通分支a和b连接起来，所得结果称为A或B。
（2）Find(v)：返回U中包含顶点v的连通分支的名字。这个运算用来确定某条边的
两个端点所属的连通分支。
*/

template< class Type >
class EdgeNode
{
	friend ostream& operator<<( ostream&, EdgeNode< Type > );
	friend bool Kruskal( int, int, EdgeNode< Type > *, EdgeNode< Type > * );
	friend void main(void);
	public:
		operator Type() const
		{
			return weight;
		}
	private:
		Type weight;
		int u,v;
};

template< class Type >
bool Kruskal( int n, int e, EdgeNode< Type > E[], EdgeNode< Type > t[] )
{
	MinHeap< EdgeNode< Type > > H(1);
	H.Initialize(E,e,e);

	UnionFind U(n);
	int k = 0;
	while( e && k < n - 1 )
	{
		EdgeNode< int > x;
		H.DeleteMin(x);
		e--;
		int a = U.Find(x,u);
		int b = U.find(x,v);
		if ( a != b )
		{
			t[k++] = x;
			U.Union(a,b);
		}

		H.Deactivate();
		return ( k == n - 1 );
	}
}

int main()
{
	return 0;
}