#include<iostream.h>
const int n=6;              //定義網(wǎng)中頂點(diǎn)數(shù)
const int e=10;             //定義網(wǎng)中邊數(shù)
typedef struct edgeset      //定義生成樹
{
	int fromvex;            //邊的起點(diǎn)
	int endvex;             //邊的終點(diǎn)
	int weight;             //邊上的權(quán)值
}edgeset;
typedef struct tree                 //定義生成樹
{
	edgeset c[n];           //存放生成樹邊
	edgeset ge[e+1];        //存放網(wǎng)中所有邊
	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;                 //統(tǒng)計(jì)生成樹的邊數(shù)
	int d=1;                 //表示待處理邊的下標(biāo)位置
	int m1,m2;               //一條邊的兩個(gè)頂點(diǎn)
	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<<"請按邊上權(quán)值從小到大輸入邊的起點(diǎn)號(hào),邊的終點(diǎn)號(hào),邊上的權(quán)值,共10條邊"<<endl;
	for(int i=1;i<=e;i++)
	{
		cout<<"請輸入第"<<i<<"條邊的具體情況"<<endl;
		cout<<"第"<<i<<"條邊的起點(diǎn)為:"<<'\t';
		cin>>t.ge[i].fromvex;
		cout<<"第"<<i<<"條邊的終點(diǎn)為:"<<'\t';
		cin>>t.ge[i].endvex;
		cout<<"第"<<i<<"條邊的權(quán)值為:"<<'\t';
		cin>>t.ge[i].weight;
	}
	kruska(t);
	cout<<"最小生成樹起點(diǎn)終點(diǎn)和權(quán)值為:"<<endl;
	for(i=1;i<n;i++)
	{
		cout<<t.c[i].fromvex<<" ";
		cout<<t.c[i].endvex<<" ";
		cout<<t.c[i].weight<<endl;
	}
}