您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言問答

C語言 BFS 最短路徑路徑記錄：前驅數組法完整實現

編輯：C 語言問答

BFS 最短路徑不僅求長度，還要輸出具體路徑

核心思想：前驅數組 (Parent/Predecessor Array)

BFS 遍歷時，對於每個被發現的節點 v，記錄它是從哪個節點 u 到達的：parent[v] = u。找到目標後，從目標沿 parent 回溯到起點，逆序即為最短路徑。

數據結構

#define MAX_N 1000
#define MAX_M 10000

// 鄰接表 (稀疏圖)
int head[MAX_N], to[MAX_M], nxt[MAX_M], ecnt = 0;
void add_edge(int u, int v) { to[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++; }

// BFS 輔助
int q[MAX_N], qh, qt;
int dist[MAX_N];
int parent[MAX_N];  // 關鍵：記錄前驅節點
int inq[MAX_N];     // 或用 dist 初始化為 -1 判斷未訪問

BFS 模板 (記錄路徑版)

void bfs(int start, int target, int n) {
    for (int i = 0; i < n; ++i) { dist[i] = -1; parent[i] = -1; }
    qh = qt = 0;
    q[qt++] = start;
    dist[start] = 0;
    parent[start] = -1;  // 起點無前驅

    while (qh < qt) {
        int u = q[qh++];
        if (u == target) break;  // 找到目標可提前結束
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;  // 記錄前驅
                q[qt++] = v;
            }
        }
    }
}

路徑重構與輸出

void print_path(int start, int target) {
    if (dist[target] == -1) { printf("不可達\n"); return; }
    int path[MAX_N], len = 0;
    for (int v = target; v != -1; v = parent[v])
        path[len++] = v;
    printf("最短距離: %d\n路徑: ", dist[target]);
    for (int i = len - 1; i >= 0; --i) {
        printf("%d", path[i]);
        if (i) printf(" -> ");
    }
    putchar('\n');
}

迷宮專用 (網格圖，四向移動)

#define MAX_R 100
#define MAX_C 100
char maze[MAX_R][MAX_C];
int dist[MAX_R][MAX_C];
int px[MAX_R][MAX_C], py[MAX_R][MAX_C];  // 前驅坐標

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
char *dir_str[4] = {"上", "右", "下", "左"};

void maze_bfs(int sx, int sy, int tx, int ty, int R, int C) {
    // 初始化 dist = -1
    int qx[MAX_R*MAX_C], qy[MAX_R*MAX_C], qh=0, qt=0;
    qx[qt] = sx; qy[qt] = sy; qt++;
    dist[sx][sy] = 0; px[sx][sy] = -1;

    while (qh < qt) {
        int x = qx[qh], y = qy[qh]; qh++;
        if (x == tx && y == ty) break;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx<0||nx>=R||ny<0||ny>=C) continue;
            if (maze[nx][ny] == '#') continue;  // 牆
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            px[nx][ny] = x; py[nx][ny] = y;
            qx[qt] = nx; qy[qt] = ny; qt++;
        }
    }
}

void print_maze_path(int tx, int ty) {
    if (dist[tx][ty] == -1) { printf("無路徑\n"); return; }
    char moves[10000]; int ml = 0;
    int x = tx, y = ty;
    while (px[x][y] != -1) {
        int px_ = px[x][y], py_ = py[x][y];
        for (int d = 0; d < 4; ++d)
            if (px_ + dx[d] == x && py_ + dy[d] == y)
                moves[ml++] = d;  // 記錄方向索引
        x = px_; y = py_;
    }
    printf("步數: %d\n路徑: ", ml);
    for (int i = ml-1; i >= 0; --i) printf("%s ", dir_str[moves[i]]);
    putchar('\n');
}