C++ প্রোগ্রামে CLRS অ্যালগরিদম অনুসারে BFS ইমপ্লিমেন্টেশন

ভূমিকা

CLRS বইয়ে বর্ণিত BFS অ্যালগরিদমকে C++ STL (vector, queue) ব্যবহার করে ইমপ্লিমেন্ট করা হয়েছে। রঙ (color), দূরত্ব (distance), প্যারেন্ট (parent) ট্র্যাক করে গ্রাফ ট্রাভার্সাল করা হয়।

এলগরিদম (CLRS BFS)

BFS(G, s)
শুরু
  সব u ∈ V-{s} এর জন্য: color=white, d=∞, p=NIL
  s: color=gray, d=0, p=NIL
  Q = {s}
  যতক্ষণ Q খালি নয়:
    u = Q.dequeue()
    প্রতিটি v ∈ Adj[u] এর জন্য:
      যদি v.color == white:
        v.color = gray, v.d = u.d+1, v.p = u, Q.enqueue(v)
    u.color = black
শেষ

C++ প্রোগ্রাম উদাহরণ

#include 
#include 
#include 
using namespace std;

vector color;
vector dist, parent;

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; color[s] = "gray";
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (auto v : g[u]) {
            if (color[v] == "white") {
                color[v] = "gray";
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
        color[u] = "black";
    }
}

void BFSAlgo(vector g[], int n) {
    color.assign(n, "white");
    dist.assign(n, 0);
    parent.assign(n, -1);
    for (int i = 0; i < n; i++)
        if (color[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);
    return 0;
}

আউটপুট

0 1 2 3 4 5 6