[AtCoder][ABC168D] BFS探索における経路復元

概要

重みづけなしグラフにおける最短経路はBFSを使うことで求めることができる。
またそのときの経路の復元方法を説明する。

手順としてはBFSをしつつ１つ前の頂点を配列に記憶する。

BFS適用

vector<int> prev(N, -2); // -2は経路未確定を示す
prev[0] = -1; // -1はこれ以上戻れないことを示す
queue<int> q;
q.push(0);
while (!q.empty()) {
    int current = q.front(); q.pop();
    for (int next: E[current]) {
        if (prev[next] >= -1) continue;
        prev[next] = current;
        q.push(next);
    }
}

経路を復元するには-1にあたるまでprev配列を戻っていけばよい。

経路復元

int current = 3; // 頂点3までの最短経路を復元する。
while (current != -1) {
    cout << current << " ";
    current = prev[current];
}

練習問題

この問題を解いてみる。
ABC168 D - .. (Double Dots)

内容としてはグラフが与えられるので頂点1から各頂点への最短経路を求めて、各頂点から１つ前の頂点を出力する。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> E(N, vector<int>());

    for (int i=0; i<M; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    vector<int> prev(N, -2);
    prev[0] = -1;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int current = q.front(); q.pop();
        for (int next: E[current]) {
            if (prev[next] >= -1) continue;
            prev[next] = current;
            q.push(next);
        }
    }

    for (int a: prev) {
        if (a == -2) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    for (int i=1; i<N; i++) {
        cout << prev[i]+1 << endl;
    }
}