kruska.cpp

里面有一自已设计的AOE和Kruska的算法,已通过运行,大家可以看看.

#include<iostream.h>
const int n=6;              //定义网中顶点数
const int e=10;             //定义网中边数
typedef struct edgeset      //定义生成树
{
	int fromvex;            //边的起点
	int endvex;             //边的终点
	int weight;             //边上的权值
}edgeset;
typedef struct tree                 //定义生成树
{
	edgeset c[n];           //存放生成树边
	edgeset ge[e+1];        //存放网中所有边
	int s[n+1][n+1];
}tree;
void kruska(tree &t)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j)t.s[i][j]=1;
			else t.s[i][j]=0;
		}
	}
	int k=1;                 //统计生成树的边数
	int d=1;                 //表示待处理边的下标位置
	int m1,m2;               //一条边的两个顶点
	while(k<n)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if((t.ge[d].fromvex==j)&&(t.s[i][j]==1))m1=i;
				if((t.ge[d].endvex==j)&&(t.s[i][j]==1))m2=i;
			}
		}
	if(m1!=m2)
	{
		t.c[k]=t.ge[d];
		k++;
		for(j=1;j<=n;j++)
		{
			t.s[m1][j]=t.s[m1][j]||t.s[m2][j];
			t.s[m2][j]=0;
		}
	}
	d++;
	}
}
void main()
{
	tree t;
	cout<<"请按边上权值从小到大输入边的起点号,边的终点号,边上的权值,共10条边"<<endl;
	for(int i=1;i<=e;i++)
	{
		cout<<"请输入第"<<i<<"条边的具体情况"<<endl;
		cout<<"第"<<i<<"条边的起点为:"<<'\t';
		cin>>t.ge[i].fromvex;
		cout<<"第"<<i<<"条边的终点为:"<<'\t';
		cin>>t.ge[i].endvex;
		cout<<"第"<<i<<"条边的权值为:"<<'\t';
		cin>>t.ge[i].weight;
	}
	kruska(t);
	cout<<"最小生成树起点终点和权值为:"<<endl;
	for(i=1;i<n;i++)
	{
		cout<<t.c[i].fromvex<<" ";
		cout<<t.c[i].endvex<<" ";
		cout<<t.c[i].weight<<endl;
	}
}