C प्रोग्राम में CLRS के एल्गोरिदम के अनुसार वैक्टर और क्यू का उपयोग करके BFS

परिचय

CLRS पुस्तक में BFS एल्गोरिदम को वैक्टर और क्यू का उपयोग करके वर्णित किया गया है। हमें C++ STL का उपयोग करके उस एल्गोरिदम को लागू करना है।

एल्गोरिदम

BFS(G, s)
शुरुआत
    G.V - {s} में प्रत्येक शीर्ष u के लिए
        u.color := white
        u.d := infinity
        u.p := NIL
    s.color := green
    s.d := 0
    s.p := NIL
    Q := NULL
    s को Q में डालें
    जब तक Q null नहीं है
        u = Q से हटाएं
        u से सटे प्रत्येक v के लिए
            यदि v.color = white
                v.color := green
                v.d := u.d + 1
                v.p := u
                v को Q में डालें
            अंत यदि
        अंत
        u.color = dark_green
    अंत
अंत

C++ प्रोग्राम उदाहरण

#include <iostream>
#include <vector>
#include <queue>
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);
    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);
}

आउटपुट

0 1 2 3 4 5 6