l7_7.cpp

数据结构课程的源代码

//用普里姆算法求无向网的最小生成树
#include <iostream.h>
const int n=6;            //定义网中顶点数
const int e=10;           //定义网中边数
 struct edgeset           //定义一条生成树的边
{	int fromvex;     //边的起点
	int endvex;      //边的终点
	int weight;      //边上的权值
};
 int s[n+1][n+1];         //网的邻接矩阵
edgeset ct[n+1];    //最小生成树的边集
void prim(edgeset ct[n+1])    
{
	int i,j,k,min,t,m,w;
		for(i=1;i<n;i++) //从顶点1出发求最小生成的树边
	{ ct[i].fromvex=1;
	  ct[i].endvex=i+1;
	  ct[i].weight=s[1][i+1];
	}
    
		for(k=2;k<=n;k++)
		{
			min=32767;
			m=k-1;
	 	  for(j=k-1;j<n;j++)    //找权值最小的树边
	       if(ct[j].weight<min)
		   {min=ct[j].weight;
		    m=j;
		   }
			edgeset temp=ct[k-1];
			ct[k-1]=ct[m];
			ct[m]=temp;
			j=ct[k-1].endvex;
			for(i=k;i<n;i++)     //重新修改树边的距离
			{ t=ct[i].endvex;
			w=s[j][t];
			if(w<ct[i].weight)//原来的边用权值较小的边取代
			{ct[i].weight=w;
			 ct[i].fromvex=j;
			}
			}
		   }
		}

void main()
{ int j,w;
  for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
		  if(i==j) s[i][j]=0;
		  else s[i][j]=32767;//若（i,j)边上无权值，用32767来代替
for(int k=1;k<=e;k++)   //建立网的邻接矩阵
{ cout<<"请输入一条边及边上的权值";
  cin>>i>>j>>w;
  cout<<endl;
  s[i][j]=w;
  s[j][i]=w;
}

prim(ct);//用普里姆算法求最小生成树
  for(i=1;i<n;i++)//输出n-1条生成树的边
  { cout<<ct[i].fromvex<<"  ";
    cout<<ct[i].endvex<<"  ";       
	cout<<ct[i].weight<<endl;;
  }
}