1 /**
2 * C: Dijkstra算法获取最短路径(邻接矩阵)
3 *
6 */
7
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <malloc.h>
11 #include <string.h>
12
13 #define MAX 100 // 矩阵最大容量
14 #define INF (~(0x1<<31)) // 最大值(即0X7FFFFFFF)
15 #define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
16 #define LENGTH(a) (sizeof(a)/sizeof(a[0]))
17
18 // 邻接矩阵
19 typedef struct _graph
20 {
21 char vexs[MAX]; // 顶点集合
22 int vexnum; // 顶点数
23 int edgnum; // 边数
24 int matrix[MAX][MAX]; // 邻接矩阵
25 }Graph, *PGraph;
26
27 // 边的结构体
28 typedef struct _EdgeData
29 {
30 char start; // 边的起点
31 char end; // 边的终点
32 int weight; // 边的权重
33 }EData;
34
35 /*
36 * 返回ch在matrix矩阵中的位置
37 */
38 static int get_position(Graph G, char ch)
39 {
40 int i;
41 for(i=0; i<G.vexnum; i++)
42 if(G.vexs[i]==ch)
43 return i;
44 return -1;
45 }
46
47 /*
48 * 读取一个输入字符
49 */
50 static char read_char()
51 {
52 char ch;
53
54 do {
55 ch = getchar();
56 } while(!isLetter(ch));
57
58 return ch;
59 }
60
61 /*
62 * 创建图(自己输入)
63 */
64 Graph* create_graph()
65 {
66 char c1, c2;
67 int v, e;
68 int i, j, weight, p1, p2;
69 Graph* pG;
70
71 // 输入"顶点数"和"边数"
72 printf("input vertex number: ");
73 scanf("%d", &v);
74 printf("input edge number: ");
75 scanf("%d", &e);
76 if ( v < 1 || e < 1 || (e > (v * (v-1))))
77 {
78 printf("input error: invalid parameters!\n");
79 return NULL;
80 }
81
82 if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
83 return NULL;
84 memset(pG, 0, sizeof(Graph));
85
86 // 初始化"顶点数"和"边数"
87 pG->vexnum = v;
88 pG->edgnum = e;
89 // 初始化"顶点"
90 for (i = 0; i < pG->vexnum; i++)
91 {
92 printf("vertex(%d): ", i);
93 pG->vexs[i] = read_char();
94 }
95
96 // 1. 初始化"边"的权值
97 for (i = 0; i < pG->vexnum; i++)
98 {
99 for (j = 0; j < pG->vexnum; j++)
100 {
101 if (i==j)
102 pG->matrix[i][j] = 0;
103 else
104 pG->matrix[i][j] = INF;
105 }
106 }
107 // 2. 初始化"边"的权值: 根据用户的输入进行初始化
108 for (i = 0; i < pG->edgnum; i++)
109 {
110 // 读取边的起始顶点，结束顶点，权值
111 printf("edge(%d):", i);
112 c1 = read_char();
113 c2 = read_char();
114 scanf("%d", &weight);
115
116 p1 = get_position(*pG, c1);
117 p2 = get_position(*pG, c2);
118 if (p1==-1 || p2==-1)
119 {
120 printf("input error: invalid edge!\n");
121 free(pG);
122 return NULL;
123 }
124
125 pG->matrix[p1][p2] = weight;
126 pG->matrix[p2][p1] = weight;
127 }
128
129 return pG;
130 }
131
132 /*
133 * 创建图(用已提供的矩阵)
134 */
135 Graph* create_example_graph()
136 {
137 char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
138 int matrix[][9] = {
139 /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
140 /*A*/ { 0, 12, INF, INF, INF, 16, 14},
141 /*B*/ { 12, 0, 10, INF, INF, 7, INF},
142 /*C*/ { INF, 10, 0, 3, 5, 6, INF},
143 /*D*/ { INF, INF, 3, 0, 4, INF, INF},
144 /*E*/ { INF, INF, 5, 4, 0, 2, 8},
145 /*F*/ { 16, 7, 6, INF, 2, 0, 9},
146 /*G*/ { 14, INF, INF, INF, 8, 9, 0}};
147 int vlen = LENGTH(vexs);
148 int i, j;
149 Graph* pG;
150
151 // 输入"顶点数"和"边数"
152 if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
153 return NULL;
154 memset(pG, 0, sizeof(Graph));
155
156 // 初始化"顶点数"
157 pG->vexnum = vlen;
158 // 初始化"顶点"
159 for (i = 0; i < pG->vexnum; i++)
160 pG->vexs[i] = vexs[i];
161
162 // 初始化"边"
163 for (i = 0; i < pG->vexnum; i++)
164 for (j = 0; j < pG->vexnum; j++)
165 pG->matrix[i][j] = matrix[i][j];
166
167 // 统计边的数目
168 for (i = 0; i < pG->vexnum; i++)
169 for (j = 0; j < pG->vexnum; j++)
170 if (i!=j && pG->matrix[i][j]!=INF)
171 pG->edgnum++;
172 pG->edgnum /= 2;
173
174 return pG;
175 }
176
177 /*
178 * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
179 */
180 static int first_vertex(Graph G, int v)
181 {
182 int i;
183
184 if (v<0 || v>(G.vexnum-1))
185 return -1;
186
187 for (i = 0; i < G.vexnum; i++)
188 if (G.matrix[v][i]!=0 && G.matrix[v][i]!=INF)
189 return i;
190
191 return -1;
192 }
193
194 /*
195 * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
196 */
197 static int next_vertix(Graph G, int v, int w)
198 {
199 int i;
200
201 if (v<0 || v>(G.vexnum-1) || w<0 || w>(G.vexnum-1))
202 return -1;
203
204 for (i = w + 1; i < G.vexnum; i++)
205 if (G.matrix[v][i]!=0 && G.matrix[v][i]!=INF)
206 return i;
207
208 return -1;
209 }
210
211 /*
212 * 深度优先搜索遍历图的递归实现
213 */
214 static void DFS(Graph G, int i, int *visited)
215 {
216 int w;
217
218 visited[i] = 1;
219 printf("%c ", G.vexs[i]);
220 // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
221 for (w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w))
222 {
223 if (!visited[w])
224 DFS(G, w, visited);
225 }
226
227 }
228
229 /*
230 * 深度优先搜索遍历图
231 */
232 void DFSTraverse(Graph G)
233 {
234 int i;
235 int visited[MAX]; // 顶点访问标记
236
237 // 初始化所有顶点都没有被访问
238 for (i = 0; i < G.vexnum; i++)
239 visited[i] = 0;
240
241 printf("DFS: ");
242 for (i = 0; i < G.vexnum; i++)
243 {
244 //printf("\n== LOOP(%d)\n", i);
245 if (!visited[i])
246 DFS(G, i, visited);
247 }
248 printf("\n");
249 }
250
251 /*
252 * 广度优先搜索（类似于树的层次遍历）
253 */
254 void BFS(Graph G)
255 {
256 int head = 0;
257 int rear = 0;
258 int queue[MAX]; // 辅组队列
259 int visited[MAX]; // 顶点访问标记
260 int i, j, k;
261
262 for (i = 0; i < G.vexnum; i++)
263 visited[i] = 0;
264
265 printf("BFS: ");
266 for (i = 0; i < G.vexnum; i++)
267 {
268 if (!visited[i])
269 {
270 visited[i] = 1;
271 printf("%c ", G.vexs[i]);
272 queue[rear++] = i; // 入队列
273 }
274 while (head != rear)
275 {
276 j = queue[head++]; // 出队列
277 for (k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点
278 {
279 if (!visited[k])
280 {
281 visited[k] = 1;
282 printf("%c ", G.vexs[k]);
283 queue[rear++] = k;
284 }
285 }
286 }
287 }
288 printf("\n");
289 }
290
291 /*
292 * 打印矩阵队列图
293 */
294 void print_graph(Graph G)
295 {
296 int i,j;
297
298 printf("Martix Graph:\n");
299 for (i = 0; i < G.vexnum; i++)
300 {
301 for (j = 0; j < G.vexnum; j++)
302 printf("%10d ", G.matrix[i][j]);
303 printf("\n");
304 }
305 }
306
307 /*
308 * prim最小生成树
309 *
310 * 参数说明：
311 * G -- 邻接矩阵图
312 * start -- 从图中的第start个元素开始，生成最小树
313 */
314 void prim(Graph G, int start)
315 {
316 int min,i,j,k,m,n,sum;
317 int index=0; // prim最小树的索引，即prims数组的索引
318 char prims[MAX]; // prim最小树的结果数组
319 int weights[MAX]; // 顶点间边的权值
320
321 // prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。
322 prims[index++] = G.vexs[start];
323
324 // 初始化"顶点的权值数组"，
325 // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
326 for (i = 0; i < G.vexnum; i++ )
327 weights[i] = G.matrix[start][i];
328 // 将第start个顶点的权值初始化为0。
329 // 可以理解为"第start个顶点到它自身的距离为0"。
330 weights[start] = 0;
331
332 for (i = 0; i < G.vexnum; i++)
333 {
334 // 由于从start开始的，因此不需要再对第start个顶点进行处理。
335 if(start == i)
336 continue;
337
338 j = 0;
339 k = 0;
340 min = INF;
341 // 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
342 while (j < G.vexnum)
343 {
344 // 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。
345 if (weights[j] != 0 && weights[j] < min)
346 {
347 min = weights[j];
348 k = j;
349 }
350 j++;
351 }
352
353 // 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。
354 // 将第k个顶点加入到最小生成树的结果数组中
355 prims[index++] = G.vexs[k];
356 // 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
357 weights[k] = 0;
358 // 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
359 for (j = 0 ; j < G.vexnum; j++)
360 {
361 // 当第j个节点没有被处理，并且需要更新时才被更新。
362 if (weights[j] != 0 && G.matrix[k][j] < weights[j])
363 weights[j] = G.matrix[k][j];
364 }
365 }
366
367 // 计算最小生成树的权值
368 sum = 0;
369 for (i = 1; i < index; i++)
370 {
371 min = INF;
372 // 获取prims[i]在G中的位置
373 n = get_position(G, prims[i]);
374 // 在vexs[0...i]中，找出到j的权值最小的顶点。
375 for (j = 0; j < i; j++)
376 {
377 m = get_position(G, prims[j]);
378 if (G.matrix[m][n]<min)
379 min = G.matrix[m][n];
380 }
381 sum += min;
382 }
383 // 打印最小生成树
384 printf("PRIM(%c)=%d: ", G.vexs[start], sum);
385 for (i = 0; i < index; i++)
386 printf("%c ", prims[i]);
387 printf("\n");
388 }
389
390 /*
391 * 获取图中的边
392 */
393 EData* get_edges(Graph G)
394 {
395 int i,j;
396 int index=0;
397 EData *edges;
398
399 edges = (EData*)malloc(G.edgnum*sizeof(EData));
400 for (i=0;i < G.vexnum;i++)
401 {
402 for (j=i+1;j < G.vexnum;j++)
403 {
404 if (G.matrix[i][j]!=INF)
405 {
406 edges[index].start = G.vexs[i];
407 edges[index].end = G.vexs[j];
408 edges[index].weight = G.matrix[i][j];
409 index++;
410 }
411 }
412 }
413
414 return edges;
415 }
416
417 /*
418 * 对边按照权值大小进行排序(由小到大)
419 */
420 void sorted_edges(EData* edges, int elen)
421 {
422 int i,j;
423
424 for (i=0; i<elen; i++)
425 {
426 for (j=i+1; j<elen; j++)
427 {
428 if (edges[i].weight > edges[j].weight)
429 {
430 // 交换"第i条边"和"第j条边"
431 EData tmp = edges[i];
432 edges[i] = edges[j];
433 edges[j] = tmp;
434 }
435 }
436 }
437 }
438
439 /*
440 * 获取i的终点
441 */
442 int get_end(int vends[], int i)
443 {
444 while (vends[i] != 0)
445 i = vends[i];
446 return i;
447 }
448
449 /*
450 * 克鲁斯卡尔（Kruskal)最小生成树
451 */
452 void kruskal(Graph G)
453 {
454 int i,m,n,p1,p2;
455 int length;
456 int index = 0; // rets数组的索引
457 int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
458 EData rets[MAX]; // 结果数组，保存kruskal最小生成树的边
459 EData *edges; // 图对应的所有边
460
461 // 获取"图中所有的边"
462 edges = get_edges(G);
463 // 将边按照"权"的大小进行排序(从小到大)
464 sorted_edges(edges, G.edgnum);
465
466 for (i=0; i<G.edgnum; i++)
467 {
468 p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号
469 p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号
470
471 m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点
472 n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点
473 // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
474 if (m != n)
475 {
476 vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n
477 rets[index++] = edges[i]; // 保存结果
478 }
479 }
480 free(edges);
481
482 // 统计并打印"kruskal最小生成树"的信息
483 length = 0;
484 for (i = 0; i < index; i++)
485 length += rets[i].weight;
486 printf("Kruskal=%d: ", length);
487 for (i = 0; i < index; i++)
488 printf("(%c,%c) ", rets[i].start, rets[i].end);
489 printf("\n");
490 }
491
492 /*
493 * Dijkstra最短路径。
494 * 即，统计图(G)中"顶点vs"到其它各个顶点的最短路径。
495 *
496 * 参数说明：
497 * G -- 图
498 * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
499 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
500 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
501 */
502 void dijkstra(Graph G, int vs, int prev[], int dist[])
503 {
504 int i,j,k;
505 int min;
506 int tmp;
507 int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
508
509 // 初始化
510 for (i = 0; i < G.vexnum; i++)
511 {
512 flag[i] = 0; // 顶点i的最短路径还没获取到。
513 prev[i] = 0; // 顶点i的前驱顶点为0。
514 dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
515 }
516
517 // 对"顶点vs"自身进行初始化
518 flag[vs] = 1;
519 dist[vs] = 0;
520
521 // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
522 for (i = 1; i < G.vexnum; i++)
523 {
524 // 寻找当前最小的路径；
525 // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
526 min = INF;
527 for (j = 0; j < G.vexnum; j++)
528 {
529 if (flag[j]==0 && dist[j]<min)
530 {
531 min = dist[j];
532 k = j;
533 }
534 }
535 // 标记"顶点k"为已经获取到最短路径
536 flag[k] = 1;
537
538 // 修正当前最短路径和前驱顶点
539 // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
540 for (j = 0; j < G.vexnum; j++)
541 {
542 tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出
543 if (flag[j] == 0 && (tmp < dist[j]) )
544 {
545 dist[j] = tmp;
546 prev[j] = k;
547 }
548 }
549 }
550
551 // 打印dijkstra最短路径的结果
552 printf("dijkstra(%c): \n", G.vexs[vs]);
553 for (i = 0; i < G.vexnum; i++)
554 printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);
555 }
556
557 void main()
558 {
559 int prev[MAX] = {0};
560 int dist[MAX] = {0};
561 Graph* pG;
562
563 // 自定义"图"(输入矩阵队列)
564 //pG = create_graph();
565 // 采用已有的"图"
566 pG = create_example_graph();
567
568 //print_graph(*pG); // 打印图
569 //DFSTraverse(*pG); // 深度优先遍历
570 //BFS(*pG); // 广度优先遍历
571 //prim(*pG, 0); // prim算法生成最小生成树
572 //kruskal(*pG); // kruskal算法生成最小生成树
573
574 // dijkstra算法获取"第4个顶点"到其它各个顶点的最短距离
575 dijkstra(*pG, 3, prev, dist);
576 }
1
2 /**
3 * C: Dijkstra算法获取最短路径(邻接表)
4 *
7 */
8
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <malloc.h>
12 #include <string.h>
13
14 #define MAX 100
15 #define INF (~(0x1<<31)) // 最大值(即0X7FFFFFFF)
16 #define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
17 #define LENGTH(a) (sizeof(a)/sizeof(a[0]))
18
19 // 邻接表中表对应的链表的顶点
20 typedef struct _ENode
21 {
22 int ivex; // 该边的顶点的位置
23 int weight; // 该边的权
24 struct _ENode *next_edge; // 指向下一条弧的指针
25 }ENode, *PENode;
26
27 // 邻接表中表的顶点
28 typedef struct _VNode
29 {
30 char data; // 顶点信息
31 ENode *first_edge; // 指向第一条依附该顶点的弧
32 }VNode;
33
34 // 邻接表
35 typedef struct _LGraph
36 {
37 int vexnum; // 图的顶点的数目
38 int edgnum; // 图的边的数目
39 VNode vexs[MAX];
40 }LGraph;
41
42 /*
43 * 返回ch在matrix矩阵中的位置
44 */
45 static int get_position(LGraph G, char ch)
46 {
47 int i;
48 for(i=0; i<G.vexnum; i++)
49 if(G.vexs[i].data==ch)
50 return i;
51 return -1;
52 }
53
54 /*
55 * 读取一个输入字符
56 */
57 static char read_char()
58 {
59 char ch;
60
61 do {
62 ch = getchar();
63 } while(!isLetter(ch));
64
65 return ch;
66 }
67
68 /*
69 * 将node链接到list的末尾
70 */
71 static void link_last(ENode *list, ENode *node)
72 {
73 ENode *p = list;
74
75 while(p->next_edge)
76 p = p->next_edge;
77 p->next_edge = node;
78 }
79
80 /*
81 * 创建邻接表对应的图(自己输入)
82 */
83 LGraph* create_lgraph()
84 {
85 char c1, c2;
86 int v, e;
87 int i, p1, p2;
88 int weight;
89 ENode *node1, *node2;
90 LGraph* pG;
91
92 // 输入"顶点数"和"边数"
93 printf("input vertex number: ");
94 scanf("%d", &v);
95 printf("input edge number: ");
96 scanf("%d", &e);
97 if ( v < 1 || e < 1 || (e > (v * (v-1))))
98 {
99 printf("input error: invalid parameters!\n");
100 return NULL;
101 }
102
103 if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
104 return NULL;
105 memset(pG, 0, sizeof(LGraph));
106
107 // 初始化"顶点数"和"边数"
108 pG->vexnum = v;
109 pG->edgnum = e;
110 // 初始化"邻接表"的顶点
111 for(i=0; i<pG->vexnum; i++)
112 {
113 printf("vertex(%d): ", i);
114 pG->vexs[i].data = read_char();
115 pG->vexs[i].first_edge = NULL;
116 }
117
118 // 初始化"邻接表"的边
119 for(i=0; i<pG->edgnum; i++)
120 {
121 // 读取边的起始顶点,结束顶点,权
122 printf("edge(%d): ", i);
123 c1 = read_char();
124 c2 = read_char();
125 scanf("%d", &weight);
126
127 p1 = get_position(*pG, c1);
128 p2 = get_position(*pG, c2);
129
130 // 初始化node1
131 node1 = (ENode*)malloc(sizeof(ENode));
132 node1->ivex = p2;
133 node1->weight = weight;
134 // 将node1链接到"p1所在链表的末尾"
135 if(pG->vexs[p1].first_edge == NULL)
136 pG->vexs[p1].first_edge = node1;
137 else
138 link_last(pG->vexs[p1].first_edge, node1);
139 // 初始化node2
140 node2 = (ENode*)malloc(sizeof(ENode));
141 node2->ivex = p1;
142 node2->weight = weight;
143 // 将node2链接到"p2所在链表的末尾"
144 if(pG->vexs[p2].first_edge == NULL)
145 pG->vexs[p2].first_edge = node2;
146 else
147 link_last(pG->vexs[p2].first_edge, node2);
148 }
149
150 return pG;
151 }
152
153 // 边的结构体
154 typedef struct _edata
155 {
156 char start; // 边的起点
157 char end; // 边的终点
158 int weight; // 边的权重
159 }EData;
160
161 // 顶点
162 static char gVexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
163 // 边
164 static EData gEdges[] = {
165 // 起点 终点 权
166 {'A', 'B', 12},
167 {'A', 'F', 16},
168 {'A', 'G', 14},
169 {'B', 'C', 10},
170 {'B', 'F', 7},
171 {'C', 'D', 3},
172 {'C', 'E', 5},
173 {'C', 'F', 6},
174 {'D', 'E', 4},
175 {'E', 'F', 2},
176 {'E', 'G', 8},
177 {'F', 'G', 9},
178 };
179
180 /*
181 * 创建邻接表对应的图(用已提供的数据)
182 */
183 LGraph* create_example_lgraph()
184 {
185 char c1, c2;
186 int vlen = LENGTH(gVexs);
187 int elen = LENGTH(gEdges);
188 int i, p1, p2;
189 int weight;
190 ENode *node1, *node2;
191 LGraph* pG;
192
193 if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
194 return NULL;
195 memset(pG, 0, sizeof(LGraph));
196
197 // 初始化"顶点数"和"边数"
198 pG->vexnum = vlen;
199 pG->edgnum = elen;
200 // 初始化"邻接表"的顶点
201 for(i=0; i<pG->vexnum; i++)
202 {
203 pG->vexs[i].data = gVexs[i];
204 pG->vexs[i].first_edge = NULL;
205 }
206
207 // 初始化"邻接表"的边
208 for(i=0; i<pG->edgnum; i++)
209 {
210 // 读取边的起始顶点,结束顶点,权
211 c1 = gEdges[i].start;
212 c2 = gEdges[i].end;
213 weight = gEdges[i].weight;
214
215 p1 = get_position(*pG, c1);
216 p2 = get_position(*pG, c2);
217
218 // 初始化node1
219 node1 = (ENode*)malloc(sizeof(ENode));
220 node1->ivex = p2;
221 node1->weight = weight;
222 // 将node1链接到"p1所在链表的末尾"
223 if(pG->vexs[p1].first_edge == NULL)
224 pG->vexs[p1].first_edge = node1;
225 else
226 link_last(pG->vexs[p1].first_edge, node1);
227 // 初始化node2
228 node2 = (ENode*)malloc(sizeof(ENode));
229 node2->ivex = p1;
230 node2->weight = weight;
231 // 将node2链接到"p2所在链表的末尾"
232 if(pG->vexs[p2].first_edge == NULL)
233 pG->vexs[p2].first_edge = node2;
234 else
235 link_last(pG->vexs[p2].first_edge, node2);
236 }
237
238 return pG;
239 }
240
241 /*
242 * 深度优先搜索遍历图的递归实现
243 */
244 static void DFS(LGraph G, int i, int *visited)
245 {
246 int w;
247 ENode *node;
248
249 visited[i] = 1;
250 printf("%c ", G.vexs[i].data);
251 node = G.vexs[i].first_edge;
252 while (node != NULL)
253 {
254 if (!visited[node->ivex])
255 DFS(G, node->ivex, visited);
256 node = node->next_edge;
257 }
258 }
259
260 /*
261 * 深度优先搜索遍历图
262 */
263 void DFSTraverse(LGraph G)
264 {
265 int i;
266 int visited[MAX]; // 顶点访问标记
267
268 // 初始化所有顶点都没有被访问
269 for (i = 0; i < G.vexnum; i++)
270 visited[i] = 0;
271
272 printf("DFS: ");
273 for (i = 0; i < G.vexnum; i++)
274 {
275 if (!visited[i])
276 DFS(G, i, visited);
277 }
278 printf("\n");
279 }
280
281 /*
282 * 广度优先搜索（类似于树的层次遍历）
283 */
284 void BFS(LGraph G)
285 {
286 int head = 0;
287 int rear = 0;
288 int queue[MAX]; // 辅组队列
289 int visited[MAX]; // 顶点访问标记
290 int i, j, k;
291 ENode *node;
292
293 for (i = 0; i < G.vexnum; i++)
294 visited[i] = 0;
295
296 printf("BFS: ");
297 for (i = 0; i < G.vexnum; i++)
298 {
299 if (!visited[i])
300 {
301 visited[i] = 1;
302 printf("%c ", G.vexs[i].data);
303 queue[rear++] = i; // 入队列
304 }
305 while (head != rear)
306 {
307 j = queue[head++]; // 出队列
308 node = G.vexs[j].first_edge;
309 while (node != NULL)
310 {
311 k = node->ivex;
312 if (!visited[k])
313 {
314 visited[k] = 1;
315 printf("%c ", G.vexs[k].data);
316 queue[rear++] = k;
317 }
318 node = node->next_edge;
319 }
320 }
321 }
322 printf("\n");
323 }
324
325 /*
326 * 打印邻接表图
327 */
328 void print_lgraph(LGraph G)
329 {
330 int i,j;
331 ENode *node;
332
333 printf("List Graph:\n");
334 for (i = 0; i < G.vexnum; i++)
335 {
336 printf("%d(%c): ", i, G.vexs[i].data);
337 node = G.vexs[i].first_edge;
338 while (node != NULL)
339 {
340 printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data);
341 node = node->next_edge;
342 }
343 printf("\n");
344 }
345 }
346
347 /*
348 * 获取G中边<start, end>的权值；若start和end不是连通的，则返回无穷大。
349 */
350 int get_weight(LGraph G, int start, int end)
351 {
352 ENode *node;
353
354 if (start==end)
355 return 0;
356
357 node = G.vexs[start].first_edge;
358 while (node!=NULL)
359 {
360 if (end==node->ivex)
361 return node->weight;
362 node = node->next_edge;
363 }
364
365 return INF;
366 }
367
368 /*
369 * prim最小生成树
370 *
371 * 参数说明：
372 * G -- 邻接表图
373 * start -- 从图中的第start个元素开始，生成最小树
374 */
375 void prim(LGraph G, int start)
376 {
377 int min,i,j,k,m,n,tmp,sum;
378 int index=0; // prim最小树的索引，即prims数组的索引
379 char prims[MAX]; // prim最小树的结果数组
380 int weights[MAX]; // 顶点间边的权值
381
382 // prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。
383 prims[index++] = G.vexs[start].data;
384
385 // 初始化"顶点的权值数组"，
386 // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
387 for (i = 0; i < G.vexnum; i++ )
388 weights[i] = get_weight(G, start, i);
389
390 for (i = 0; i < G.vexnum; i++)
391 {
392 // 由于从start开始的，因此不需要再对第start个顶点进行处理。
393 if(start == i)
394 continue;
395
396 j = 0;
397 k = 0;
398 min = INF;
399 // 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
400 while (j < G.vexnum)
401 {
402 // 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。
403 if (weights[j] != 0 && weights[j] < min)
404 {
405 min = weights[j];
406 k = j;
407 }
408 j++;
409 }
410
411 // 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。
412 // 将第k个顶点加入到最小生成树的结果数组中
413 prims[index++] = G.vexs[k].data;
414 // 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
415 weights[k] = 0;
416 // 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
417 for (j = 0 ; j < G.vexnum; j++)
418 {
419 // 获取第k个顶点到第j个顶点的权值
420 tmp = get_weight(G, k, j);
421 // 当第j个节点没有被处理，并且需要更新时才被更新。
422 if (weights[j] != 0 && tmp < weights[j])
423 weights[j] = tmp;
424 }
425 }
426
427 // 计算最小生成树的权值
428 sum = 0;
429 for (i = 1; i < index; i++)
430 {
431 min = INF;
432 // 获取prims[i]在G中的位置
433 n = get_position(G, prims[i]);
434 // 在vexs[0...i]中，找出到j的权值最小的顶点。
435 for (j = 0; j < i; j++)
436 {
437 m = get_position(G, prims[j]);
438 tmp = get_weight(G, m, n);
439 if (tmp < min)
440 min = tmp;
441 }
442 sum += min;
443 }
444 // 打印最小生成树
445 printf("PRIM(%c)=%d: ", G.vexs[start].data, sum);
446 for (i = 0; i < index; i++)
447 printf("%c ", prims[i]);
448 printf("\n");
449 }
450
451 /*
452 * 获取图中的边
453 */
454 EData* get_edges(LGraph G)
455 {
456 int i,j;
457 int index=0;
458 ENode *node;
459 EData *edges;
460
461 edges = (EData*)malloc(G.edgnum*sizeof(EData));
462 for (i=0; i<G.vexnum; i++)
463 {
464 node = G.vexs[i].first_edge;
465 while (node != NULL)
466 {
467 if (node->ivex > i)
468 {
469 edges[index].start = G.vexs[i].data; // 起点
470 edges[index].end = G.vexs[node->ivex].data; // 终点
471 edges[index].weight = node->weight; // 权
472 index++;
473 }
474 node = node->next_edge;
475 }
476 }
477
478 return edges;
479 }
480
481 /*
482 * 对边按照权值大小进行排序(由小到大)
483 */
484 void sorted_edges(EData* edges, int elen)
485 {
486 int i,j;
487
488 for (i=0; i<elen; i++)
489 {
490 for (j=i+1; j<elen; j++)
491 {
492 if (edges[i].weight > edges[j].weight)
493 {
494 // 交换"第i条边"和"第j条边"
495 EData tmp = edges[i];
496 edges[i] = edges[j];
497 edges[j] = tmp;
498 }
499 }
500 }
501 }
502
503 /*
504 * 获取i的终点
505 */
506 int get_end(int vends[], int i)
507 {
508 while (vends[i] != 0)
509 i = vends[i];
510 return i;
511 }
512
513 /*
514 * 克鲁斯卡尔（Kruskal)最小生成树
515 */
516 void kruskal(LGraph G)
517 {
518 int i,m,n,p1,p2;
519 int length;
520 int index = 0; // rets数组的索引
521 int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
522 EData rets[MAX]; // 结果数组，保存kruskal最小生成树的边
523 EData *edges; // 图对应的所有边
524
525 // 获取"图中所有的边"
526 edges = get_edges(G);
527 // 将边按照"权"的大小进行排序(从小到大)
528 sorted_edges(edges, G.edgnum);
529
530 for (i=0; i<G.edgnum; i++)
531 {
532 p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号
533 p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号
534
535 m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点
536 n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点
537 // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
538 if (m != n)
539 {
540 vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n
541 rets[index++] = edges[i]; // 保存结果
542 }
543 }
544 free(edges);
545
546 // 统计并打印"kruskal最小生成树"的信息
547 length = 0;
548 for (i = 0; i < index; i++)
549 length += rets[i].weight;
550 printf("Kruskal=%d: ", length);
551 for (i = 0; i < index; i++)
552 printf("(%c,%c) ", rets[i].start, rets[i].end);
553 printf("\n");
554 }
555
556 /*
557 * Dijkstra最短路径。
558 * 即，统计图(G)中"顶点vs"到其它各个顶点的最短路径。
559 *
560 * 参数说明：
561 * G -- 图
562 * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
563 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
564 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
565 */
566 void dijkstra(LGraph G, int vs, int prev[], int dist[])
567 {
568 int i,j,k;
569 int min;
570 int tmp;
571 int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
572
573 // 初始化
574 for (i = 0; i < G.vexnum; i++)
575 {
576 flag[i] = 0; // 顶点i的最短路径还没获取到。
577 prev[i] = 0; // 顶点i的前驱顶点为0。
578 dist[i] = get_weight(G, vs, i); // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
579 }
580
581 // 对"顶点vs"自身进行初始化
582 flag[vs] = 1;
583 dist[vs] = 0;
584
585 // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
586 for (i = 1; i < G.vexnum; i++)
587 {
588 // 寻找当前最小的路径；
589 // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
590 min = INF;
591 for (j = 0; j < G.vexnum; j++)
592 {
593 if (flag[j]==0 && dist[j]<min)
594 {
595 min = dist[j];
596 k = j;
597 }
598 }
599 // 标记"顶点k"为已经获取到最短路径
600 flag[k] = 1;
601
602 // 修正当前最短路径和前驱顶点
603 // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
604 for (j = 0; j < G.vexnum; j++)
605 {
606 tmp = get_weight(G, k, j);
607 tmp = (tmp==INF ? INF : (min + tmp)); // 防止溢出
608 if (flag[j] == 0 && (tmp < dist[j]) )
609 {
610 dist[j] = tmp;
611 prev[j] = k;
612 }
613 }
614 }
615
616 // 打印dijkstra最短路径的结果
617 printf("dijkstra(%c): \n", G.vexs[vs].data);
618 for (i = 0; i < G.vexnum; i++)
619 printf(" shortest(%c, %c)=%d\n", G.vexs[vs].data, G.vexs[i].data, dist[i]);
620 }
621
622 void main()
623 {
624 int prev[MAX] = {0};
625 int dist[MAX] = {0};
626 LGraph* pG;
627
628 // 自定义"图"(自己输入数据)
629 //pG = create_lgraph();
630 // 采用已有的"图"
631 pG = create_example_lgraph();
632
633 //print_lgraph(*pG); // 打印图
634 //DFSTraverse(*pG); // 深度优先遍历
635 //BFS(*pG); // 广度优先遍历
636 //prim(*pG, 0); // prim算法生成最小生成树
637 //kruskal(*pG); // kruskal算法生成最小生成树
638
639 // dijkstra算法获取"第4个顶点"到其它各个顶点的最短距离
640 dijkstra(*pG, 3, prev, dist);
641 }