BFS

상위 문서: 알고리즘 설계와 분석

개요

BFS(Breadth-First Traversal) 알고리즘의 핵심은 그래프를 체계적으로(순서 있게) 탐색하는 것이다. BFS는 모든 vertex와 edge를 한 번씩 방문한다. 이는 아래와 같은 규칙을 따른다.

• “Breadth-First”는 탐색 시 가까운 노드(이웃)를 먼저 방문하고, 그 후에 더 멀리 있는 노드를 탐색하는 방식이다.
  • 예를 들어, 루트 노드로부터 거리 1인 정점들을 모두 방문한 뒤, 그 다음으로 거리가 2인 정점, 3인 정점...을 방문하는 방식이다.
• BFS는 queue(큐)를 이용해 이 순서를 보장한다.

이에 따라 BFS는 특히 unweighted 그래프에서 최단 경로(shortest path)를 찾는 데 적합하다. 이는 DFS(깊이 우선 탐색)와 달리, BFS는 각 vertex까지의 최단 거리(간선 개수 기준)를 자연스럽게 구할 수 있기 때문이다.

Implementing BFS

Data Structures for BFS

BFS를 구현하기 위해 필요한 자료구조는 3가지이다:

bool processed[MAXV+1];   // 이미 완전히 처리된 정점 
bool discovered[MAXV+1];  // 방문은 했지만 아직 다 보지 않은 정점 
int parent[MAXV+1];       // 해당 정점을 방문하기 전의 부모 노드

또한 BFS는 FIFO queue를 이용하므로, 먼저 발견된 노드를 먼저 처리해야 “너비 우선” 순서가 유지된다. 이때 새로운 정점이 발견되면 discovered[y] = true로 표시하고 큐에 추가한다. 즉, queue는 처리할 정점들이 저장되는 to-do list와 같은 존재이다.

Initializing BFS

아래는 탐색을 시작하기 전에 배열을 초기화하는 함수이다.

void bfs(graph *g, int start) {
    queue q;           /* 방문할 정점들을 담는 큐 */
    int v;             /* 현재 방문 중인 정점 */
    int y;             /* 인접(후속) 정점 */
    edgenode *p;       /* 인접 리스트를 순회하기 위한 포인터 */

    /* 초기화 단계 */
    init_queue(&q);            // 큐 초기화
    enqueue(&q, start);        // 시작 정점을 큐에 넣기
    discovered[start] = true;  // 시작 정점을 "발견됨"으로 표시

    /* BFS 메인 루프 */
    while (!empty_queue(&q)) {
        v = dequeue(&q);           // 큐에서 정점을 하나 꺼냄
        process_vertex_early(v);   // 방문 직후 처리 (예: 출력)
        processed[v] = true;       // 완전히 처리된 정점으로 표시

        /* 인접 정점 순회 */
        p = g->edges[v];           // v의 인접 리스트의 첫 노드
        while (p != NULL) {
            y = p->y;              // 인접 정점 번호

            /* 간선 (v, y) 처리 */
            if ((!processed[y]) || g->directed) {
                process_edge(v, y); // 간선 처리 (예: 출력, 트리 생성 등)
            }

            /* 새로운 정점 발견 시 */
            if (!discovered[y]) {
                enqueue(&q, y);          // 큐에 추가
                discovered[y] = true;    // 발견됨 표시
                parent[y] = v;           // BFS 트리 상의 부모 설정
            }

            p = p->next;                 // 다음 인접 정점으로 이동
        }

        process_vertex_late(v);          // 정점 처리 완료 후 작업
    }
}