在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
endExample
的中文翻译为：示例
#include#include #include using namespace std; vector colour; vector dist; vector par; void addEdge(vector g[], int u, int v) { //add edge to form the graph g[u].push_back(v); g[v].push_back(u); } void BFS(vector g[], int s) { queue 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 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 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
