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와 같은 존재이다.

BFS Code

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

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);          // 정점 처리 완료 후 작업
    }
}

Exploiting Traversal

BFS 알고리즘은 그래프의 각 정점과 간선을 정확히 한번씩 방문하며, 이때 훅(hook) 함수들을 끼워 넣으면, 원하는 일을 자동으로 수행할 수 있다. 위에서 정의된 BFS() 함수에서의:

• process_vertex_early(int v): 정점 v를 꺼냈을 때 (BFS면 큐에서 dequeue 직후) 가장 먼저 호출
  • 정점 방문 순서 출력, 레벨(거리) 기록, 통계 수집, 색칠 등의 작업을 실행
• process_edge(int x, int y): 정점 x의 인접리스트를 훑는 각 간선 (x, y)를 만날 때마다 호출
  • 간선 방문 순서 출력, 선 개수 세기, 사이클 탐지 등을 함

이때 방문 순서를 출력할 경우 각 정점, 간선들은 정확히 한번 씩 출력되므로, 해당 함수들을 단순히 printf로 채우면 방문된 모든 정점과 간선이 중복 없이 출력된다. 하지만 undirected 그래프에서는 간선 (u, v)가 (v, u)와 같이 해석될 수 있으므로 “간선을 한 번만” 처리하려면 보통

if (!processed[y] || g->directed) process_edge(x, y);

와 같은 제약을 사용한다. 이는 위의 BFS() 함수 구현에서도 구현되어 있다.

Finding Paths

BFS는 정점을 처음 발견했을 때 “누가 이 정점을 발견했는지”를 parent[] 배열에 기록한다:

• parent[i] = 정점 i를 처음 큐에 넣게 만든 “직전의” 정점(발견자).
  • 시작 정점 s는 보통 parent[s] = -1로 표시함.
• 모든 parent 화살표를 모으면, 시작 정점을 루트 노드로 하는 “발견 트리(discovery tree)”가 생김
  • 이 트리는 탐색 순서를 보존함. 즉, 어떤 정점이 어떤 정점을 통해 처음 도달되었는지를 담고 있어, 경로 복원 등에 사용됨.

아래는 parent[]를 이용해 끝점에서 시작점으로 거꾸로 따라가면 경로를 복원하는 함수이다:

void find_path(int start, int end, int parents[]) {
    if ((start == end) || (end == -1)) { //루트 노드에 도달
          printf("\n%d", start);
    } else {
        find_path(start, parents[end], parents); //end의 부모 쪽으로 한 칸 올라가서 해당 경로 출력
        printf(" %d", end);
    }
}

Shortest Paths and BFS

BFS는 간선 가중치가 모두 동일할 때, 시작 정점으로부터의 최단(간선 수 최소) 경로를 자동으로 보장한다. 이는 BFS가 레이어 순서대로 확장하기 때문이다. 거리 0(시작) → 거리 1 → 거리 2 → … 순서로 큐에서 꺼내 처리하기 때문에, 발견 트리에서 루트 내의 임의의 정점 x 로 내려가는 유일한 트리 경로는, 가능한 경로 중 간선 수가 최소이다. 이는 figure에서 알 수 있듯이 어떤 그래프가 주어졌을 때 parent[] 배열을 이용하여 발견 트리를 구성할 수 있으며, 이때 발견 트리의 어떤 정점에 대한 깊이는 루트에서의 해당 정점까지의 경로의 길이에 비례하기 때문이다.

Applications of BFS

BFS 알고리즘은 그 특성 덕분에 단순한 탐색을 넘어 더 다양한 분야에 사용된다.

Connected components

Connected components는 undirected 그래프를 여러 조각으로 나눈 것으로, 같은 조각 안의 임의의 두 정점 사이에는 경로가 있고, 서로 다른 조각 사이에는 경로가 없다. 이때 어떤 그래프가 주어졌을 때, 해당 그래프 내의 모든 조각들을 찾아내는 문제에 대해 BFS는 좋은 해결책이 된다. 이는 임의의 시작점에서 BFS를 한 번 돌리면 그 시작점과 같은 연결 요소에 있는 모든 정점이 발견되기 때문이다. 또한 아직 안 발견된 정점이 남아 있으면, 거기서 다시 BFS를 시작해 다음 연결 요소를 찾아서 문제를 해결할 수 있다. 이는 이를 구현하는 코드이다:

void connected_components(graph *g) {
    int c = 0;   // 조각의 숫자를 계산하는 카운터
    int i;

    initialize_search(g);   // discovered[], processed[], parent[] 등 초기화

    /* 그래프의 모든 정점을 순회 */
    for (i = 1; i <= g->nvertices; i++) {
        if (!discovered[i]) {           // 아직 방문되지 않은 정점이라면
            c++;                  // 새로운 연결 요소 발견 → 카운터 증가
            printf("Component %d:", c); // 몇 번째 조각인지 출력
            bfs(g, i);                  // 해당 정점부터 BFS 탐색 수행
            printf("\n");               // 한 컴포넌트 출력 후 줄바꿈
        }
    }
}
void process_vertex_early(int v) {
    printf(" %d", v);
}
void process_edge(int x, int y) {}

Two-Coloring Graphs

Two-Coloring Graphs 문제는 인접한 두 정점이 같은 색이 되지 않도록 색을 배정하는 문제이다. 또한 단 두 색으로도 충돌 없이 색칠 가능한 그래프를 이분 그래프(bipartite)라고 한다. 이는 아래와 같은 코드를 통해 해결할 수 있다:

void twocolor(graph *g) {
    int i;
    /* 모든 정점을 미색칠 상태로 초기화 */
    for (i = 1; i <= g->nvertices; i++) {
        color[i] = UNCOLORED;
    }

    bipartite = true;          // 이분 그래프라고 가정하고 시작
    initialize_search(g);      // BFS용 초기화 (discovered, processed 등)

    /* 모든 정점에 대해 BFS 수행 (연결되지 않은 그래프 대비) */
    for (i = 1; i <= g->nvertices; i++) {
        if (!discovered[i]) {  // 아직 방문하지 않은 정점이라면
            color[i] = WHITE;  // 시작 색은 WHITE로 설정
            bfs(g, i);         // BFS 탐색 시작
        }
    }
}

void process_edge(int x, int y) {
    if (color[x] == color[y]) {   // 같은 색이면 이분 그래프 아님
        bipartite = false;
        printf("Warning: not bipartite, due to (%d,%d)\n", x, y);
    }
    color[y] = complement(color[x]);  // y를 x의 반대 색으로 칠하기
}

int complement(int color) { //현재 색의 반대색 반환 함수
    if (color == WHITE) {
        return BLACK;
    } else if (color == BLACK) {
        return WHITE;
    } else return UNCOLORED;
}