1 /** 2 * C: Dijkstra算法获取最短路径(邻接矩阵) 3 * 4 * @author skywang 5 * @date 2014/04/24 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 * 5 * @author skywang 6 * @date 2014/04/24 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 }
原文：https://www.cnblogs.com/ranzhong/p/13738611.html