너비 우선 탐색(Breadth-First Search)

이번 포스트에서는 너비 우선 탐색(BFS) 알고리즘에 대해 다루도록 하겠습니다.

너비 우선 탐색(BFS)이란?

: 루트 노드(혹은 임의의 노드)부터 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것입니다.

 

너비 우선 탐색의 특징 :

• 재귀적으로 동작하지 않는다.
• 방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
• 어떤 노드를 방문했는지를 반드시 검사한다.

너비 우선 탐색의 동작 과정 : 



 

1. 초기 상태의 큐에는 시작 노드만 저장. (Q = [0])
2. 큐에서 노드를 꺼내서 방문 및 인접 노드를 큐에 삽입 -> V0 방문 (Q = [1, 2])
3. 더 이상 삽입할 인접한 노드가 없다면 dequeue 실행 (큐의 맨 앞에서 노드를 꺼낸다) -> V1 방문 (Q = [2])
4. V1의 인접 노드를 큐에 삽입 (Q = [2, 3, 4])
5. V2 방문 및 인접 노드 삽입 (Q = [3, 4, 5, 6])
6. V3 방문 및 인접 노드 삽입 (Q = [4, 5, 6, 7], V1은 이미 방문했으니 생략)
7. V4 방문 및 인접 노드 삽입 (Q = [5, 6, 7])
8. V5 방문 및 인접 노드 삽입 (Q = [6, 7])
9. V6 방문 및 인접 노드 삽입 (Q = [7])
10. V7 방문 및 인접 노드 삽입 (Q = [], 더 이상 인접 노드가 없으니 종료)
11. 최종 결과 : V0, V1, V2, V3, V4, V5, V6, V7

너비 우선 탐색 소스 코드 :

void bfs(int v)
{
    node_pointer w;
    queue_pointer front = NULL, rear = NULL;
    
    printf("%5d", v);
    visited[v] = TRUE;
    addq(&front, &rear, v);
    while (front) {
    	v = deleteq(&front);
        for (w = graph[v]; w; w = w->link) {
        	if (!visited[w->vertex]) {
            		printf("%5d", w->vertex);
                	addq(&front, &rear, w->vertex);
                	visited[w->vertex] = TRUE;
            }
        }
    }
}

 

소스 코드 분석 :

초기 노드부터 시작하여 방문하고 큐에 추가한다. 큐가 완전히 소진할 때까지 반복한다. 반복하는 동안에 이미 방문한 노드를 삭제하여 인접 노드 중 방문하지 않는 노드를 차례대로 큐에 삽입한다. 더 이상 인접 노드가 없으면 큐에서 제일 앞에 위치한 노드를 방문하고 삭제하여 이전 과정을 반복한다.