用c语言写一个用bfs搜索所有路径的代码
时间: 2024-03-03 16:53:05 浏览: 19
下面是一个使用BFS搜索所有路径的C语言代码,它可以在一个有向图中搜索从起点到终点的所有路径:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100 // 最大顶点数
typedef struct node {
int vertex; // 顶点编号
struct node* next; // 指向下一个节点的指针
} Node;
Node* graph[MAX_VERTICES]; // 图的邻接表表示
int visited[MAX_VERTICES]; // 记录每个顶点是否已经被访问过
int path[MAX_VERTICES]; // 记录当前路径
int front = 0, rear = 0; // 队列的头指针和尾指针
int queue[MAX_VERTICES]; // 队列
int num_vertices; // 顶点数
int start_vertex, end_vertex; // 起点和终点
void add_edge(int u, int v) {
// 添加一条边 (u, v)
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->vertex = v;
new_node->next = graph[u];
graph[u] = new_node;
}
void bfs() {
// 初始化队列和visited数组
queue[rear++] = start_vertex;
visited[start_vertex] = 1;
path[0] = start_vertex;
while (front != rear) {
int vertex = queue[front++];
if (vertex == end_vertex) {
// 如果找到了终点,输出当前路径
for (int i = 0; i < rear; i++) {
printf("%d ", path[i]);
}
printf("\n");
} else {
// 否则遍历当前节点的邻居节点,并将其加入队列
for (Node* p = graph[vertex]; p != NULL; p = p->next) {
int neighbor = p->vertex;
if (!visited[neighbor]) {
visited[neighbor] = 1;
path[rear] = neighbor;
queue[rear++] = neighbor;
}
}
}
}
}
int main() {
// 读入图的顶点数和边数
scanf("%d", &num_vertices);
// 初始化图的邻接表
for (int i = 0; i < num_vertices; i++) {
graph[i] = NULL;
}
// 读入每条边,并将其添加到邻接表中
int num_edges;
scanf("%d", &num_edges);
for (int i = 0; i < num_edges; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
}
// 读入起点和终点
scanf("%d%d", &start_vertex, &end_vertex);
// 使用BFS搜索所有路径
bfs();
return 0;
}
```
注意,该代码仅适用于有向图。如果要在无向图中搜索所有路径,需要在添加边的时候同时添加反向边。