Laksanakan BFS menggunakan vektor dan baris gilir, dan laksanakan algoritma CLRS dalam program C

Dalam buku CLRS, algoritma BFS diterangkan menggunakan vektor dan baris gilir. Kita perlu menggunakan C++ STL untuk melaksanakan algoritma ini. Mula-mula mari kita lihat algoritma. Terjemahan bahasa Cina bagi

algoritma

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

Contoh

ialah:

Contoh

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

Output

rreee

Atas ialah kandungan terperinci Laksanakan BFS menggunakan vektor dan baris gilir, dan laksanakan algoritma CLRS dalam program C. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!