그래프 탐색 BFS

2026. 08. 06

들어가는 말

깊이 우선 탐색(Depth-First Search, DFS)은 한 경로를 끝까지 탐색한 뒤 되돌아오므로,
후입선출(LIFO, Last In, First Out) 방식의 재귀나 스택으로 구현하기 적합하다.
반면 너비 우선 탐색(Breadth-First Search, BFS)은 시작 정점에서 가까운 정점부터 차례로 탐색한다.
먼저 발견한 정점을 먼저 처리해야 하므로, BFS는 선입선출(FIFO, First In, First Out) 방식의 큐를 사용한다.

BFS의 동작 원리

            A
        ╱       ╲
       B         C
     ╱   ╲     ╱   ╲
    D     E   F     G
   ╱ ╲
  H   I

먼저 익숙한 이진 트리를 BFS로 방문해 보자.
BFS는 시작 노드에서 같은 거리에 있는 노드를 먼저 방문한 뒤, 그다음 거리에 있는 노드를 방문하는 탐색 방식이다.
BFS는 먼저 발견한 노드부터 방문하기 위해 큐 자료구조를 사용한다.
큐는 먼저 넣은 노드가 먼저 나오므로, 같은 깊이의 노드를 차례로 방문할 수 있다.

왼쪽 자식을 먼저 큐에 넣는다고 가정하면 BFS의 방문 순서는 A → B → C → D → E → F → G → H → I가 된다.
A에서 시작한 BFS는 A를 방문한 뒤 왼쪽 자식 B와 오른쪽 자식 C를 차례로 큐에 넣는다.
이후 큐의 앞에 있는 B를 먼저 방문하고, B의 자식 D, E를 큐에 넣는다.
그다음 C를 방문하고, C의 자식 F, G를 큐에 넣는다.
그다음 큐의 앞에 있는 D를 방문하고, D의 자식 H, I를 큐에 넣는다.
이후 E, F, G를 차례로 방문하지만 이 노드들은 자식이 없으므로 새 노드를 큐에 넣지 않는다.
마지막으로 큐에 남아 있는 H, I를 차례로 방문한다.

오른쪽 자식을 먼저 큐에 넣는다고 가정하면 BFS의 방문 순서는 A → C → B → G → F → E → D → I → H가 된다.
어느 자식을 먼저 큐에 넣을지는 구현에서 자식을 확인하는 순서에 따라 달라지며, 이 글에서는 왼쪽 자식부터 넣는다.

이제 무방향 그래프로 BFS를 살펴보자.

  1---4
 / \  | \
0--2--5--7
|  |/    |
3--6-----8
    \   /
     \ /
      9

위 그래프에서 정점 0부터 탐색을 시작하고, 인접 정점은 번호가 작은 순서대로 방문해 보자.

방문 표시는 정점을 큐에서 꺼낼 때나 큐에 넣을 때 할 수 있다.
다만 꺼낼 때 표시하면, 꺼내기 전까지 같은 정점이 여러 번 큐에 들어갈 수 있다.
이 글에서는 한 번 큐에 들어간 정점은 나중에 반드시 꺼낸다는 점을 이용해, 큐에 넣는 순간 방문 표시로 구현한다.

아래 표에서는 큐의 상태를 []로 표시하며, 왼쪽이 front, 오른쪽이 rear이다.
탐색 순서는 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9가 된다.

