그래프 탐색 DFS 스택

들어가는 말

앞서 재귀로 구현한 DFS를 살펴보았다.
재귀 DFS는 함수를 호출할 때마다 호출 정보를 호출 스택(Call Stack)에 쌓아, 다음에 탐색할 정점과 탐색을 마친 뒤 돌아갈 위치를 기억한다.
재귀는 구현이 간결하지만 호출이 반복될수록 함수 호출 오버헤드가 누적되어 성능이 저하될 수 있다.
또한 그래프의 깊이가 매우 깊으면 호출 스택이 넘쳐 스택 오버플로가 발생해 프로그램이 중단될 수도 있다.

스택을 이용한 DFS는 호출 스택이 맡던 두 가지 역할을 명시적인 스택 자료구조로 직접 처리하는 방식이다.
두 가지 역할이란 다음에 탐색할 정점을 기억하는 일과 탐색을 마친 뒤 돌아갈 위치를 관리하는 일이다.
따라서 재귀 호출 깊이 제한을 피할 수 있으며, 탐색 상태를 명시적으로 관리하는 등 실행 흐름을 세밀하게 제어해야 할 때도 유용하다.

스택을 이용한 DFS의 동작 원리

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

위 무방향 그래프는 재귀 DFS에서 사용한 그래프와 같다.
재귀 DFS를 정점 0에서 시작해 인접 정점을 작은 번호부터 방문하면, 0 → 1 → 2 → 5 → 4 → 7 → 8 → 6 → 3 → 9 순서가 된다.
같은 조건으로 스택 DFS를 구현하면 방문 순서는 달라진다.
이때 방문 순서는 0 → 3 → 6 → 9 → 8 → 7 → 4 → 5 → 2 → 1이다.
스택은 LIFO(Last In, First Out) 자료구조이므로, 마지막에 넣은 큰 번호의 정점이 먼저 꺼내지기 때문이다.

스택 DFS에서 방문 표시를 하는 방법은 두 가지가 있다.
정점을 스택에서 꺼낼 때 방문 표시하는 방법과, 스택에 넣을 때 방문 표시하는 방법이다.
정점을 꺼낼 때 방문 표시하면 아직 꺼내지지 않은 같은 정점이 스택에 여러 번 들어갈 수 있다.
이 경우 꺼낸 정점이 이미 방문한 정점이라면 건너뛰는 방식으로 처리할 수 있다.
이 글에서는 정점을 스택에 넣을 때 방문 표시하는 방법을 사용한다.
정점이 스택에 들어가면 언젠가 스택에서 꺼내져 탐색되는 것이 보장되기 때문이다.

다음 설명에서는 스택을 배열처럼 [] 안에 가로로 표현하며, 오른쪽이 top이다.

단계	연산	정점	스택 전	스택 후	판단
1	push	0	[]	[0]	시작 정점 0을 방문 표시한다.
2	pop	0	[0]	[]	0을 방문한다.
3	push	1	[]	[1]	0의 방문하지 않은 인접 정점 1을 방문 표시한다.
4	push	2	[1]	[1, 2]	0의 방문하지 않은 인접 정점 2를 방문 표시한다.
5	push	3	[1, 2]	[1, 2, 3]	0의 방문하지 않은 인접 정점 3을 방문 표시한다.
6	pop	3	[1, 2, 3]	[1, 2]	3을 방문한다.
7	push	6	[1, 2]	[1, 2, 6]	3의 인접 정점 0은 이미 방문했고, 6을 방문 표시한다.
8	pop	6	[1, 2, 6]	[1, 2]	6을 방문한다.
9	push	5	[1, 2]	[1, 2, 5]	6의 인접 정점 2, 3은 이미 방문했고, 5를 방문 표시한다.
10	push	8	[1, 2, 5]	[1, 2, 5, 8]	6의 방문하지 않은 인접 정점 8을 방문 표시한다.
11	push	9	[1, 2, 5, 8]	[1, 2, 5, 8, 9]	6의 방문하지 않은 인접 정점 9를 방문 표시한다.
12	pop	9	[1, 2, 5, 8, 9]	[1, 2, 5, 8]	9를 방문한다. 9의 인접 정점 6, 8은 이미 방문했으므로 넣지 않는다.
13	pop	8	[1, 2, 5, 8]	[1, 2, 5]	8을 방문한다.
14	push	7	[1, 2, 5]	[1, 2, 5, 7]	8의 인접 정점 6, 9는 이미 방문했고, 7을 방문 표시한다.
15	pop	7	[1, 2, 5, 7]	[1, 2, 5]	7을 방문한다.
16	push	4	[1, 2, 5]	[1, 2, 5, 4]	7의 인접 정점 5, 8은 이미 방문했고, 4를 방문 표시한다.
17	pop	4	[1, 2, 5, 4]	[1, 2, 5]	4를 방문한다. 4의 인접 정점 1, 5, 7은 이미 방문했으므로 넣지 않는다.
18	pop	5	[1, 2, 5]	[1, 2]	5를 방문한다. 5의 인접 정점 2, 4, 6, 7은 이미 방문했으므로 넣지 않는다.
19	pop	2	[1, 2]	[1]	2를 방문한다. 2의 인접 정점 0, 1, 5, 6은 이미 방문했으므로 넣지 않는다.
20	pop	1	[1]	[]	1을 방문한다. 1의 인접 정점 0, 2, 4는 이미 방문했으므로 넣지 않는다.

