prim.txt

用C语言编写的 如果以无向网表示n个城市之间的交通网络建设规划

如果以无向网表示n个城市之间的交通网络建设规划，顶点表示城市，边上的权表示该线路的造价，试设计一个方案，使这个交通网的总造价最小。 

# include<stdio.h> 
# include<stdlib.h> 
# define maxlen 10 
# define large 999 
# define null 0 
typedef struct 
{ 
  int a[maxlen],b[maxlen],w[maxlen];         /*第K边的起点，终点，权值*/ 
  char vexs[maxlen];                          /*顶点信息集合*/ 
  int vexnum,arcnum;                          /*顶点数和边数*/ 
  int arcs[maxlen][maxlen];                  /*邻接矩阵*/ 
}graph; 
graph g;                                       /*g为图类型变量*/     

graph cre_grah(graph g)                        /*创建图结构*/ 
{ 
  int i,j,k,c=999;                           /*设c值999为无穷大*/ 
  for (i=0;i<g.vexnum;i++)                   
    for(j=0;j<g.vexnum;j++) 
     g.arcs[i][j]=c;                        /*初始化邻接矩阵中的所有元素值为无穷大*/ 
  for (k=0;k<g.arcnum;k++) 
   { 
     g.arcs[g.a[k]-1][g.b[k]-1]=g.w[k];      /*对邻接矩阵赋值*/ 
     g.arcs[g.b[k]-1][g.a[k]-1]=g.w[k]; 
    } 
   print_graph(g);                           /*调用输出邻接矩阵函数*/ 
   return g;                                 /*返回创建的图*/ 
 } 


print_graph(graph g)                         /*输出邻接矩阵*/ 
{ 
  int i,j; 
  printf("ljjz:\n");      
  printf("vertex\t");                          /*vertex为顶点标示*/ 
  for (i=0;i<g.vexnum;i++) 
    printf("%4c",g.vexs[i]);                  /*输出邻接矩阵中的所有顶点*/ 
  printf("\n");          
  for(i=0;i<g.vexnum;i++)                      /*输出邻接矩阵中的所有值*/ 
  { 
    printf("% 4c \t",g.vexs[i]); 
    for(j=0;j<g.vexnum;j++); 
      printf("%4d",g.arcs[i][j]); 
    printf("\n"); 
  } 
} 

void prim(graph g)                           /*用prim算法求最小生成树*/ 
{ 
   int i,j,k,min; 
   int lowcost[maxlen];                       /*保存权值的数组*/ 
   int closet[maxlen];                        /*保存最小生成树结点的数组*/ 
   printf("zui xiao sheng cheng shu de biao:\n"); 
   for(i=1;i<g.vexnum;i++)                     /*将邻接矩阵中第1行的所有权值存入lowcost数组*/ 
   { 
     lowcost[i]=g.arcs[0][i]; 
     closet[i]=1; 
   } 
   closet[1]=0;                               /*选择顶点1作为出发点*/ 
   j=1; 
   for(i=1;i<g.vexnum;i++)                    /*找权值最小的边*/ 
   { 
    min=lowcost[j]; 
    k=i; 
    for(j=1;j<g.vexnum;j++) 
      if(lowcost[j]<min&&closet[j]!=0) 
      { 
          min=lowcost[j]; 
         k=j; 
      } 
    printf("(%c,%c),",g.vexs[closet[k]],g.vexs[k]); /*输出权值最小的边*/ 
    closet[k]=0;                                    /*设置为已访问标志*/ 
    for(j=1;j<g.vexnum;j++)                         /*考虑经过已选出的最短边，修改其他边的权值*/ 
    if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0) 
     { 
       lowcost[j]=g.arcs[k][j]; 
       closet[j]=k; 
      } 
   } 
} 


main() 
{ 
   int a,i,j,k,h; 
   clrscr(); 
   printf("qing shu ru cheng shi ge shu he cheng shi wang lou ge shu:"); /*输入城市个数和城市网络个数*/
   scanf("%d,%d",&i,&j); 
   g.vexnum=i; 
   g.arcnum=j; 
   for (i=0;i<g.vexnum;i++) 
   { 
     getchar(); 
     printf("\nDi %d ge ding dian de xin xi:",i++);             /*输入所有顶点信息*/ 
     g.vexs[i]=getchar(); 
   } 
   for (k=1;k<=g.arcnum;k++) 
   { 
     printf("\tqing shu ru di %d tiao bian de qi dian:",k);    /*输入所有边的起点*/ 
     scanf("%d",&g.a[k-1]); 
     printf("\nqing shu ru di %d tiao bian de zhong dian:",k); /*输入所有边的终点*/
     scanf("%d",&g.b[k-1]); 
     printf("\nqing shu ru di %dtiao bian de quan zhi:",k);     /*输入所有边的权值*/
     scanf("%d",&g.w[k-1]); 
   } 
   cre_grah(g); 
   prim(g); 
}