231.c

对于个顶点的连通网可以建立许多不同的生成树

#include <stdio.h>
 
#include <limits.h>
 
#define INFINITY 0
 
#define MaxEdge 50
 
#define MAX_VERTEX_NUM 10
 
 
typedef struct {     /* 图的定义*/
 
  int vexs[MAX_VERTEX_NUM];      /* 顶点信息*/
 
  int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*以矩阵存储边的信息*/
 
  int vexnum,
 e;   /* 顶点数，弧数 */
 
}Graph;
 
 
typedef struct ENode{ /*以数组存储边的信息*/
 
  int vex1,vex2;
 
  int weight;
 
}ENode;
 
 
Graph G;
 
ENode edgelist[MaxEdge],temp;
 
 
void CreateGraph(Graph G,int a,int b){
 
  int i,j,k;
  int start,end,weight;
 
  k=0;
  G.vexnum=a;  G.e=b;
 
  for(i=0;i<a;i++)
 
    for(j=0;j<b;j++)
 
       G.arcs[i][j]=INFINITY;
 
  for(i=0;i<b;i++){
 
    printf("Intput the arcs and its weight(format:1,3,2):\n");
 
    scanf("%d,%d,%d",&start,&end,&weight);
 
    getchar();
 
    G.arcs[start-1][end-1]=weight;
    G.arcs[end-1][start-1]=weight;
 
  }
 
for(i=0;i<b;i++)  /*将矩阵中边的信息复制到edgelist 中*/
 
    for(j=0;j<=i;j++)
 
     
 if(G.arcs[i][j]){
 
        edgelist[k].weight=G.arcs[i][j];
 
        edgelist[k].vex1=j+1;
        edgelist[k].vex2=i+1;
         k++;
 
      }
 
  for(i=0;i<b;i++) /*按边的权重非递减将边排序*/
 
    for(j=i+1;j<b;j++)
 
      if(edgelist[i].weight>=edgelist[j].weight)
     {
 
        temp=edgelist[i];
        edgelist[i]=edgelist[j];
          edgelist[j]=temp;
     }
 
}
 
 
void Kruskal_MST(ENode edgelist[],int a,int b)
 
{/*用Kruskal算法构造最小生成树*/
 
  int i,j,k,v1,v2,*Vset;
 
  Vset=(int *)malloc(a*sizeof(int));
 
  for(i=0;i<G.vexnum;i++)
 
     Vset[i]=i;
 
  j=0;k=0;
 
  printf("\nThe min tree:");
 
  while(k<a-1&&j<b-1){
 
    v1=edgelist[j].vex1;   v2=edgelist[j].vex2;
 
    if( Vset[v1]!=Vset[v2]){
 
    printf("\n(%d,%d),%d",v1,v2,edgelist[j].weight);
 
    k++;
 
    for(i=0;i<a;i++)
 
      if(Vset[i]==Vset[v2])  Vset[i]=Vset[v1];
 
}
 
    j++;
 
  }
 
  if(k<a-1)
 
      printf("\nError! Can not creat the min tree!");
 
  free(Vset);
 
  return;
 
}
int a,b;
 
void main(){
 
char j='y' ;
  int a,b;
 
clrscr();     /*清屏*/
 
while(j!='N'&&j!='n'){
 
    printf("\nPlease input the numbers of vex:\n");
    printf("(format:3,3):\n");
 
    scanf("%d,%d",&a,&b);
 
       CreateGraph(G,a,b);
 
       Kruskal_MST(edgelist,a,b);
 
       getchar();
 
       printf("\ncontinue(Y/N)?");
 
       scanf("%c",&j);
 
    }
 
}