图的最小生成树.cpp

数据结构常用算法：图的最小生成树 经典算法：图的最小生成树

#define INFINITY INT_MAX
#define MN 20
#include <limits.h>
#include<iostream.h>

typedef char VertexType;
typedef int Edgetype;
typedef struct {
	VertexType vexs[MN];
	Edgetype edges[MN][MN];
	int n,a;
}MGraph;
typedef struct {
	int fromvex,tovex;
	int cost;
}MST[MN-1];
MGraph CreatMGraph()
{
    /*邻接矩阵法创建图*/
	MGraph G;
	int i,j,k,c;
	cout<<"请输入顶点数目，弧边数目："<<endl;
	cin>>G.n>>G.a;
	
	cout<<"请输入顶点信息："<<endl;
	for(i=0;i<G.n;i++)   /*取顶点信息*/
		cin>>G.vexs[i];
	for(i=0;i<G.n;i++)
           for(j=0;j<G.n;j++)    /*初始化各边权值为无穷*/
			G.edges[i][j]=INFINITY;
    cout<<"请输入弧边信息：注意顶点序号从0开始!!!"<<endl;
    for(k=0;k<G.a;k++)    /*取弧边信息*/
	{
		cout<<"第"<<k+1<<"条边的两个端点序号,权值:"<<endl;
		cin>>i>>j>>c;
		G.edges[i][j]=c;
		G.edges[j][i]=c;
	}
	return G;
}
MST T;    /*定义T为全局变量*/   
void InitcandidataSet(MGraph G,int r)
{    /*初始化绿边*/   
	int i,k=0;     /*i为蓝点序号*/
	for(i=0;i<G.n;i++)
		if(i!=r){
			T[k].fromvex=r;
			T[k].tovex=i;
			T[k].cost=G.edges[r][i];
			k++;
		}
}
Edgetype Selectlightedge(MGraph G,int k)
{      /*选择轻边函数*/
       /*k为当前红边的数目，则T{0....k-1}放红边，T{k.....n-2}放绿边。*/
	int min=INFINITY,minpos,i;    /*minpos放轻边序号*/
	for(i=k;i<G.n-1;i++)        /*选择最小权值边*/
		if(T[i].cost<min){
			min=T[i].cost;
			minpos=i;
		}
	if(min==INFINITY)    /*如果最小权值为无穷说明图为非连通图*/
		cout<<"错误!!!"<<endl;
	return minpos;
}
void ModifycondidateSet(MGraph G,int k,int v)
{    /*调整绿边函数*/ 
     /*V为新加边的红点序号，K为红边数，d为新的绿边权值*/
        int d,i;
	for(i=k;i<G.n-1;i++)
	{
		d=G.edges[v][T[i].tovex];
		if(d<T[i].cost)     /*如果新的绿边权值小，替换原绿边*/
		{
			T[i].cost=d;
			T[i].fromvex=v;
		}
	}
}
void PrimMST(MGraph G,int r)
{     /*普里姆函数*/
	int v,k;
        Edgetype m;
	InitcandidataSet(G,r);   /*调用初始化绿边函数*/
	for(k=0;k<G.n-1;k++)
	{
		m=Selectlightedge(G,k);    /*m为最轻边序号*/
		T[MN-1]=T[m];
		T[m]=T[k];
		T[k]=T[MN-1];    /*加入红边*/
		v=T[k].tovex;
		ModifycondidateSet(G,k+1,v);   /*调用调整绿边函数*/
	}
}
void main(){
	MGraph G;
	int r,i;
    cout<<"输入数据时，中间均以空格间隔!!!"<<endl;
	G=CreatMGraph();     /*创建图*/
	cout<<"从第几个顶点开始:"<<endl;
	cin>>r;      /*输入开始顶点*/
        PrimMST(G,r);    /*调用普里姆函数*/
        cout<<"最小生成树："<<endl;
	for(i=0;i<G.n-1;i++)    /*输出最小生成树*/
		cout<<G.vexs[T[i].fromvex]<<"->"<<G.vexs[T[i].tovex]<<"  权值"<<T[i].cost<<endl;
}