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

Jianbaiyi

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

最佳答案

月排行榜 / 总排行榜

wuliangtdi

2023-4-18 18:19:46

代码：

#include <stdio.h>
#include <stdbool.h>

#define MAXN 100 // 最大节点数
#define INF 0x3f3f3f3f // 无穷大

int n, m; // n为节点数，m为边数
int G[MAXN][MAXN]; // 邻接矩阵
int dist[MAXN]; // 距离数组
int pre[MAXN]; // 前驱节点数组
bool visited[MAXN]; // 标记数组

void bfs(int s) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF; // 初始化距离数组
        pre[i] = -1; // 初始化前驱节点数组
        visited[i] = false; // 初始化标记数组
    }
    dist[s] = 0; // 起点距离为0
    visited[s] = true; // 起点已经访问过
    int q[MAXN], front = 0, rear = 0; // 队列及其指针
    q[rear++] = s; // 起点入队
    while (front < rear) { // 队列非空
        int u = q[front++]; // 取出队首节点
        for (int v = 0; v < n; v++) { // 遍历u的邻接点
            if (G[u][v] != INF && !visited[v]) { // 如果v是u的邻接点且未访问过
                dist[v] = dist[u] + 1; // 更新v的距离
                pre[v] = u; // 设置v的前驱节点为u
                visited[v] = true; // 标记v已经访问过
                q[rear++] = v; // v入队
            }
        }
    }
}

void print_path(int s, int t) {
    if (s == t) { // 如果起点和终点相同，直接输出起点
        printf("%d", s);
        return;
    }
    int path[MAXN], top = 0; // 路径数组及其指针
    for (int u = t; u != -1; u = pre[u]) { // 从终点往前遍历前驱节点
        path[top++] = u; // 将节点加入路径数组
    }
    for (int i = top - 1; i >= 0; i--) { // 输出路径上的节点
        printf("%d", path[i]);
        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[i][j] = INF; // 初始化邻接矩阵
        }
    }
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u][v] = G[v][u] = 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;
}

                               
登录/注册后可看大图

                               
登录/注册后可看大图

跳转到最佳答案楼层

歌者文明清理员

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

#include <stdio.h>
#define MAX_N 100

int map[MAX_N][MAX_N];   // 存储地图的邻接矩阵
int pre[MAX_N];          // 存储每个节点的前驱节点
int visited[MAX_N];      // 记录节点是否已经被访问过

typedef struct queue{
    int data[MAX_N];
    int head, tail;
} Queue;

// 初始化队列
void initQueue(Queue *q){
    q->head = q->tail = 0;
}

// 入队
void enqueue(Queue *q, int value){
    q->data[q->tail++] = value;
}

// 出队
int dequeue(Queue *q){
    return q->data[q->head++];
}

// BFS遍历，查找最短路径
int bfs(int n, int start, int end){
    Queue q;
    initQueue(&q);
    visited[start] = 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[cur][i]==1 && visited[i]==0){
                visited[i] = 1;     // 标记为访问过
                pre[i] = cur;        // 记录i的前驱节点是cur
                enqueue(&q, i);      // 将i加入队列
            }
        }
    }

    // 构造路径
    int path[MAX_N];
    int len = 0;
    while (end != start){
        path[len++] = end;  // 将当前节点加入路径数组
        end = pre[end];     // 更新为前驱节点
    }
    path[len++] = start;    // 将起点加入数组

    // 输出路径
    for (int i=len-1; i>=0; i--){
        printf("%d ", path[i]);
    }
    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[a][b] = map[b][a] = 1;
    }

    int start, end;
    scanf("%d%d", &start, &end);

    printf("最短路径是：");
    bfs(n, start, end);

    return 0;
}

说明：

• 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）来找到并显示无向图中两个顶点之间的最短路径。这个实现假定您已经使用了一个邻接表来表示图。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_NODES 100

typedef struct Queue {
    int items[MAX_NODES];
    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[][num_nodes], 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[num_nodes][num_nodes];
    for (int i = 0; i < num_nodes; i++) {
        for (int j = 0; j < num_nodes; j++) {
            adj[i][j] = 0;
        }
    }

    printf("Enter the edges:\n");
    for (int i = 0; i < num_edges; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u][v] = adj[v][u] = 1;
    }

    int start, target;
    printf("Enter the starting and target nodes: ");
    scanf("%d%d", &start, &target);

    int path[MAX_NODES];
    for (int i = 0; i < MAX_NODES; i++) {
        path[i] = -1;
    }

    bfs(start, target, num_nodes, adj, path);

    printf("Shortest Path: ");
    if (path[target] != -1) {
        int node = target;
        while (node != start) {
            printf("%d <- ", node);
            node = path[node];
        }
        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[q->rear] = value;
    }
}

int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        item = -1;
    } else {
        item = q->items[q->front];
        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[][num_nodes], int path[]) {
    Queue* q = createQueue();
    bool visited[num_nodes];

    for (int i = 0; i < num_nodes; i++) {
        visited[i] = false;
    }

    visited[start] = true;
    enqueue(q, start);

    while (!isEmpty(q)) {
        int current = dequeue(q);

        for (int i = 0; i < num_nodes; i++) {
            if (adj[current][i] && !visited[i]) {
                visited[i] = true;
                enqueue(q, i);
                path[i] = current;
                if (i == target) {
                    break;
                }
            }
        }
    }
    free(q);
}

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

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

wuliangtdi

代码：

#include <stdio.h>
#include <stdbool.h>

#define MAXN 100 // 最大节点数
#define INF 0x3f3f3f3f // 无穷大

int n, m; // n为节点数，m为边数
int G[MAXN][MAXN]; // 邻接矩阵
int dist[MAXN]; // 距离数组
int pre[MAXN]; // 前驱节点数组
bool visited[MAXN]; // 标记数组

void bfs(int s) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF; // 初始化距离数组
        pre[i] = -1; // 初始化前驱节点数组
        visited[i] = false; // 初始化标记数组
    }
    dist[s] = 0; // 起点距离为0
    visited[s] = true; // 起点已经访问过
    int q[MAXN], front = 0, rear = 0; // 队列及其指针
    q[rear++] = s; // 起点入队
    while (front < rear) { // 队列非空
        int u = q[front++]; // 取出队首节点
        for (int v = 0; v < n; v++) { // 遍历u的邻接点
            if (G[u][v] != INF && !visited[v]) { // 如果v是u的邻接点且未访问过
                dist[v] = dist[u] + 1; // 更新v的距离
                pre[v] = u; // 设置v的前驱节点为u
                visited[v] = true; // 标记v已经访问过
                q[rear++] = v; // v入队
            }
        }
    }
}

void print_path(int s, int t) {
    if (s == t) { // 如果起点和终点相同，直接输出起点
        printf("%d", s);
        return;
    }
    int path[MAXN], top = 0; // 路径数组及其指针
    for (int u = t; u != -1; u = pre[u]) { // 从终点往前遍历前驱节点
        path[top++] = u; // 将节点加入路径数组
    }
    for (int i = top - 1; i >= 0; i--) { // 输出路径上的节点
        printf("%d", path[i]);
        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[i][j] = INF; // 初始化邻接矩阵
        }
    }
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u][v] = G[v][u] = 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;
}

                               
登录/注册后可看大图

                               
登录/注册后可看大图

wangxiangtan2

我去，這ChatGPT出了大力了