BFS ใช้เวกเตอร์และคิวตามอัลกอริทึม CLRS ในโปรแกรม C

ในหนังสือ CLRS อธิบายอัลกอริทึม BFS ใช้เวกเตอร์และคิว ต้องนำไปสู่ C++ STL

อัลกอริทึม

BFS(G, s) -

begin
  for each vertex u in G.V - {s}, do
    u.color := white
    u.d := infinity
    u.p := NIL
  done
  s.color := green
  s.d := 0
  s.p := NIL
  Q := NULL
  insert s into Q
  while Q is not null, do
    u = delete from Q
    for each v in adjacent to u, do
      if v.color = white
        v.color := green
        v.d := u.d + 1
        v.p := u
        insert v into Q
      end if
    done
    u.color = dark_green
  done
end

ตัวอย่างโค้ด C++

#include
#include
#include
using namespace std;
vector colour;
vector dist;
vector 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); // แทรก source
    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") { // white คือโหนดยังไม่เยี่ยมชม
                colour[*i] = "gray"; // gray คือเยี่ยมชมแล้วแต่ยังไม่เสร็จ
                dist[*i] = dist[u] + 1;
                par[*i] = u;
                q.push(*i);
            }
        }
        colour[u] = "black"; // 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);
}

ผลลัพธ์

0 1 2 3 4 5 6