AlgoLib/BreadthFirstDirectedPaths.h at master · 4eetah/AlgoLib · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#pragma once
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

class BreadthFirstDirectedPaths
{
    using Bag = std::vector<int>;
    std::vector<bool> marked;
    std::vector<int> edgeTo;
    std::vector<int> m_distTo;

public:
    BreadthFirstDirectedPaths(Digraph& G, int s)
    : marked(G.V()), edgeTo(G.V()), m_distTo(G.V(), INT_MAX)
    {
        bfs(G, s);
    }

    BreadthFirstDirectedPaths(Digraph& G, const Bag& sources)
    : marked(G.V()), edgeTo(G.V()), m_distTo(G.V(), INT_MAX)
    {
        bfs(G, sources);
    }

    void bfs(Digraph& G, int s) {
        std::queue<int> q;
        q.push(s);
        m_distTo[s] = 0;
        marked[s] = true;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    marked[w] = true;
                    edgeTo[w] = v;
                    m_distTo[w] = m_distTo[v] + 1;
                    q.push(w);
                }
            }
        }
    }

    // breadth first search from multiple sources
    void bfs(Digraph& G, const Bag& sources) {
        std::queue<int> q;
        for (int s : sources) {
            q.push(s);
            m_distTo[s] = 0;
            marked[s] = true;
        }
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    marked[w] = true;
                    edgeTo[w] = v;
                    m_distTo[w] = m_distTo[v] + 1;
                    q.push(w);
                }
            }
        }

    }

    bool hasPathTo(int v) {
        return marked[v];
    }

    int distTo(int v) {
        return m_distTo[v];
    }

    Bag pathTo(int v) {
        if (!hasPathTo(v)) return Bag();
        Bag stack;
        int x;
        for (x = v; m_distTo[x] != 0; x = edgeTo[x])
            stack.push_back(x);
        stack.push_back(x);
        std::reverse(stack.begin(), stack.end());
        return stack;
    }
};