/*****************************普里姆（Prim）算法***************************/
/*
此为无向图
Prim算法思想很简单，依托临接矩阵
就是从顶点0开始，依次比较起始点到下一个点的最短路径，并将其更新
然后以新的点为起始点，再找到该点能够到达的下一个最短路径，
直到所有点都遍历完为止！
*/
根据程序，最小线段生成如下：
1 #include "000库函数.h"
2
3 #define MAXVEX 20
4 #define INFINITY 65535//视为无穷大
5
6 //临接矩阵的数据结构
7 struct MGraph {
8 int arc[MAXVEX][MAXVEX];
9 int numVertexes, numEdges;
10 };
11
12 //初始化临接矩阵
13 MGraph *CreateMGraph(MGraph *G) {
14 G->numEdges = 15;
15 G->numVertexes = 9;
16
17 for (int i = 0; i < G->numVertexes; i++)/* 初始化图 */
18 {
19 for (int j = 0; j < G->numVertexes; j++)
20 {
21 if (i == j)
22 G->arc[i][j] = 0;
23 else
24 G->arc[i][j] = G->arc[j][i] = INFINITY;
25 }
26 }
27
28 G->arc[0][1] = 10;
29 G->arc[0][5] = 11;
30 G->arc[1][2] = 18;
31 G->arc[1][8] = 12;
32 G->arc[1][6] = 16;
33 G->arc[2][8] = 8;
34 G->arc[2][3] = 22;
35 G->arc[3][8] = 21;
36 G->arc[3][6] = 24;
37 G->arc[3][7] = 16;
38 G->arc[3][4] = 20;
39 G->arc[4][7] = 7;
40 G->arc[4][5] = 26;
41 G->arc[5][6] = 17;
42 G->arc[6][7] = 19;
43
44 for (int i = 0; i < G->numVertexes; i++)
45 {
46 for (int j = i; j < G->numVertexes; j++)
47 {
48 G->arc[j][i] = G->arc[i][j];
49 }
50 }
51 return G;
52 }
53
54 //使用Prim算法生成最小树
55 void MiniSpanTree_Prim(MGraph *G) {
56 int min, i, j, k;
57 int adjvex[MAXVEX];//保存相关顶点的下标
58 int lowcost[MAXVEX]; // 保存相关顶点间边的权值
59 lowcost[0] = 0;//将v0顶点加入进来
60 adjvex[0] = 0;//初始化第一个顶点为0
61 for (int i = 1; i < G->numVertexes; ++i) {
62 lowcost[i] = G->arc[0][i];//先将v0能到其他点的距离记录下来
63 adjvex[i] = 0;//即到达每个点的起始点都为0点
64 }
65
66 for (int i = 1; i < G->numVertexes; ++i) {
67 min = INFINITY;//将最短路径设为无穷
68 j = 1; k = 0;
69 while (j < G->numVertexes) {
70 if (lowcost[j] != 0 && lowcost[j] < min) {//找到点0到下一个距离最短的值
71 min = lowcost[j];//
72 k = j;//记住最小值的点
73 }
74 ++j;
75 }
76
77 printf("(%d, %d)\n", adjvex[k], k);
78 lowcost[k] = 0;//重新以点k为起始点，然后继续寻找下一个最短路径
79 for (j = 1; j < G->numVertexes; ++j) {
80 if (lowcost[j] != 0 && G->arc[k][j] < lowcost[j]) {//找到下一个最短路劲
81 lowcost[j] = G->arc[k][j];
82 adjvex[j] = k;
83 }
84 }
85
86 }
87 }
88
89 int T025(void){
90 MGraph *G;
91 G = new MGraph;//初始化图
92 G = CreateMGraph(G);
93 MiniSpanTree_Prim(G);
94
95 return 0;
96
97 }
/************************克鲁斯卡尔（Kruskal）******************/
根据权值大小，生成权值表，然后根据权值表进行探索路径
1 #include "000库函数.h"
2
3 #define MAXVEX 20
4 #define INFINITY 65535//视为无穷大
5
6 //临接矩阵的数据结构
7 struct MGraph {
8 int arc[MAXVEX][MAXVEX];
9 int numVertexes, numEdges;
10 };
11
12 //初始化临接矩阵
13 MGraph *CreateMGraph(MGraph *G) {
14 G->numEdges = 15;
15 G->numVertexes = 9;
16
17 for (int i = 0; i < G->numVertexes; i++)/* 初始化图 */
18 {
19 for (int j = 0; j < G->numVertexes; j++)
20 {
21 if (i == j)
22 G->arc[i][j] = 0;
23 else
24 G->arc[i][j] = G->arc[j][i] = INFINITY;
25 }
26 }
27
28 G->arc[0][1] = 10;
29 G->arc[0][5] = 11;
30 G->arc[1][2] = 18;
31 G->arc[1][8] = 12;
32 G->arc[1][6] = 16;
33 G->arc[2][8] = 8;
34 G->arc[2][3] = 22;
35 G->arc[3][8] = 21;
36 G->arc[3][6] = 24;
37 G->arc[3][7] = 16;
38 G->arc[3][4] = 20;
39 G->arc[4][7] = 7;
40 G->arc[4][5] = 26;
41 G->arc[5][6] = 17;
42 G->arc[6][7] = 19;
43
44 for (int i = 0; i < G->numVertexes; i++)
45 {
46 for (int j = i; j < G->numVertexes; j++)
47 {
48 G->arc[j][i] = G->arc[i][j];
49 }
50 }
51 return G;
52 }
53
54 //寻找下一个顶点位置
55 int Find(vector<int>parent, int v) {
56 while (parent[v] > 0)v = parent[v];
57 return v;
58 }
59
60
61 //使用MiniSpanTree_Kruskal生成最小树
62 void MiniSpanTree_Kruskal(MGraph *G) {
63 int n, m;
64 int k = 0;
65 vector<int> Parent(MAXVEX, 0);//定义一个数组，用来判断是否形成了环路
66 int Edge[MAXVEX][3];//权值表，存放起始点、终止点、权值
67 //构建权值表
68 for (int i = 0; i < G->numVertexes; ++i) {
69 for (int j = i + 1; j < G->numVertexes; ++j) {
70 if (G->arc[i][j] < INFINITY) {
71 Edge[k][0] = i;
72 Edge[k][1] = j;
73 Edge[k][2] = G->arc[i][j];
74 k++;
75 }
76 }
77 }
78 //进行排序
79 for (int i = 0; i < k; ++i) {
80 int min = Edge[i][2];
81 for (int j = i + 1; j < k; ++j) {
82 if (min > Edge[j][2]) {
83 min = Edge[j][2];
84 for (int t = 0; t < 3; ++t) {
85 int temp;
86 temp = Edge[i][t];
87 Edge[i][t] = Edge[j][t];
88 Edge[j][t] = temp;
89 }
90 }
91 }
92 }
93
94
95 /*************************算法的核心*****************************/
96
97
98
99
100 int adjvex[MAXVEX];//保存相关顶点的下标
101 int lowcost[MAXVEX]; // 保存相关顶点间边的权值
102 lowcost[0] = 0;//将v0顶点加入进来
103 adjvex[0] = 0;//初始化第一个顶点为0
104 for (int i = 1; i < G->numVertexes; ++i) {
105 lowcost[i] = G->arc[0][i];//先将v0能到其他点的距离记录下来
106 adjvex[i] = 0;//即到达每个点的起始点都为0点
107 }
108
109 for (int i = 0; i < k; ++i) {//循环每一个权值矩阵
110 n = Find(Parent, Edge[i][0]);
111 m = Find(Parent, Edge[i][1]);
112 if (n != m) {//不会形成环，可以使用
113 Parent[n] = m;
114 cout << Edge[i][0] << "," << Edge[i][1] << endl;
115 }
116 }
117 }
118
119
120
121 int T026(void) {
122 MGraph *G;
123 G = new MGraph;//初始化图
124 G = CreateMGraph(G);
125 MiniSpanTree_Kruskal(G);
126
127 return 0;
128
129 }