# 图论
关于图，有一些比较晦涩的算法，这里记录一下实现过程，代码我在 Visual Studio 2019 上测试过，可以放心食用。
时间汇总:
2021.4.29 更新图的最短路径算法
Dijkstra算法：求图的单源最短路径；Floyd算法：求图的多源最短路径；
2021.4.30 更新图的最小生成树算法
Prim算法：时间复杂度O(n²)
// 必要参数
#define MVNum 100 // 最大顶点数
#define INF 32767 // 无穷数
/*
* 最小生成树·Prim 算法
*/
void Prim(Graph* G, int v0)
{
// 构建辅助数组
bool isJoin[MVNum] = { false }; // 记录该顶点是否加入了U集
int lowCast[MVNum] = { 0 }; // 存放顶点如果加入到U集的最小权值
VexTexType u[MVNum] = { 0 }; // U集, 收纳已经加入最小生成树中的顶点
int i, w;
int miniCost = 0; // 最小代价之合
int count = 0;// 工具中间数,用来记录往最终素组(U集)中已经填入了几个顶点
// 初始化辅助数组
for (i = 0; i < G->vexnum; i++) {
isJoin[i] = false;
lowCast[i] = G->Edge[v0][i];
}
isJoin[v0] = true;
u[0] = G->Vex[v0];
count++;
// Prim
for (i = 0; i < G->vexnum; i++) {
if (i == v0) {
continue;
}
int minDis = INF;
int nextVex;
// 求下一个顶点
for (w = 0; w < G->vexnum; w++) {
if (!isJoin[w] && lowCast[w] < minDis) {
minDis = lowCast[w];
nextVex = w;
}
}
isJoin[nextVex] = true;
u[count++] = G->Vex[nextVex];
miniCost += minDis;
// 更新 lowCast
for (w = 0; w < G->vexnum; w++) {
if (!isJoin[w] && G->Edge[nextVex][w] < lowCast[w]) {
lowCast[w] = G->Edge[nextVex][w];
}
}
}
// 打印
printf("\n******************** Prim ********************\n");
printf("\n源点：%c\n", G->Vex[v0]);
printf("最小生成树为: ");
for (i = 0; i < G->vexnum; i++) {
printf("%c", u[i]);
}
printf("\n最小代价为: %d", miniCost);
}
/*
* 最短路径·Dijkstra 算法
*/
void Dijkstra(Graph *G, int v0)
{
// 创建辅助数组
bool final[MVNum] = { false };
int dis[MVNum] = { 0 };
int path[MVNum] = { 0 };
int i, w;
// 辅助数组初始化
for (i = 0; i < G->vexnum; i++) {
final[i] = false;
dis[i] = G->Edge[v0][i];
path[i] = dis[i] < INF ? v0 : -1;
}
final[v0] = true;
dis[v0] = 0;
// Dijkstra
for (i = 1; i < G->vexnum; i++) {
int minDis = INF;
int nextVex;
for (w = 0; w < G->vexnum; w++) {
if (!final[w] && dis[w] < minDis) {
minDis = dis[w];
nextVex = w;
}
}
final[nextVex] = true;
for (w = 0; w < G->vexnum; w++) {
if (!final[w] && G->Edge[nextVex][w] + minDis < dis[w]) {
dis[w] = G->Edge[nextVex][w] + minDis;
path[w] = nextVex;
}
}
}
printf("\n******************** Dijkstra ********************\n");
printf("\n源点：%c\n", G->Vex[v0]);
for (i = 0; i < G->vexnum; i++) {
printf("%c 到 %c 的最短路径为: %d\n", G->Vex[v0], G->Vex[i], dis[i]);
}
}
/*
* 最短路径·Floyd 算法
*/
void Floyd(Graph* G)
{
int dis[MVNum][MVNum] = { 0 };
int path[MVNum][MVNum] = { 0 };
int i, j, k;
// 初始化辅助数组
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
dis[i][j] = G->Edge[i][j];
path[i][j] = G->Edge[i][j] < INF ? i : -1;
}
}
// Floyd
for (k = 0; k < G->vexnum; k++) {
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
if (dis[i][k] + dis[k][j] < dis[i][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
path[i][j] = path[k][j];
}
}
}
}
// 打印结果
printf("\n******************** Floyd ********************\n");
printf("\ndis表如下: \n");
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
printf("%2d ", dis[i][j]);
}
printf("\n");
}
printf("\npath表如下: \n");
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
printf("%2d ", path[i][j]);
}
printf("\n");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148