C语言数据结构-algo7-2.c

blake

1. /* algo7-2.c 实现算法7.9的程序 */
   
2. #include"c1.h"
   
3. typedef int VRType;
   
4. typedef char InfoType;
   
5. #define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
   
6. #define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
   
7. typedef char VertexType[MAX_NAME];
   
8. #include"c7-1.h"
   
9. #include"bo7-1.c"
   
10. 
    
11. typedef struct
    
12. { /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */
    
13.    VertexType adjvex;
    
14.    VRType lowcost;
    
15. }minside[MAX_VERTEX_NUM];
    
16. 
    
17. int minimum(minside SZ,MGraph G)
    
18. { /* 求closedge.lowcost的最小正值 */
    
19.    int i=0,j,k,min;
    
20.    while(!SZ[i].lowcost)
    
21.      i++;
    
22.    min=SZ[i].lowcost; /* 第一个不为0的值 */
    
23.    k=i;
    
24.    for(j=i+1;j<G.vexnum;j++)
    
25.      if(SZ[j].lowcost>0)
    
26.        if(min>SZ[j].lowcost)
    
27.        {
    
28.          min=SZ[j].lowcost;
    
29.          k=j;
    
30.        }
    
31.    return k;
    
32. }
    
33. 
    
34. void MiniSpanTree_PRIM(MGraph G,VertexType u)
    
35. { /* 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 算法7.9 */
    
36.    int i,j,k;
    
37.    minside closedge;
    
38.    k=LocateVex(G,u);
    
39.    for(j=0;j<G.vexnum;++j) /* 辅助数组初始化 */
    
40.    {
    
41.      if(j!=k)
    
42.      {
    
43.        strcpy(closedge[j].adjvex,u);
    
44.        closedge[j].lowcost=G.arcs[k][j].adj;
    
45.      }
    
46.    }
    
47.    closedge[k].lowcost=0; /* 初始,U={u} */
    
48.    printf("最小代价生成树的各条边为:\n");
    
49.    for(i=1;i<G.vexnum;++i)
    
50.    { /* 选择其余G.vexnum-1个顶点 */
    
51.      k=minimum(closedge,G); /* 求出T的下一个结点：第K顶点 */
    
52.      printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); /* 输出生成树的边 */
    
53.      closedge[k].lowcost=0; /* 第K顶点并入U集 */
    
54.      for(j=0;j<G.vexnum;++j)
    
55.        if(G.arcs[k][j].adj<closedge[j].lowcost)
    
56.        { /* 新顶点并入U集后重新选择最小边 */
    
57.          strcpy(closedge[j].adjvex,G.vexs[k]);
    
58.          closedge[j].lowcost=G.arcs[k][j].adj;
    
59.        }
    
60.    }
    
61. }
    
62. 
    
63. void main()
    
64. {
    
65.    MGraph G;
    
66.    CreateAN(&G);
    
67.    MiniSpanTree_PRIM(G,G.vexs[0]);
    
68. }
    
69. 

复制代码