BFS sử dụng vectơ &hàng đợi theo thuật toán của CLRS trong Chương trình C?

Trong cuốn sách CLRS, thuật toán BFS được mô tả bằng cách sử dụng vectơ và hàng đợi. Chúng ta phải thực hiện thuật toán đó bằng cách sử dụng C ++ STL. Đầu tiên, hãy để chúng tôi xem thuật toán.

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

0 1 2 3 4 5 6