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 }
View Code