BFS dùng vector và queue theo thuật toán CLRS trong C

Triển khai BFS theo sách CLRS dùng vector và queue STL C++.

Thuật toán CLRS

BFS(G, s)
    VỚI u IN G.V - {s}: color=white, d=inf, p=NIL
    s.color=gray, s.d=0, s.p=NIL
    Q = {s}
    KHI Q KHÔNG RỖNG
        u = DEQUEUE(Q)
        VỚI v KẺ VỚI u
            NẾU v.color == white
                v.color=gray, v.d=u.d+1, v.p=u
                ENQUEUE(Q, v)
        u.color=black
KẾT THÚC

Chương trình C++ ví dụ

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

vector colour;
vector dist, par;

void addEdge(vector g[], int u, int v) {
    g[u].push_back(v); g[v].push_back(u);
}

void BFS(vector g[], int s) {
    queue q; q.push(s);
    dist[s] = 0; colour[s] = "gray";
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (auto i = g[u].begin(); i != g[u].end(); i++) {
            if (colour[*i] == "white") {
                colour[*i] = "gray";
                dist[*i] = dist[u] + 1;
                par[*i] = u;
                q.push(*i);
            }
        }
        colour[u] = "black";
    }
}

void BFSAlgo(vector g[], int n) {
    colour.assign(n, "white");
    dist.assign(n, 0);
    par.assign(n, -1);
    for (int i = 0; i < n; i++)
        if (colour[i] == "white") BFS(g, i);
}

int main() {
    int n = 7;
    vector g[n];
    addEdge(g,0,1); addEdge(g,0,2); addEdge(g,1,3);
    addEdge(g,1,4); addEdge(g,2,5); addEdge(g,2,6);
    BFSAlgo(g, n);
}

Kết quả

0 1 2 3 4 5 6