ในหนังสือ CLRS มีการอธิบายอัลกอริทึม BFS โดยใช้เวกเตอร์และคิว เราต้องใช้อัลกอริทึมนั้นโดยใช้ C++ STL เรามาดูอัลกอริทึมกันก่อน
อัลกอริทึม
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 ตัวอย่าง
#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
