Prim求解最小生成树

 1 #include "ljjz.h"
 2 
 3 typedef struct edgedata  /*用于保存最小生成树的边类型定义*/
 4        { int beg,en;     /*beg,en是边顶点序号*/
 5          int length;     /*边长*/
 6        }edge;
 7 
 8 /*函数功能：prim算法构造最小生成树
 9 函数参数：图的邻接矩阵g;边向量edge
10 */
11 void prim(Mgraph g, edge tree[M-1])
12 {  edge x;
13    int d,min,j,k,s,v;
14 
15    /* 建立初始入选点，并初始化生成树边集tree*/
16    for(v=1;v<=g.n-1;v++)
17    {
18        tree[v-1].beg=0;
19        tree[v-1].en=v;
20        tree[v-1].length=g.edges[0][v];
21    }
22 
23    /*依次求当前(第k条）最小两栖边，并加入TE*/
24    for(k=0;k<=g.n-3;k++)
25    {
26        min=tree[k].length;
27        s=k;
28        for(j=k+1;j<=g.n-2;j++)
29            if(tree[j].length<min)
30            {
31                min=tree[j].length;
32                s=j;
33            }
34        v=tree[s].en;
35        x=tree[s];
36        tree[s]=tree[k];
37        tree[k]=x;
38 
39    /*由于新顶点v的加入，修改两栖边的基本信息*/
40        for(j=k+1;j<=g.n-2;j++)
41        {
42            d=g.edges[v][tree[j].en];
43            if(d<tree[j].length)
44            {
45                tree[j].length=d;
46                tree[j].beg=v;
47            }
48        }
49    }
50    /*输出最小生成树*/
51     printf("
最小生成树是:
");/*输出最小生成树*/
52     for (j=0;j<=g.n-2;j++)
53         printf("
%c---%c  %d
",g.vexs[tree[j].beg],g.vexs[tree[j].en],tree[j].length);
54     printf("
最小生成树的根是： %c
", g.vexs[0]);
55  }
56 
57 int  main()
58   {
59    Mgraph g;
60    edge  tree[M-1];  /*用于存放最小生成树的M-1条边*/
61    creat(&g,"g.txt",0);  /*创建无向图的邻接矩阵*/
62    prim(g,tree);        /*求解图的最小生成树*/
63    return 0;
64 
65   }

 1 /********************************************/
 2 /*         邻接矩阵类型定义的头文件             */
 3 /*               文件名：ljjz.h                   */
 4 /********************************************/
 5 
 6 #include <stdio.h>
 7 #define FINITY 5000               /*此处用5000代表无穷大*/
 8 #define M 20                          /*最大顶点数*/
 9 typedef char vertextype;          /*顶点值类型*/
10 typedef int edgetype;             /*权值类型*/
11 typedef struct{
12     vertextype vexs[M];            /*顶点信息域*/
13     edgetype edges[M][M];     /*邻接矩阵*/
14     int n,e;                              /*图中顶点总数与边数*/
15 } Mgraph;                               /*邻接矩阵表示的图类型*/
16 /*   函数功能：建立图的邻接矩阵存储结构
17      函数参数：邻接矩阵的指针变量g；存放图信息的文件名s；图的类型c，c=0表示建立无向图，否则表示建立有向图 
18    函数返回值：无
19 */ 
20 void creat(Mgraph *g,char *s ,int c)
21 {int i,j,k,w;           /*建立网络的邻接矩阵存储结构*/
22    FILE *rf ;
23    rf = fopen(s, "r") ;   /*从文件中读取图的边信息*/
24    if (rf)
25    {
26    fscanf(rf,"%d%d",&g->n,&g->e);  /*读入图的顶点数与边数*/
27    for(i=0;i<g->n;i++)    /*读入图中的顶点值*/
28       fscanf(rf,"%1s",&g->vexs[i]);
29  
30    for(i=0;i<g->n;i++)    /*初始化邻接矩阵*/
31       for(j=0;j<g->n;j++)
32        if (i==j) g->edges[i][j]=0;
33        else g->edges[i][j]=FINITY;
34 
35    for (k=0;k<g->e;k++)  /*读入网络中的边*/
36     {fscanf(rf,"%d%d%d", &i,&j,&w);
37      g->edges[i][j]=w;
38      if (c==0) g->edges[j][i]=w;   /*如果C==0则建立无向图邻接矩阵，否则建立有向图邻矩阵*/
39     }
40    fclose(rf);
41    }
42    else g->n=0;
43 }
44 
45 
46 void  print(Mgraph g)
47 {/*辅助函数，输出邻接矩阵表示的图g*/
48   int i,j;
49  
50   for (i=0;i<g.n;i++)
51    { printf("%c ",g.vexs[i]); 
52     }
53     printf("
");
54   for (i=0;i<g.n;i++)
55     {    for (j=0;j<g.n;j++)
56          {printf("%6d",g.edges[i][j]);
57         }
58           printf("
");
59        }
60   }