bfs path

ソースコード

 1#include <vector>
 2#include <algorithm>
 3#include <queue>
 4using namespace std;
 5
 6// bfs_path
 7namespace titan23 {
 8
 9    vector<int> bfs_path(const vector<vector<int>> &G, int s, int t) {
10        int n = G.size();
11        vector<int> prev(n, -1);
12        const int inf = 1e9;
13        vector<int> dist(n, inf);
14        dist[s] = 0;
15        queue<int> todo;
16        todo.emplace(s);
17        while (!todo.empty()) {
18            int v = todo.front();
19            todo.pop();
20            for (const int x : G[v]) {
21                if (dist[x] == inf) {
22                    dist[x] = dist[v] + 1;
23                    prev[x] = v;
24                    todo.emplace(x);
25                }
26            }
27        }
28        if (dist[t] == inf) {
29            return {};
30        }
31        vector<int> path;
32        while (prev[t] != -1) {
33            path.emplace_back(t);
34            t = prev[t];
35        }
36        path.emplace_back(t);
37        reverse(path.begin(), path.end());
38        return path;
39    }
40}

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/bfs_path.cpp