[알고리즘] BFS - Breadth First Search

너비 우선 검색 기법은 그래프를 검색하거나 원형 구조(archetype)을 검색할 때 유용합니다.
개념은 단순하지만 깊게는 Prim's Minimum-Spanning-Tree  알고리즘이나 다익스트라의 Single source shortest path까지도 BFS와 관련된 알고리즘입니다.

 

CLRS의 수도 코드

Graph G
for each vertex u in G.v
	u.color = WHITE
    u.d = INF
    u.p = NIL

s.color = GRAY
s.d = 0
s.p = NIL

Queue Q
Enqueue(Q, s)
while Q is not empty()
	u = Dequeue(Q)
    for each v In G.adj[v]
    	if v.color == WHITE
        	v.color = GRAY
            v.d = u.d + 1
            v.p = u
            Enqueue(Q, v)
    u.color = BLACK

수도코드를 적긴 했지만 가독성이 많이 떨어집니다. 나중에 수정할 예정입니다.

C++ 코드형식으로 수도 코드

bool visited[size]={false};

void bfs(int k){
  queue<int> Q;

  // 초기 시작 Node(root)
  Q.push(K);
  visited[k] = true;
    
  // Queue가 빌때까지
  while(!Q.empty()){
  int current = Q.front();
  Q.pop();

  // G[current]와 adjacent한 node 탐색 loop 
  for(int i=0; i<G[current].size(); i++){
    if(!visited[G[current][i]]){
      visited[G[current][i]] = true;
      Q.push(G[current][i]);
      }
    }
  }
}