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

Jianbaiyi

不是要显示距离，要把怎么走的显示出来，求助！！！

最佳答案

月排行榜 / 总排行榜

wuliangtdi

2023-4-18 18:19:46

代码：

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. }

复制代码

                               
登录/注册后可看大图

                               
登录/注册后可看大图

跳转到最佳答案楼层

歌者文明清理员

以下是C语言实现BFS寻找最短路径并将路径显示出来的示例代码：

1. #include <stdio.h>
   
2. #define MAX_N 100
   
3. 
   
4. int map[MAX_N][MAX_N];   // 存储地图的邻接矩阵
   
5. int pre[MAX_N];          // 存储每个节点的前驱节点
   
6. int visited[MAX_N];      // 记录节点是否已经被访问过
   
7. 
   
8. typedef struct queue{
   
9.     int data[MAX_N];
   
10.     int head, tail;
    
11. } Queue;
    
12. 
    
13. // 初始化队列
    
14. void initQueue(Queue *q){
    
15.     q->head = q->tail = 0;
    
16. }
    
17. 
    
18. // 入队
    
19. void enqueue(Queue *q, int value){
    
20.     q->data[q->tail++] = value;
    
21. }
    
22. 
    
23. // 出队
    
24. int dequeue(Queue *q){
    
25.     return q->data[q->head++];
    
26. }
    
27. 
    
28. // BFS遍历，查找最短路径
    
29. int bfs(int n, int start, int end){
    
30.     Queue q;
    
31.     initQueue(&q);
    
32.     visited[start] = 1;  // 将起点标记为访问过
    
33.     enqueue(&q, start);  // 将其加入队列
    
34. 
    
35.     while (q.head != q.tail){  // 判断队列是否为空
    
36.         int cur = dequeue(&q);  // 将队首元素出队
    
37.         if (cur == end) break;  // 找到了终点，退出循环
    
38. 
    
39.         for (int i=1; i<=n; i++){
    
40.             // 如果当前节点与i相邻且i没有被访问过
    
41.             if (map[cur][i]==1 && visited[i]==0){
    
42.                 visited[i] = 1;     // 标记为访问过
    
43.                 pre[i] = cur;        // 记录i的前驱节点是cur
    
44.                 enqueue(&q, i);      // 将i加入队列
    
45.             }
    
46.         }
    
47.     }
    
48. 
    
49.     // 构造路径
    
50.     int path[MAX_N];
    
51.     int len = 0;
    
52.     while (end != start){
    
53.         path[len++] = end;  // 将当前节点加入路径数组
    
54.         end = pre[end];     // 更新为前驱节点
    
55.     }
    
56.     path[len++] = start;    // 将起点加入数组
    
57. 
    
58.     // 输出路径
    
59.     for (int i=len-1; i>=0; i--){
    
60.         printf("%d ", path[i]);
    
61.     }
    
62.     printf("\n");
    
63. 
    
64.     return len - 1;  // 返回路径长度
    
65. }
    
66. 
    
67. int main(){
    
68.     int n, m;
    
69.     scanf("%d%d", &n, &m);
    
70. 
    
71.     // 读入地图信息，构造邻接矩阵
    
72.     for (int i=1; i<=m; i++){
    
73.         int a, b;
    
74.         scanf("%d%d", &a, &b);
    
75.         map[a][b] = map[b][a] = 1;
    
76.     }
    
77. 
    
78.     int start, end;
    
79.     scanf("%d%d", &start, &end);
    
80. 
    
81.     printf("最短路径是：");
    
82.     bfs(n, start, end);
    
83. 
    
84.     return 0;
    
85. }

复制代码

说明：

• map 是一个二维数组，用于存储地图的邻接矩阵。如果map[i ][j]为1，则表示第i个节点与第j个节点相邻；否则表示不相邻。
• pre 是一个一维数组，用于存储每个节点的前驱节点。在BFS过程中，如果发现节点i的前驱节点是节点j，则将 pre[i ]设为j。
• visited 是一个一维数组，用于记录每个节点是否已经被访问过。初始时，将起点标记为已访问过。
• Queue 是一个结构体，包含一个整型数组和两个指针 head、tail，分别指向队列头部和尾部。initQueue 函数用于初始化队列，enqueue 函数用于入队，dequeue 函数用于出队。在本示例中，我们采用数组实现队列。
• 在 BFS 过程中，我们从起点开始遍历地图，将访问过的节点加入队列。在遍历过程中，我们记录每个节点的前驱节点，直到找到了终点或队列为空。如果找到了终点，则构造路径并输出。
  

注意事项：

• 本示例中，在构造路径时使用了逆序输出方式。具体来说，我们先将终点加入路径数组，然后沿着前驱节点逐步往回推导，最终得到完整路径，并按照从起点到终点的顺序输出。
• 本示例中没有考虑输入数据是否合法，比如节点编号是否越界、起点和终点是否为同一节点等。在实际编程中，建议添加相应的输入检查处理。
  

