बीएफएस सी प्रोग्राम में सीएलआरएस के एल्गोरिदम के अनुसार वैक्टर और कतार का उपयोग कर रहा है?

CLRS बुक में बीएफएस एल्गोरिथम को वैक्टर और क्यू का उपयोग करके वर्णित किया गया है। हमें सी ++ एसटीएल का उपयोग करके उस एल्गोरिदम को लागू करना होगा। आइए पहले एल्गोरिथम देखें।

एल्गोरिदम

बीएफएस (जी, एस) -

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

उदाहरण

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<string> colour;
vector<int> dist;
vector<int> par;
void addEdge(vector <int> g[], int u, int v) { //add edge to form the graph
   g[u].push_back(v);
   g[v].push_back(u);
}
void BFS(vector <int> g[], int s) {
   queue<int> q;
   q.push(s); //insert source
   dist[s] = 0;
   colour[s] = "gray";
   while (!q.empty()) {
      int u = q.front(); //top element from queue, then delete it
      q.pop();
      cout << u << " ";
      for (auto i = g[u].begin(); i != g[u].end(); i++) {
         if (colour[*i] == "white") { //white is unvisited node
            colour[*i] = "gray"; //gray is visited but not completed
            dist[*i] = dist[u] + 1;
            par[*i] = u;
            q.push(*i);
         }
      }
      colour[u] = "black"; //black is completed node
   }
}
void BFSAlgo(vector <int> g[], int n) {
   colour.assign(n, "white"); //put as unvisited
   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 <int> 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