단계	연산	정점	큐 전	큐 후	판단
1	enqueue	`0`	`[]`	`[0]`	시작 정점 `0`을 방문 표시하고 큐에 넣는다.
2	dequeue	`0`	`[0]`	`[]`	`0`을 방문한다.
3	enqueue	`1`	`[]`	`[1]`	`0`의 방문하지 않은 인접 정점 `1`을 방문 표시하고 넣는다.
4	enqueue	`2`	`[1]`	`[1, 2]`	`0`의 방문하지 않은 인접 정점 `2`를 방문 표시하고 넣는다.
5	enqueue	`3`	`[1, 2]`	`[1, 2, 3]`	`0`의 방문하지 않은 인접 정점 `3`을 방문 표시하고 넣는다.
6	dequeue	`1`	`[1, 2, 3]`	`[2, 3]`	`1`을 방문한다.
7	enqueue	`4`	`[2, 3]`	`[2, 3, 4]`	`1`의 인접 정점 `0`, `2`는 이미 방문했고, `4`를 방문 표시하고 넣는다.
8	dequeue	`2`	`[2, 3, 4]`	`[3, 4]`	`2`를 방문한다.
9	enqueue	`5`	`[3, 4]`	`[3, 4, 5]`	`2`의 방문하지 않은 인접 정점 `5`를 방문 표시하고 넣는다.
10	enqueue	`6`	`[3, 4, 5]`	`[3, 4, 5, 6]`	`2`의 방문하지 않은 인접 정점 `6`을 방문 표시하고 넣는다.
11	dequeue	`3`	`[3, 4, 5, 6]`	`[4, 5, 6]`	`3`을 방문하고, 인접 정점 `0`, `6`은 이미 방문했으므로 넣지 않는다.
12	dequeue	`4`	`[4, 5, 6]`	`[5, 6]`	`4`를 방문한다.
13	enqueue	`7`	`[5, 6]`	`[5, 6, 7]`	`4`의 방문하지 않은 인접 정점 `7`을 방문 표시하고 넣는다.
14	dequeue	`5`	`[5, 6, 7]`	`[6, 7]`	`5`를 방문하고, 인접 정점은 모두 이미 방문했으므로 넣지 않는다.
15	dequeue	`6`	`[6, 7]`	`[7]`	`6`을 방문한다.
16	enqueue	`8`	`[7]`	`[7, 8]`	`6`의 방문하지 않은 인접 정점 `8`을 방문 표시하고 넣는다.
17	enqueue	`9`	`[7, 8]`	`[7, 8, 9]`	`6`의 방문하지 않은 인접 정점 `9`를 방문 표시하고 넣는다.
18	dequeue	`7`	`[7, 8, 9]`	`[8, 9]`	`7`을 방문하고, 인접 정점은 모두 이미 방문했으므로 넣지 않는다.
19	dequeue	`8`	`[8, 9]`	`[9]`	`8`을 방문하고, 인접 정점은 모두 이미 방문했으므로 넣지 않는다.
20	dequeue	`9`	`[9]`	`[]`	`9`를 방문하고, 큐가 비었으므로 탐색을 종료한다.

소스 코드

앞서 BFS의 동작 원리에서 살펴본 그래프를 인접 행렬과 인접 리스트로 각각 구현해 보자.
두 구현 모두 정점 0에서 탐색을 시작하면 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 순서로 방문한다.

1. 인접 행렬로 구현하기

아래 표에서 행은 현재 정점이고 열은 연결 여부를 확인할 정점이다.
두 정점이 연결되어 있으면 1이고, 연결되어 있지 않으면 0이다.

	0	1	2	3	4	5	6	7	8	9
0	0	1	1	1	0	0	0	0	0	0
1	1	0	1	0	1	0	0	0	0	0
2	1	1	0	0	0	1	1	0	0	0
3	1	0	0	0	0	0	1	0	0	0
4	0	1	0	0	0	1	0	1	0	0
5	0	0	1	0	1	0	1	1	0	0
6	0	0	1	1	0	1	0	0	1	1
7	0	0	0	0	1	1	0	0	1	0
8	0	0	0	0	0	0	1	1	0	1
9	0	0	0	0	0	0	1	0	1	0

#include <stdio.h>
#include <stdbool.h>

#define VERTEX_COUNT 10
#define QUEUE_CAPACITY VERTEX_COUNT

typedef struct
{
    int data[QUEUE_CAPACITY];
    int front;
    int rear;
    int count;
} Queue;

typedef struct
{
    bool matrix[VERTEX_COUNT][VERTEX_COUNT];
} Graph;

void queue_init(Queue* queue)
{
    queue->front = 0;
    queue->rear = 0;
    queue->count = 0;
}

int queue_is_empty(const Queue* queue)
{
    return queue->count == 0;
}

void queue_enqueue(Queue* queue, int value)
{
    if (queue->count == QUEUE_CAPACITY)
        return;

    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % QUEUE_CAPACITY;
    queue->count++;
}