isdkz

以下是一个基本的C语言实现，使用广度优先搜索（BFS）来找到并显示无向图中两个顶点之间的最短路径。这个实现假定您已经使用了一个邻接表来表示图。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <stdbool.h>
   
4. 
   
5. #define MAX_NODES 100
   
6. 
   
7. typedef struct Queue {
   
8.     int items[MAX_NODES];
   
9.     int front;
   
10.     int rear;
    
11. } Queue;
    
12. 
    
13. Queue* createQueue();
    
14. void enqueue(Queue* q, int value);
    
15. int dequeue(Queue* q);
    
16. int isEmpty(Queue* q);
    
17. 
    
18. void bfs(int start, int target, int num_nodes, int adj[][num_nodes], int path[]);
    
19. 
    
20. int main() {
    
21.     int num_nodes, num_edges;
    
22.     printf("Enter the number of nodes and edges: ");
    
23.     scanf("%d%d", &num_nodes, &num_edges);
    
24. 
    
25.     int adj[num_nodes][num_nodes];
    
26.     for (int i = 0; i < num_nodes; i++) {
    
27.         for (int j = 0; j < num_nodes; j++) {
    
28.             adj[i][j] = 0;
    
29.         }
    
30.     }
    
31. 
    
32.     printf("Enter the edges:\n");
    
33.     for (int i = 0; i < num_edges; i++) {
    
34.         int u, v;
    
35.         scanf("%d%d", &u, &v);
    
36.         adj[u][v] = adj[v][u] = 1;
    
37.     }
    
38. 
    
39.     int start, target;
    
40.     printf("Enter the starting and target nodes: ");
    
41.     scanf("%d%d", &start, &target);
    
42. 
    
43.     int path[MAX_NODES];
    
44.     for (int i = 0; i < MAX_NODES; i++) {
    
45.         path[i] = -1;
    
46.     }
    
47. 
    
48.     bfs(start, target, num_nodes, adj, path);
    
49. 
    
50.     printf("Shortest Path: ");
    
51.     if (path[target] != -1) {
    
52.         int node = target;
    
53.         while (node != start) {
    
54.             printf("%d <- ", node);
    
55.             node = path[node];
    
56.         }
    
57.         printf("%d\n", start);
    
58.     } else {
    
59.         printf("No path found.\n");
    
60.     }
    
61. 
    
62.     return 0;
    
63. }
    
64. 
    
65. Queue* createQueue() {
    
66.     Queue* q = (Queue*)malloc(sizeof(Queue));
    
67.     q->front = -1;
    
68.     q->rear = -1;
    
69.     return q;
    
70. }
    
71. 
    
72. void enqueue(Queue* q, int value) {
    
73.     if (q->rear == MAX_NODES - 1)
    
74.         return;
    
75.     else {
    
76.         if (q->front == -1)
    
77.             q->front = 0;
    
78.         q->rear++;
    
79.         q->items[q->rear] = value;
    
80.     }
    
81. }
    
82. 
    
83. int dequeue(Queue* q) {
    
84.     int item;
    
85.     if (isEmpty(q)) {
    
86.         item = -1;
    
87.     } else {
    
88.         item = q->items[q->front];
    
89.         q->front++;
    
90.         if (q->front > q->rear) {
    
91.             q->front = q->rear = -1;
    
92.         }
    
93.     }
    
94.     return item;
    
95. }
    
96. 
    
97. int isEmpty(Queue* q) {
    
98.     return q->rear == -1;
    
99. }
    
100. 
     
101. void bfs(int start, int target, int num_nodes, int adj[][num_nodes], int path[]) {
     
102.     Queue* q = createQueue();
     
103.     bool visited[num_nodes];
     
104. 
     
105.     for (int i = 0; i < num_nodes; i++) {
     
106.         visited[i] = false;
     
107.     }
     
108. 
     
109.     visited[start] = true;
     
110.     enqueue(q, start);
     
111. 
     
112.     while (!isEmpty(q)) {
     
113.         int current = dequeue(q);
     
114. 
     
115.         for (int i = 0; i < num_nodes; i++) {
     
116.             if (adj[current][i] && !visited[i]) {
     
117.                 visited[i] = true;
     
118.                 enqueue(q, i);
     
119.                 path[i] = current;
     
120.                 if (i == target) {
     
121.                     break;
     
122.                 }
     
123.             }
     
124.         }
     
125.     }
     
126.     free(q);
     
127. }

复制代码

这个程序首先读取节点和边的数量，并初始化一个邻接矩阵。然后，它从用户处获取边和起始节点、目标节点的信息。最后，它使用BFS算法找到最短路径，并将其打印出来。

请注意，此实现仅适用于无向图，并且不支持带有权重的边。对于有向图和带权重的边的图，请考虑使用其他算法，如Dijkstra算法。

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. }

复制代码

                               
登录/注册后可看大图

                               
登录/注册后可看大图

wangxiangtan2

我去，這ChatGPT出了大力了