//给出kruskal球联通网络的最小生成树的算法实现
//调试成功
#include<iostream>
#include<stack>
using namespace std;
int main()
{
stack<int> travstack;
int i,j,k,n=5;
cout<<"以矩阵形式表示"<<endl;
int a[5][5],b[5][5],c[5][5],d[5];
cout<<"请输入各路径权值";
for( i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
cout<<"a[i][j]="<<endl;
cin>>a[i][j];
}
int biggest=0,big=1000;
for(k=0;k<n*n-n;k++)
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i][j]>biggest&&a[i][j]<big)
{
biggest=a[i][j];
travstack.push(i);
travstack.push(j);
}
big=a[i][j];
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
int p1,p2;
p1=travstack.top();//p1=j
travstack.pop();
p2=travstack.top();//p2=i
travstack.pop();
if(b[p1][p2]==0)
{
b[p1][p2]=1;
b[p2][p1]=1;
c[p2][p1]=a[p2][p1];
if(d[p1]==0&&d[p2]==0)
d[p1]=d[p2]=1;
else if(d[p1]==0)
{
d[p1]=1;
for( i=0;i<n;i++)
{
if(b[p2][i]==1)
{
b[p1][i]=1;
b[i][p1]=1;
}
}
}
else if(d[p2]==0)
{
d[p2]=1;
for(i=0;i<n;i++)
{
if(b[p1][i]==1)
{
b[p2][i]=1;
b[i][p2]=1;
}
}
}
}
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
cout<<"c[i][j]="<<c[i][j];
cout<<endl;
for(int k=0;k<n;k++)
cout<<"*";
}
return 0;
}