[已解决]C语言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算法。