12.cpp

1.显示该图的邻接矩阵 2.输出最小生成树的所有边及权值和

#include <iostream>
using namespace std; 
#define int_max 10000
#define inf 9999 
#define max 20

//------------------------------------邻接矩阵定义--------------------------
typedef struct ArcCell
{	int adj;
	char *info;
}ArcCell,AdjMatrix[20][20];

typedef struct 
{	char vexs[20];
	AdjMatrix arcs;
	int vexnum,arcnum;
}MGraph_L;

//-------------------------------确定顶点在图中的位置-----------------------
int localvex(MGraph_L G,char v)
{	int i=0;
	while(G.vexs[i]!=v)
		++i;
	return i;
}

//-------------------------------创建图用邻接矩阵表示-----------------------
int creatMGraph_L(MGraph_L &G)
{	char v1,v2;
	int i,j,w;
	cout<<"请输入图G顶点数和边数:"<<endl;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i!=G.vexnum;++i)
	{	cout<<"请输入第"<<i+1<<"个顶点: ";
		cin>>G.vexs[i];
	}
	for(i=0;i!=G.vexnum;++i)
		for(j=0;j!=G.vexnum;++j)
		{	 G.arcs[i][j].adj=int_max;
			 G.arcs[i][j].info=NULL;
		}
	for(int k=0;k!=G.arcnum;++k)
	{	cout<<"请输入一条边依附的顶点和权值:"<<endl;
		cin>>v1>>v2>>w;            //输入一条边依附的两点及权值
		i=localvex(G,v1);          //确定顶点V1和V2在图中的位置
		j=localvex(G,v2);
		G.arcs[i][j].adj=w;
		G.arcs[j][i].adj=w;
	}
	cout<<"图G邻接矩阵创建成功！"<<endl;
	return G.vexnum;
}

//---------------------------------输出邻接矩阵-----------------------------
void ljjzprint(MGraph_L G)
{	int i,j;
	for(i=0;i!=G.vexnum;++i)
	{	for(j=0;j!=G.vexnum;++j)
			cout<<G.arcs[i][j].adj<<"	";
		cout<<endl;
	}
}




//------------------------------最小生成树普里姆算法-----------------------
typedef struct 
 {	int adjvex;
	int lowcost;
 }closedge;
void prim(int g[][max],int n,char s[])
{	int lowcost[max],prevex[max]; //lowcost[]存储当前集合U分别到剩余结点的最短路径
								  //prevex[]存储最短路径在U中的结点
	int i,j,k,min,add;
	add=0;
	for(i=2;i<=n;i++)                 //n个顶点，n-1条边 
	{	lowcost[i]=g[1][i];           //初始化 
		prevex[i]=1;                  //顶点未加入到最小生成树中 
	} 
	lowcost[1]=0;                     //标志顶点1加入U集合
	cout<<"最小生成树的所有边为:"<<endl;
	for(i=2;i<=n;i++)                 //形成n-1条边的生成树 
	{	min=inf; 
		k=0; 
		for(j=2;j<=n;j++)             //寻找满足边的一个顶点在U,另一个顶点在V的最小边 
			if((lowcost[j]<min)&&(lowcost[j]!=0)) 
			{    min=lowcost[j]; 
				 k=j; 
			} add+=min;
		cout<<"("<<s[prevex[k]-1]<<","<<s[k-1]<<")"<<endl; 
		lowcost[k]=0;                           //顶点k加入U 
		for(j=2;j<=n;j++)                       //修改由顶点k到其他顶点边的权值 
			if(g[k][j]<lowcost[j]) 
			{    lowcost[j]=g[k][j]; 
				 prevex[j]=k; 
			}  
	}  
	cout<<"最小生成树所有边的权值和为:"<<add<<endl;
} 




void main()
{	MGraph_L G;
	int i,d,g[20][20];
	d=creatMGraph_L(G);
	cout<<endl;
    cout<<"----------------------------------------------------------------"<<endl;
    cout<<"请选择操作:"<<endl;
    cout<<"         1.显示该图的邻接矩阵"<<endl;
    cout<<"         2.输出最小生成树的所有边及权值和"<<endl;
    cout<<"         3.结束本程序"<<endl; 
	cout<<"----------------------------------------------------------------"<<endl;
	int j=1;
    int x;
	cout<<"请选择操作:"<<endl;
    cin>>x;
   	while(j!=0)
    {switch(x)
        {case 1:
            cout<<"邻接矩阵显示如下："<<endl;
			ljjzprint(G);
			cout<<"请选择操作:"<<endl;
			cin>>x;
			j=1;
			break;
		 case 2:
            for(i=0;i!=G.vexnum;++i)
				for(int j=0;j!=G.vexnum;++j)
					g[i+1][j+1]=G.arcs[i][j].adj;
			prim(g,d,G.vexs);
			cout<<"请选择操作:"<<endl;
			cin>>x;
			j=1;
			break;
         case 3:
			cout<<"欢迎使用!"<<endl;
			j=0;
            break;
         default:
            cout<<"输入有误,重新输入"<<endl;
			cout<<"请选择操作:"<<endl;
			cin>>x;
			j=1;
			break;
        }
	} 
}