int queue_dequeue(Queue* queue)
{
    if (queue_is_empty(queue))
        return -1;

    const int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % QUEUE_CAPACITY;
    queue->count--;

    return value;
}

void graph_add_undirected_edge(Graph* graph, int a, int b)
{
    graph->matrix[a][b] = true;
    graph->matrix[b][a] = true;
}

void graph_bfs(const Graph* graph, int start)
{
    Queue queue;
    bool visited[VERTEX_COUNT] = { false };

    queue_init(&queue);
    queue_enqueue(&queue, start);
    visited[start] = true;

    while (!queue_is_empty(&queue))
    {
        const int current = queue_dequeue(&queue);

        printf("%d ", current);

        for (int neighbor = 0; neighbor < VERTEX_COUNT; neighbor++)
        {
            if (graph->matrix[current][neighbor] && !visited[neighbor])
            {
                visited[neighbor] = true;
                queue_enqueue(&queue, neighbor);
            }
        }
    }
}

int main(void)
{
    Graph graph = { 0 };

    graph_add_undirected_edge(&graph, 0, 1);
    graph_add_undirected_edge(&graph, 0, 2);
    graph_add_undirected_edge(&graph, 0, 3);
    graph_add_undirected_edge(&graph, 1, 2);
    graph_add_undirected_edge(&graph, 1, 4);
    graph_add_undirected_edge(&graph, 2, 5);
    graph_add_undirected_edge(&graph, 2, 6);
    graph_add_undirected_edge(&graph, 3, 6);
    graph_add_undirected_edge(&graph, 4, 5);
    graph_add_undirected_edge(&graph, 4, 7);
    graph_add_undirected_edge(&graph, 5, 6);
    graph_add_undirected_edge(&graph, 5, 7);
    graph_add_undirected_edge(&graph, 6, 8);
    graph_add_undirected_edge(&graph, 6, 9);
    graph_add_undirected_edge(&graph, 7, 8);
    graph_add_undirected_edge(&graph, 8, 9);

    graph_bfs(&graph, 0);
    printf("\n");

    return 0;
}

2. 인접 리스트로 구현하기

각 정점은 인접한 정점들을 연결 리스트로 관리한다.

정점	인접 리스트
0	`1 → 2 → 3`
1	`0 → 2 → 4`
2	`0 → 1 → 5 → 6`
3	`0 → 6`
4	`1 → 5 → 7`
5	`2 → 4 → 6 → 7`
6	`2 → 3 → 5 → 8 → 9`
7	`4 → 5 → 8`
8	`6 → 7 → 9`
9	`6 → 8`

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define VERTEX_COUNT 10
#define QUEUE_CAPACITY VERTEX_COUNT

typedef struct VertexNode
{
    int vertex;
    struct VertexNode* next;
} VertexNode;

typedef struct
{
    VertexNode* heads[VERTEX_COUNT];
    VertexNode* tails[VERTEX_COUNT];
} Graph;

typedef struct
{
    int data[QUEUE_CAPACITY];
    int front;
    int rear;
    int count;
} Queue;

void queue_init(Queue* queue)
{
    queue->front = 0;
    queue->rear = 0;
    queue->count = 0;
}

int queue_is_empty(const Queue* queue)
{
    return queue->count == 0;
}

void queue_enqueue(Queue* queue, int value)
{
    if (queue->count == QUEUE_CAPACITY)
        return;

    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % QUEUE_CAPACITY;
    queue->count++;
}

int queue_dequeue(Queue* queue)
{
    if (queue_is_empty(queue))
        return -1;

    const int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % QUEUE_CAPACITY;
    queue->count--;

    return value;
}

void graph_init(Graph* graph)
{
    for (int i = 0; i < VERTEX_COUNT; i++)
    {
        graph->heads[i] = NULL;
        graph->tails[i] = NULL;
    }
}

static void graph_add_directed_edge(Graph* graph, int from, int to)
{
    VertexNode* const new_node = malloc(sizeof(VertexNode));

    new_node->vertex = to;
    new_node->next = NULL;

    if (graph->heads[from] == NULL)
        graph->heads[from] = new_node;
    else
        graph->tails[from]->next = new_node;

    graph->tails[from] = new_node;
}

