lliyun.cpp

1． 利用克鲁斯卡尔算法求网的最小生成树 2.以存储边（带权）的数组表示图

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#define ERROR -1
#define MAX 20
#define INF 10000 
//最大值无穷#
typedef struct ArcCell{
int adj;
char *info;
}ArcCell,AdjMatrix[MAX][MAX];
typedef struct {
AdjMatrix edges;
    char vexs[MAX];
	int n,e;
}MGraph;
typedef struct{
 int u;//边的起始顶点
 int v;//边的终止顶点
 int weight;//边的权值
}EdgeType;
 void Check(int n,int&i,int&j)	
{
	while(1){
	 if(i<0||i>n||j<0||j>n)
	  	cout<<"输入有误，请重新输入！"<<endl;
 	 else return ;
	 cin>>i>>j;
	}
}	
 int LocateVex(MGraph G,char v)
 {int i;
 for(i=1;i<=G.n;i++)
 if(G.vexs[i]==v)
	 return i;
 return -1;
 }
void CreatMgraph(MGraph &G)
{int i,j,w,k;
char v1,v2;
 cout<<"请输入无向网的顶点数和边数:";
cin>>G.n>>G.e;
cout<<"输入各顶点信息如下："<<endl;
for(i=1;i<=G.n;i++) cin>>G.vexs[i];
cout<<endl;
//初始化邻接矩阵
 for(i=1;i<=G.n;i++)
for(j=1;j<=G.n;j++)
{	G.edges[i][j].info=NULL;
	if(i==j)	G.edges[i][j].adj=0;
		
	else 	G.edges[i][j].adj=G.edges[i][j].adj=INF;
cout<<G.edges[i][j].adj<<' ';
}
cout<<"依次输入无向网的每条边的起点和终点"<<endl;
cout<<"权值!"<<endl;
for(k=1;k<=G.e;k++)
{cout<<"请输入第"<<k<<"条边的信息：";
 cin>>v1>>v2>>w;
 i=LocateVex(G,v1);j=LocateVex(G,v2);
  	cout<<i;cout<<j;cout<<w;cout<<endl;
 
 G.edges[i][j].adj=w;
 cout<<w;
G.edges[i][j].adj=G.edges[j][i].adj =w;  
}
cout<<endl; 

}
 void DispMat(MGraph G)
 {cout<<"邻接矩阵："<<endl; 
  int i,j,k;
  k=0;
  for(i=1;i<=G.n;i++)
   for(j=1;j<=G.n;j++)
 { cout<<setw(4)<<G.edges[i][j].adj;
  k++;
if(k%4==0) cout<<endl;
  }
 }
void Inssertsort(EdgeType E[],int e)//对E【0...n-1】a按w递增有序进行直接插入排序
{ 
	int i,j;
 EdgeType temp;

 for(i=2;i<=e;i++)
 {  
  temp=E[i];
  j=i-1;
  while(j>=1&&temp.weight<E[j].weight)
  {
   E[j+1]=E[j];  
    j--;
  }
E[j+1]=temp;
}
}
void OutputEdgeSet(MGraph G,EdgeType E[],int e)
{
int i,k=0;
cout<<'{';
for(i=1;i<=e-1;i++)
 
	if(E[i].weight>0){
	k++;

	cout<<'('<<G.vexs[E[i].u]<<','<<G.vexs[E[i].v];
	cout<<','<<E[i].weight<<')'<<',';
	if(k%5==0)cout<<endl;
	}
 	if(e>0&&E[i].weight>0){
     cout<<'('<< G.vexs[E[e].u]<<','<<G.vexs[E[e].v]<<','<<E[e].weight<<')';          
	 cout<<'}'<<endl;
	}
 return;
}

void d(EdgeType E[],MGraph G)
{int m1,m2,s1,s2;
int k;
int i,j;
int vset[MAX];//辅助数组
 
for(i=1;i<=G.n;i++)
{vset[i]=i;//初始化辅助数组
cout<<i<<' ';
}
k=1;
j=1;//E中边的下标，初值为0
while(k<=G.n)
{
m1=E[j].u;
m2=E[j].v;//取一条边的头尾顶点
s1=vset[m1];
s2=vset[m2];//分别得到两个顶点所属的集合编号
if(s1!=s2)
{
cout<<"边：";
cout<<m1<<m2<<E[j].weight<<endl;
k++;
for(i=1;i<=G.n;i++)
if(vset[i]==s2)
vset[i]=s1;
}
else break;
j++;
}
}
void Kruskal(MGraph& G)
{
 EdgeType E[MAX];
int i,j;
int k;
k=1;//将各边次难道E[0...g.e-1]
for(i=1;i<=G.n;i++)
for(j=i+1;j<=G.n;j++)
if(G.edges[i][j].adj!=0&&G.edges[i][j].adj!=10000)
{E[k].u=i;E[k].v=j;E[k].weight=G.edges[i][j].adj;
k++;
}
cout<<"输出邻接矩阵生成图的边集数组:"<<endl;
	OutputEdgeSet(G,E,G.e);
Inssertsort(E,G.e);
 cout<<"!!!";
cout<<"队E数组按w递增排序如下:"<<endl;
OutputEdgeSet(G,E,G.e);
d(E,G);
}
void main()
{ 
	MGraph  G ; 
	CreatMgraph(G);
	DispMat(G);
  cout<<"用Cruskal构造最小生成树"<<endl;
   Kruskal(G);
}