[已解决]C语言bfs寻找最短路径

wuliangtdi

代码：

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. #define MAXN 100 // 最大节点数
   
5. #define INF 0x3f3f3f3f // 无穷大
   
6. 
   
7. int n, m; // n为节点数，m为边数
   
8. int G[MAXN][MAXN]; // 邻接矩阵
   
9. int dist[MAXN]; // 距离数组
   
10. int pre[MAXN]; // 前驱节点数组
    
11. bool visited[MAXN]; // 标记数组
    
12. 
    
13. void bfs(int s) {
    
14.     for (int i = 0; i < n; i++) {
    
15.         dist[i] = INF; // 初始化距离数组
    
16.         pre[i] = -1; // 初始化前驱节点数组
    
17.         visited[i] = false; // 初始化标记数组
    
18.     }
    
19.     dist[s] = 0; // 起点距离为0
    
20.     visited[s] = true; // 起点已经访问过
    
21.     int q[MAXN], front = 0, rear = 0; // 队列及其指针
    
22.     q[rear++] = s; // 起点入队
    
23.     while (front < rear) { // 队列非空
    
24.         int u = q[front++]; // 取出队首节点
    
25.         for (int v = 0; v < n; v++) { // 遍历u的邻接点
    
26.             if (G[u][v] != INF && !visited[v]) { // 如果v是u的邻接点且未访问过
    
27.                 dist[v] = dist[u] + 1; // 更新v的距离
    
28.                 pre[v] = u; // 设置v的前驱节点为u
    
29.                 visited[v] = true; // 标记v已经访问过
    
30.                 q[rear++] = v; // v入队
    
31.             }
    
32.         }
    
33.     }
    
34. }
    
35. 
    
36. void print_path(int s, int t) {
    
37.     if (s == t) { // 如果起点和终点相同，直接输出起点
    
38.         printf("%d", s);
    
39.         return;
    
40.     }
    
41.     int path[MAXN], top = 0; // 路径数组及其指针
    
42.     for (int u = t; u != -1; u = pre[u]) { // 从终点往前遍历前驱节点
    
43.         path[top++] = u; // 将节点加入路径数组
    
44.     }
    
45.     for (int i = top - 1; i >= 0; i--) { // 输出路径上的节点
    
46.         printf("%d", path[i]);
    
47.         if (i > 0) printf("->");
    
48.     }
    
49. }
    
50. 
    
51. int main() {
    
52.     scanf("%d%d", &n, &m);
    
53.     for (int i = 0; i < n; i++) {
    
54.         for (int j = 0; j < n; j++) {
    
55.             G[i][j] = INF; // 初始化邻接矩阵
    
56.         }
    
57.     }
    
58.     while (m--) {
    
59.         int u, v;
    
60.         scanf("%d%d", &u, &v);
    
61.         G[u][v] = G[v][u] = 1; // 无向图，两个方向都要设置
    
62.     }
    
63.     int s, t;
    
64.     scanf("%d%d", &s, &t);
    
65.     bfs(s);
    
66.     printf("Shortest path from %d to %d: ", s, t);
    
67.     print_path(s, t);
    
68.     printf("\n");
    
69.     return 0;
    
70. }

复制代码

                               
登录/注册后可看大图

                               
登录/注册后可看大图