minispantree_prim.cpp

c语言数据结构源代码（全）相当经典

//MiniSpanTree_Prim.cpp
//Prim算法构造最小生成树
# include <iostream.h>
# include <malloc.h>
# include <conio.h>
# include <stdio.h>

# define INFINITY 1000
# define MAX_VERTEX_NUM 20
# define OK 1
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef int EType;
typedef int InfoType;
typedef int VertexType;
typedef int VRType;
typedef int lowcost;

typedef struct			//define Closedege structure
{   VertexType adjvex;	//存储该边依附的在U中的顶点
    VRType    lowcost;	//存储该边上的权
}Closedge;

typedef struct ArcCell	//define MGraph structure
{  EType adj;
   InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{  VertexType vexs[MAX_VERTEX_NUM];
   AdjMatrix  arcs;
   int vexnum,arcnum;
   GraphKind kind;
}MGraph;

int LocateVex(MGraph G,int v)	//确定v在G中的位置
{
	return(v);
}

int CreatUDN(MGraph &G)		//CreatUDN() 子函数
{  int i,j,k,v1,v2,w;
   int IncInfo;
   cout<<endl<<"Please input the number of G.vexnum 顶点数目 (eg, 4): ";
   cin>>G.vexnum;			//输入顶点数目
   cout<<"Please input the number of G.arcnum 弧的数目 (eg, 4): ";
   cin>>G.arcnum;			//输入弧的数目
   //cout<<"Please input IncInfo 弧的信息 (0 for none)                  : ";
   printf("Please input IncInfo 弧的信息 (0 for none)          : ");
   //cin>>IncInfo;			//输入弧的信息
   scanf("%d",&IncInfo);
   for(i=1;i<=G.vexnum;++i)
     for(j=1;j<=G.vexnum;++j)
       {  G.arcs[i][j].adj=INFINITY;	//初始化邻接矩阵
		  G.arcs[i][j].info=NULL;
       }
   cout<<"Plese input 弧 arc(V1-->V2), For example: arc(1,3),arc(2,4)..."<<endl;
   for(k=0;k<G.arcnum;++k)	//构造邻接矩阵
   {   cout<<endl<<"Please input the "<<k+1<<"th arc's v1 弧头 [1.."<<G.vexnum<<"] :";
       cin>>v1;				//输入弧头
       cout<<"Please input the "<<k+1<<"th arc's v2 弧尾 [1.."<<G.vexnum<<"] :";
       cin>>v2;				//输入弧尾
       cout<<"Please input the "<<k+1<<"th arc's weight 权      :";
       cin>>w;				//输入权
	   i=LocateVex(G,v1);	//确定v1在G中的位置
       j=LocateVex(G,v2);	//确定v2在G中的位置
       while(i<1||i>G.vexnum||j<1||j>G.vexnum)	//如果弧头或弧尾不合法,重新输入
       {	cout<<"Please input Again the "<<k+1<<"th arc's v1 弧头[1.."<<G.vexnum<<"] :";
			cin>>v1;
			cout<<"Please input Again the"<<k+1<<"th arc's v2 弧尾[11.."<<G.vexnum<<"] :";
			cin>>v2;
			cout<<"Please input Again the "<<k+1<<"th arc's weight 权      :";
			cin>>w;
			i=LocateVex(G,v1);	//确定v1在G中的位置
			j=LocateVex(G,v2);	//确定v2在G中的位置
       } //while end
       G.arcs[i][j].adj=G.arcs[j][i].adj=w;			//weight
	   if(IncInfo!=0)
		   {	G.arcs[i][j].info=&IncInfo;
			//printf("%d",*G.arcs[i][j].info);
		}
   } //for end
   return (OK);
} //CreatUDN() end

void ShowMGraph(MGraph G)	//输出图 G
{	int i,j;
	for(i=1;i<=G.vexnum;++i)
		for(j=1;j<=G.vexnum;++j)
			if(G.arcs[i][j].adj!=INFINITY)
				printf("\narc(%d,%d) weight=%d  ",i,j,G.arcs[i][j].adj);
}

int Minimum(Closedge closedge[MAX_VERTEX_NUM],int Vexnum)	//Minimum() sub-function
{   int min,j;                        //return min (closedge[min].lowcost)
    for(min=1; min<=Vexnum && closedge[min].lowcost==0; min++) ;
    for(j=min;j<=Vexnum;++j)
      if(closedge[j].lowcost<closedge[min].lowcost && closedge[j].lowcost>0)
			min=j;				
    return (min);		//返回MIN[closedge[min].lowcost]
} //Minimim() end

int LocatedVex(MGraph G,VertexType u)	//LocatedVex() 子函数
{  return (u);
}

void MiniSpanTree_Prim(MGraph G,VertexType u)	//MiniSpanTree_Prim() 子函数
//用普里姆(Prim)算法从第u个顶点出发构造网G的最小生成树T
//并输出T的各条边.G采用邻接矩阵存储结构
{  int k,j,i,Vexnum=G.vexnum;
   k=LocatedVex(G,u);		//确定顶点u在图G中的位置
   Closedge closedge[MAX_VERTEX_NUM];
   for(j=1;j<=G.vexnum;++j)	//辅助数组初始化
     if(j!=k)
     {	closedge[j].adjvex=u;  	// (u,j)
		closedge[j].lowcost=G.arcs[k][j].adj;
     }
   closedge[k].lowcost=0;	//初始,U={u},closedge[k].lowcost=0表示顶点k并入U
   for(i=2;i<=G.vexnum;++i)
   {  k=Minimum(closedge,Vexnum);	//求出T的下一个结点:第 k 顶点
      //此时 closedge[k].lowcost=MIN{closedge[vi].lowcost|closedge[vi].lowcost>0,vi∈V-U}
      cout<<endl<<"Arc("<<closedge[k].adjvex<<","<<k<<")";
      cout<<"="<<G.arcs[closedge[k].adjvex][k].adj;
      closedge[k].lowcost=0;	//U include k
      for(j=1;j<=G.vexnum;++j)   //renew closedge[k]
	  if(G.arcs[k][j].adj<closedge[j].lowcost)
	   {  closedge[j].adjvex=k;
	      closedge[j].lowcost=G.arcs[k][j].adj;
	   } //if end
   } //for end
} //Minimun() end

void main()  				//main() function
{   MGraph G;
    VertexType u=1;
    cout<<endl<<endl<<"MiniSpanTree_Prim.cpp";
    cout<<endl<<"====================="<<endl;
    if(CreatUDN(G))			//构造图G
	{	printf("\nCreate MGraph success !");
		ShowMGraph(G);		//显示图G
	}
	cout<<endl<<endl<<"The MiniSpanTree_Prim is created as follow order:";
    MiniSpanTree_Prim(G,u);	//调用 MiniSpanTree_Prim() function
    cout<<endl<<endl<<"...OK!...";
    getch();
} //main() end