스택이 비었으므로 탐색을 종료한다.

소스 코드

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

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 STACK_CAPACITY VERTEX_COUNT

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

typedef struct
{
    int data[STACK_CAPACITY];
    int top;
} Stack;

void stack_init(Stack* stack)
{
    stack->top = -1;
}

void stack_push(Stack* stack, int value)
{
    stack->data[++stack->top] = value;
}

int stack_pop(Stack* stack)
{
    return stack->data[stack->top--];
}

int stack_is_empty(const Stack* stack)
{
    return stack->top == -1;
}

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

void graph_print(const Graph* graph)
{
    printf("  ");
    for (int col = 0; col < VERTEX_COUNT; col++)
    {
        printf("%d ", col);
    }
    printf("\n");

    for (int row = 0; row < VERTEX_COUNT; row++)
    {
        printf("%d ", row);
        for (int col = 0; col < VERTEX_COUNT; col++)
        {
            printf("%d ", graph->matrix[row][col]);
        }
        printf("\n");
    }
}

void graph_dfs(const Graph* graph, int start)
{
    Stack stack;
    stack_init(&stack);
    stack_push(&stack, start);

    bool visited[VERTEX_COUNT] = { false };
    visited[start] = true;

    while (!stack_is_empty(&stack))
    {
        const int current = stack_pop(&stack);

        printf("%d ", current);

        for (int neighbor = 0; neighbor < VERTEX_COUNT; neighbor++)
        {
            if (graph->matrix[current][neighbor] && !visited[neighbor])
            {
                visited[neighbor] = true;
                stack_push(&stack, 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_print(&graph);
    printf("\n");

    graph_dfs(&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 STACK_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[STACK_CAPACITY];
    int top;
} Stack;

void stack_init(Stack* stack)
{
    stack->top = -1;
}

void stack_push(Stack* stack, int value)
{
    stack->data[++stack->top] = value;
}

int stack_pop(Stack* stack)
{
    return stack->data[stack->top--];
}

int stack_is_empty(const Stack* stack)
{
    return stack->top == -1;
}

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_print(const Graph* graph)
{
    for (int vertex = 0; vertex < VERTEX_COUNT; vertex++)
    {
        printf("%d:", vertex);
        const VertexNode* current = graph->heads[vertex];

        while (current != NULL)
        {
            printf(" %d", current->vertex);
            current = current->next;
        }
        printf("\n");
    }
}

void graph_dfs(const Graph* graph, int start)
{
    Stack stack;
    stack_init(&stack);
    stack_push(&stack, start);

    bool visited[VERTEX_COUNT] = { false };
    visited[start] = true;

    while (!stack_is_empty(&stack))
    {
        const int current = stack_pop(&stack);
        const VertexNode* node = graph->heads[current];

        printf("%d ", current);

        while (node != NULL)
        {
            if (!visited[node->vertex])
            {
                visited[node->vertex] = true;
                stack_push(&stack, 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* const 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_print(&graph);
    graph_dfs(&graph, 0);
    printf("\n");

    graph_destroy(&graph);

    return 0;
}