C语言bfs寻找最短路径
不是要显示距离，要把怎么走的显示出来，求助！！！ 本帖最后由 歌者文明清理员 于 2023-4-18 17:18 编辑以下是C语言实现BFS寻找最短路径并将路径显示出来的示例代码：
#include <stdio.h>
#define MAX_N 100
int map; // 存储地图的邻接矩阵
int pre; // 存储每个节点的前驱节点
int visited; // 记录节点是否已经被访问过
typedef struct queue{
int data;
int head, tail;
} Queue;
// 初始化队列
void initQueue(Queue *q){
q->head = q->tail = 0;
}
// 入队
void enqueue(Queue *q, int value){
q->data = value;
}
// 出队
int dequeue(Queue *q){
return q->data;
}
// BFS遍历，查找最短路径
int bfs(int n, int start, int end){
Queue q;
initQueue(&q);
visited = 1;// 将起点标记为访问过
enqueue(&q, start);// 将其加入队列
while (q.head != q.tail){// 判断队列是否为空
int cur = dequeue(&q);// 将队首元素出队
if (cur == end) break;// 找到了终点，退出循环
for (int i=1; i<=n; i++){
// 如果当前节点与i相邻且i没有被访问过
if (map==1 && visited==0){
visited = 1; // 标记为访问过
pre = cur; // 记录i的前驱节点是cur
enqueue(&q, i); // 将i加入队列
}
}
}
// 构造路径
int path;
int len = 0;
while (end != start){
path = end;// 将当前节点加入路径数组
end = pre; // 更新为前驱节点
}
path = start; // 将起点加入数组
// 输出路径
for (int i=len-1; i>=0; i--){
printf("%d ", path);
}
printf("\n");
return len - 1;// 返回路径长度
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
// 读入地图信息，构造邻接矩阵
for (int i=1; i<=m; i++){
int a, b;
scanf("%d%d", &a, &b);
map = map = 1;
}
int start, end;
scanf("%d%d", &start, &end);
printf("最短路径是：");
bfs(n, start, end);
return 0;
}
说明：
[*]map 是一个二维数组，用于存储地图的邻接矩阵。如果map为1，则表示第i个节点与第j个节点相邻；否则表示不相邻。
[*]pre 是一个一维数组，用于存储每个节点的前驱节点。在BFS过程中，如果发现节点i的前驱节点是节点j，则将 pre设为j。
[*]visited 是一个一维数组，用于记录每个节点是否已经被访问过。初始时，将起点标记为已访问过。
[*]Queue 是一个结构体，包含一个整型数组和两个指针 head、tail，分别指向队列头部和尾部。initQueue 函数用于初始化队列，enqueue 函数用于入队，dequeue 函数用于出队。在本示例中，我们采用数组实现队列。
[*]在 BFS 过程中，我们从起点开始遍历地图，将访问过的节点加入队列。在遍历过程中，我们记录每个节点的前驱节点，直到找到了终点或队列为空。如果找到了终点，则构造路径并输出。
注意事项：
[*]本示例中，在构造路径时使用了逆序输出方式。具体来说，我们先将终点加入路径数组，然后沿着前驱节点逐步往回推导，最终得到完整路径，并按照从起点到终点的顺序输出。
[*]本示例中没有考虑输入数据是否合法，比如节点编号是否越界、起点和终点是否为同一节点等。在实际编程中，建议添加相应的输入检查处理。
以下是一个基本的C语言实现，使用广度优先搜索（BFS）来找到并显示无向图中两个顶点之间的最短路径。这个实现假定您已经使用了一个邻接表来表示图。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_NODES 100
typedef struct Queue {
int items;
int front;
int rear;
} Queue;
Queue* createQueue();
void enqueue(Queue* q, int value);
int dequeue(Queue* q);
int isEmpty(Queue* q);
void bfs(int start, int target, int num_nodes, int adj[], int path[]);
int main() {
int num_nodes, num_edges;
printf("Enter the number of nodes and edges: ");
scanf("%d%d", &num_nodes, &num_edges);
int adj;
for (int i = 0; i < num_nodes; i++) {
for (int j = 0; j < num_nodes; j++) {
adj = 0;
}
}
printf("Enter the edges:\n");
for (int i = 0; i < num_edges; i++) {
int u, v;
scanf("%d%d", &u, &v);
adj = adj = 1;
}
int start, target;
printf("Enter the starting and target nodes: ");
scanf("%d%d", &start, &target);
int path;
for (int i = 0; i < MAX_NODES; i++) {
path = -1;
}
bfs(start, target, num_nodes, adj, path);
printf("Shortest Path: ");
if (path != -1) {
int node = target;
while (node != start) {
printf("%d <- ", node);
node = path;
}
printf("%d\n", start);
} else {
printf("No path found.\n");
}
return 0;
}
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = -1;
q->rear = -1;
return q;
}
void enqueue(Queue* q, int value) {
if (q->rear == MAX_NODES - 1)
return;
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items = value;
}
}
int dequeue(Queue* q) {
int item;
if (isEmpty(q)) {
item = -1;
} else {
item = q->items;
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
}
return item;
}
int isEmpty(Queue* q) {
return q->rear == -1;
}
void bfs(int start, int target, int num_nodes, int adj[], int path[]) {
Queue* q = createQueue();
bool visited;
for (int i = 0; i < num_nodes; i++) {
visited = false;
}
visited = true;
enqueue(q, start);
while (!isEmpty(q)) {
int current = dequeue(q);
for (int i = 0; i < num_nodes; i++) {
if (adj && !visited) {
visited = true;
enqueue(q, i);
path = current;
if (i == target) {
break;
}
}
}
}
free(q);
}
这个程序首先读取节点和边的数量，并初始化一个邻接矩阵。然后，它从用户处获取边和起始节点、目标节点的信息。最后，它使用BFS算法找到最短路径，并将其打印出来。
请注意，此实现仅适用于无向图，并且不支持带有权重的边。对于有向图和带权重的边的图，请考虑使用其他算法，如Dijkstra算法。
代码：
#include <stdio.h>
#include <stdbool.h>
#define MAXN 100 // 最大节点数
#define INF 0x3f3f3f3f // 无穷大
int n, m; // n为节点数，m为边数
int G; // 邻接矩阵
int dist; // 距离数组
int pre; // 前驱节点数组
bool visited; // 标记数组
void bfs(int s) {
for (int i = 0; i < n; i++) {
dist = INF; // 初始化距离数组
pre = -1; // 初始化前驱节点数组
visited = false; // 初始化标记数组
}
dist = 0; // 起点距离为0
visited = true; // 起点已经访问过
int q, front = 0, rear = 0; // 队列及其指针
q = s; // 起点入队
while (front < rear) { // 队列非空
int u = q; // 取出队首节点
for (int v = 0; v < n; v++) { // 遍历u的邻接点
if (G != INF && !visited) { // 如果v是u的邻接点且未访问过
dist = dist + 1; // 更新v的距离
pre = u; // 设置v的前驱节点为u
visited = true; // 标记v已经访问过
q = v; // v入队
}
}
}
}
void print_path(int s, int t) {
if (s == t) { // 如果起点和终点相同，直接输出起点
printf("%d", s);
return;
}
int path, top = 0; // 路径数组及其指针
for (int u = t; u != -1; u = pre) { // 从终点往前遍历前驱节点
path = u; // 将节点加入路径数组
}
for (int i = top - 1; i >= 0; i--) { // 输出路径上的节点
printf("%d", path);
if (i > 0) printf("->");
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
G = INF; // 初始化邻接矩阵
}
}
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
G = G = 1; // 无向图，两个方向都要设置
}
int s, t;
scanf("%d%d", &s, &t);
bfs(s);
printf("Shortest path from %d to %d: ", s, t);
print_path(s, t);
printf("\n");
return 0;
}
https://i.328888.xyz/2023/04/18/i6kF8y.png
https://i.328888.xyz/2023/04/18/i6koMH.png 我去，這ChatGPT出了大力了
页:
[1]