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