Prim函数

 1 /***********************************************************
 2 * Name: Prim
 3 * Called By: main
 4 * Parameter: G 无向网, start 起始顶点下标
 5 * Description: 通过辅助数组closedge来依次查找最小权值邻接顶点；
 6 *              并打印查找到的最小权值的顶点和它的邻接顶点
 7 ************************************************************/
 8 void Prim(AdjMatrix* G, int start)
 9 {
10     struct
11     {
12         int adjvex;
13         int lowcost;
14     }closedge[MAXVEX] = { 0 };/*辅助数组*/
15 
16     int i = 1;
17     int j = 1;
18     int k = 1;
19     int minvex = 0;/*最小权值的邻接顶点*/
20     int minweight = 0;/*最小权值*/
21 
22     closedge[start].lowcost = 0;
23     /*对除了出发点start以外的所有顶点初始化对应的closedge数组*/
24     for (i = 1; i <= G->vexnum; i++)
25     {
26         if (i != start)
27         {
28             closedge[i].adjvex = start;
29             closedge[i].lowcost = G->arcs[start][i];
30         }
31     }
32 
33     /*控制选中的n - 1条符合条件的边*/
34     for (i = 1; i <= G->vexnum - 1; i++)
35     {
36         /*选择最小权值的邻接顶点*/
37         minweight = INFINITY;
38         for (j = 1; j <= G->vexnum; j++)
39         {
40             if (closedge[j].lowcost != 0 && closedge[j].lowcost < minweight)
41             {
42                 minvex = j;
43                 minweight = closedge[j].lowcost;
44             }
45         }
46         printf("%c--%c\n", G->vex[closedge[minvex].adjvex], G->vex[minvex]);
47         closedge[minvex].lowcost = 0;/*标记该顶点不会再次被遍历*/
48 
49         /*更新closedge数组*/
50         for (k = 1; k <= G->vexnum; k++)
51         {
52             /*一旦发现有更小的权值出现，则更新closedge数组对应顶点的最小权值*/
53             if (k != minvex && G->arcs[minvex][k] < closedge[k].lowcost)
54             {
55                 closedge[k].adjvex = minvex;
56                 closedge[k].lowcost = G->arcs[minvex][k];
57             }
58         }
59     }
60 }