void graph_add_undirected_edge(Graph* graph, int a, int b)
{
    graph_add_directed_edge(graph, a, b);
    graph_add_directed_edge(graph, b, a);
}

void graph_bfs(const Graph* graph, int start)
{
    Queue queue;
    bool visited[VERTEX_COUNT] = { false };

    queue_init(&queue);
    queue_enqueue(&queue, start);
    visited[start] = true;

    while (!queue_is_empty(&queue))
    {
        const int current = queue_dequeue(&queue);
        const VertexNode* node = graph->heads[current];

        printf("%d ", current);

        while (node != NULL)
        {
            if (!visited[node->vertex])
            {
                visited[node->vertex] = true;
                queue_enqueue(&queue, node->vertex);
            }

            node = node->next;
        }
    }
}

void graph_destroy(Graph* graph)
{
    for (int vertex = 0; vertex < VERTEX_COUNT; vertex++)
    {
        VertexNode* current = graph->heads[vertex];

        while (current != NULL)
        {
            VertexNode* next = current->next;
            free(current);
            current = next;
        }
    }
}

int main(void)
{
    Graph graph;
    graph_init(&graph);

    graph_add_undirected_edge(&graph, 0, 1);
    graph_add_undirected_edge(&graph, 0, 2);
    graph_add_undirected_edge(&graph, 0, 3);
    graph_add_undirected_edge(&graph, 1, 2);
    graph_add_undirected_edge(&graph, 1, 4);
    graph_add_undirected_edge(&graph, 2, 5);
    graph_add_undirected_edge(&graph, 2, 6);
    graph_add_undirected_edge(&graph, 3, 6);
    graph_add_undirected_edge(&graph, 4, 5);
    graph_add_undirected_edge(&graph, 4, 7);
    graph_add_undirected_edge(&graph, 5, 6);
    graph_add_undirected_edge(&graph, 5, 7);
    graph_add_undirected_edge(&graph, 6, 8);
    graph_add_undirected_edge(&graph, 6, 9);
    graph_add_undirected_edge(&graph, 7, 8);
    graph_add_undirected_edge(&graph, 8, 9);

    graph_bfs(&graph, 0);
    printf("\n");

    graph_destroy(&graph);

    return 0;
}

	0	1	2	3	4	5	6	7	8	9
0	0	1	1	1	0	0	0	0	0	0
1	1	0	1	0	1	0	0	0	0	0
2	1	1	0	0	0	1	1	0	0	0
3	1	0	0	0	0	0	1	0	0	0
4	0	1	0	0	0	1	0	1	0	0
5	0	0	1	0	1	0	1	1	0	0
6	0	0	1	1	0	1	0	0	1	1
7	0	0	0	0	1	1	0	0	1	0
8	0	0	0	0	0	0	1	1	0	1
9	0	0	0	0	0	0	1	0	1	0

	0	1	2	3	4	5	6	7	8	9
0	0	1	1	1	0	0	0	0	0	0
1	1	0	1	0	1	0	0	0	0	0
2	1	1	0	0	0	1	1	0	0	0
3	1	0	0	0	0	0	1	0	0	0
4	0	1	0	0	0	1	0	1	0	0
5	0	0	1	0	1	0	1	1	0	0
6	0	0	1	1	0	1	0	0	1	1
7	0	0	0	0	1	1	0	0	1	0
8	0	0	0	0	0	0	1	1	0	1
9	0	0	0	0	0	0	1	0	1	0

	0	1	2	3	4	5	6	7	8	9
0	0	1	1	1	0	0	0	0	0	0
1	1	0	1	0	1	0	0	0	0	0
2	1	1	0	0	0	1	1	0	0	0
3	1	0	0	0	0	0	1	0	0	0
4	0	1	0	0	0	1	0	1	0	0
5	0	0	1	0	1	0	1	1	0	0
6	0	0	1	1	0	1	0	0	1	1
7	0	0	0	0	1	1	0	0	1	0
8	0	0	0	0	0	0	1	1	0	1
9	0	0	0	0	0	0	1	0	1	0