l7_8.cpp

来自「《数据结构（C++描述）》-李根强-源代码」· C++ 代码 · 共 61 行

//用克鲁斯卡尔算法求无向网的最小生成树
#include <iostream.h>
const int n=6;
const int e=10;
 struct edgeset
{	int fromvex;
	int endvex;
	int weight;
};
edgeset c[n],ge[e+1];
void kruska(edgeset ge[e+1])    
{
	int i,j;
	int s[n+1][n+1];
	for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
		if(i==j) s[i][j]=1;
		else 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((ge[d].fromvex==j)&&(s[i][j]==1))
           m1=i;
           if((ge[d].endvex==j)&&(s[i][j]==1))
           m2=i;
		 }                                        
	if(m1!=m2)
	{
	  c[k]=ge[d];
	  k++;
	  for(j=1;j<=n;j++)
	  {
		s[m1][j]=s[m1][j]||s[m2][j];
		s[m2][j]=0;
	  }
	}                                        
	d++;
	}
}

void main()
{ 
  for(int i=1;i<=e;i++)
  { cout<<"按从小到大的顺序输入第"<<i<<"条树边及权值"<<endl;
	  cin>>ge[i].fromvex;
    cin>>ge[i].endvex;       
	cin>>ge[i].weight;
  }
  kruska(ge);  
  cout<<"最小生成树的边为:"<<endl;
  for( i=1;i<n;i++)
  { cout<<c[i].fromvex<<"  ";
    cout<<c[i].endvex<<"  ";
	cout<<c[i].weight<<endl;
  }
}