源代码

  1 /******************************************************************
  2 * Name: 最小生成树的Prim算法(无向网)
  3 * Date: 2022.01.24
  4 * Author: 吕辉
  5 * Description: 求最小生成树(Minimum Cost Spanning Tree)的Prim算法是
  6 *              利用最小生成树性质的一种贪心算法。适合稠密图(顶点多边少),
  7 *              通过辅助数组closedge来依次查找最小代价的邻接顶点，直至
  8 *              所有顶点全部遍历。
  9 *******************************************************************/
 10 #define _CRT_SECURE_NO_WARNINGS
 11 #include <stdio.h>
 12 #include <stdlib.h>
 13 
 14 #define MAXVEX 20/*最大顶点数*/
 15 #define INFINITY 32767/*权值最大值*/
 16 typedef struct
 17 {
 18     int vexnum;/*顶点数*/
 19     int arcnum;/*弧数*/
 20     char vex[MAXVEX];/*顶点信息*/
 21     int arcs[MAXVEX][MAXVEX];/*弧的权值*/
 22 }AdjMatrix;/*邻接矩阵*/
 23 
 24 void Create(AdjMatrix* G);
 25 int LocateVex(AdjMatrix* G, char vex);
 26 void Prim(AdjMatrix* G, int start);
 27 
 28 int main(void)
 29 {
 30     AdjMatrix G;
 31     Create(&G);
 32     Prim(&G, 1);
 33     system("pause");
 34     return 0;
 35 }
 36 /*****************************************
 37 * Name: Create
 38 * Call: Locatevex
 39 * Called By: main
 40 * Parameter: G 无向网
 41 * Description: 创建无向网
 42 ******************************************/
 43 void Create(AdjMatrix* G)
 44 {
 45     int i = 1;
 46     int j = 1;
 47     int k = 1;
 48     int weight = 0;
 49     char vex1 = '\0';
 50     char vex2 = '\0';
 51 
 52     printf("请输入顶点数和弧数(逗号分隔)：");
 53     scanf("%d%*c%d", &G->vexnum, &G->arcnum);
 54     /*初始化权值*/
 55     for (i = 1; i <= G->vexnum; i++)
 56     {
 57         for (j = 1; j <= G->vexnum; j++)
 58         {
 59             G->arcs[i][j] = INFINITY;
 60         }
 61     }
 62     for (i = 1; i <= G->vexnum; i++)
 63     {
 64         printf("请输入第%d个顶点：", i);
 65         scanf(" %c", &G->vex[i]);/*%c前有一空格用于吸收空白字符*/
 66     }
 67     for (k = 1; k <= G->arcnum; k++)
 68     {
 69         printf("请输入第%d条弧的两个顶点和权值(逗号分隔)：", k);
 70         scanf(" %c%*c%c%*c%d", &vex1, &vex2, &weight);
 71         i = LocateVex(G, vex1);
 72         j = LocateVex(G, vex2);
 73         G->arcs[i][j] = weight;
 74         G->arcs[j][i] = weight;
 75     }
 76 }
 77 /**********************************************************
 78 * Name: LocateVex
 79 * Called By: Create
 80 * Parameter: G 无向网, vex 顶点
 81 * Description: 若顶点表中存在该顶点则返回其在顶点表中的位置下标;
 82 *              否则返回0
 83 ***********************************************************/
 84 int LocateVex(AdjMatrix* G, char vex)
 85 {
 86     int i = 1;
 87     for (i = 1; i <= G->vexnum; i++)
 88     {
 89         if (G->vex[i] == vex)
 90         {
 91             return i;
 92         }
 93     }
 94     return 0;
 95 }
 96 /************************************************************
 97 * Name: Prim
 98 * Called By: main
 99 * Parameter: G 无向网, start 初始顶点下标
100 * Description: 通过辅助数组closedge来依次查找最小权值邻接顶点；
101 *              并打印查找到的最小权值的顶点和它的邻接顶点
102 *************************************************************/
103 void Prim(AdjMatrix* G, int start)
104 {
105     struct
106     {
107         int adjvex;
108         int lowcost;
109     }closedge[MAXVEX] = { 0 };/*辅助数组*/
110 
111     int i = 1;
112     int j = 1;
113     int k = 1;
114     int minvex = 0;/*最小权值的邻接顶点*/
115     int minweight = 0;/*最小权值*/
116 
117     closedge[start].lowcost = 0;
118     /*对除了出发点start以外的所有顶点初始化对应的closedge数组*/
119     for (i = 1; i <= G->vexnum; i++)
120     {
121         if (i != start)
122         {
123             closedge[i].adjvex = start;
124             closedge[i].lowcost = G->arcs[start][i];
125         }
126     }
127 
128     /*控制选中的n - 1条符合条件的边*/
129     for (i = 1; i <= G->vexnum - 1; i++)
130     {
131         /*选择最小权值的邻接顶点*/
132         minweight = INFINITY;
133         for (j = 1; j <= G->vexnum; j++)
134         {
135             if (closedge[j].lowcost != 0 && closedge[j].lowcost < minweight)
136             {
137                 minvex = j;
138                 minweight = closedge[j].lowcost;
139             }
140         }
141         printf("%c--%c\n", G->vex[closedge[minvex].adjvex], G->vex[minvex]);
142         closedge[minvex].lowcost = 0;/*标记该顶点不会再次被遍历*/
143 
144         /*更新closedge数组*/
145         for (k = 1; k <= G->vexnum; k++)
146         {
147             /*一旦发现有更小的权值出现，则更新closedge数组对应顶点的最小权值*/
148             if (k != minvex && G->arcs[minvex][k] < closedge[k].lowcost)
149             {
150                 closedge[k].adjvex = minvex;
151                 closedge[k].lowcost = G->arcs[minvex][k];
152             }
153         }
154     }
155 }