그래프 탐색 DFS 재귀
들어가는 말
그래프는 어떻게 표현할지뿐 아니라, 각 정점을 어떤 순서와 방식으로 방문할지도 중요하다.
대표적인 그래프 탐색 방법에는 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)이 있다.
이 글에서는 두 탐색 방법 중 흐름을 직관적으로 이해하기 쉬운 DFS부터 살펴본다.
DFS는 재귀 호출 또는 명시적인 스택으로 구현할 수 있고, 그래프는 인접 행렬 또는 인접 리스트로 표현할 수 있다.
따라서 DFS의 구현 방식과 그래프 표현 방식을 조합하면 모두 네 가지 경우가 나온다.
이 글에서는 재귀 DFS를 인접 행렬과 인접 리스트로 차례로 구현해 본다.
재귀를 이용한 DFS 동작 원리
먼저 익숙한 이진 트리의 구조를 살펴보자.
A
╱ ╲
B C
╱ ╲ ╱ ╲
D E F G
╱ ╲
H I이진 트리도 그래프의 일종이며, 루트에서 특정 노드까지 가는 경로는 하나뿐이다.
예를 들어 노드 I에 도달하는 경로는 A → B → D → I이다.
이제 이진 트리를 DFS로 방문해 보자.
DFS는 현재 노드에서 방문하지 않은 자식 노드가 있으면 그 노드로 계속 이동하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아오는 탐색 방식이다.
이처럼 한 경로를 가능한 깊게 탐색하고, 막힌 지점에서 되돌아와 다른 경로를 탐색하는 것이 DFS의 핵심이다.
왼쪽 자식을 먼저 방문한다고 가정하면 DFS의 방문 순서는 A → B → D → H → I → E → C → F → G가 된다.
A에서 시작한 DFS는 왼쪽 자식을 따라 B, D, H까지 내려간다.
H에 자식이 없으므로 D로 돌아가고, D의 아직 방문하지 않은 오른쪽 자식 I를 방문한다.
I에도 자식이 없으므로 D, B 순으로 돌아가 B의 오른쪽 자식 E를 방문한다.
E를 방문한 뒤에는 B와 A로 돌아가 A의 오른쪽 자식 C를 방문한다.
마지막으로 C의 왼쪽 자식 F를 방문하고, C로 돌아와 오른쪽 자식 G를 방문한다.
오른쪽 자식을 먼저 방문한다고 가정하면 DFS의 방문 순서는 A → C → G → F → B → E → D → I → H가 된다.
어느 자식을 먼저 방문할지는 구현에서 자식을 확인하는 순서에 따라 달라지며, 이 글에서는 왼쪽 자식부터 방문한다.
이 과정은 재귀 호출로 자연스럽게 구현할 수 있다.
재귀 호출이 일어날 때마다 호출 스택(Call Stack)에는 현재 탐색 중인 노드와, 탐색을 마친 뒤 돌아와 이어서 실행할 위치가 쌓인다.
따라서 자식 노드를 모두 탐색하면 별도의 되돌아가기 코드를 작성하지 않아도 이전 노드의 탐색으로 자연스럽게 돌아갈 수 있다.
이제 무방향 그래프로 DFS를 살펴보자.
1---4
/ \ | \
0--2--5--7
| |/ |
3--6-----8
\ /
\ /
9DFS는 어떤 정점에서든 시작할 수 있으며, 시작 정점에 따라 방문 순서가 달라질 수 있다.
이 예시에서는 정점 0에서 DFS를 시작한다.
인접 정점은 작은 번호부터 방문한다고 가정하면 DFS의 방문 순서는 0 → 1 → 2 → 5 → 4 → 7 → 8 → 6 → 3 → 9가 된다.
각 정점을 처음 방문할 때 방문했다는 표시를 남기고, 이미 방문한 정점은 다시 방문하지 않는다.
0에서 시작한 DFS는 인접 정점 1, 2, 3 중 번호가 가장 작은 1을 방문한다.
1에서 0은 방문했고, 방문하지 않은 2와 4 중 번호가 작은 2를 방문한다.
2에서 0과 1은 방문했고, 방문하지 않은 5와 6 중 번호가 작은 5를 방문한다.
5에서 2는 방문했고, 방문하지 않은 4, 6, 7 중 번호가 가장 작은 4를 방문한다.
4에서 1과 5는 방문했으므로 남은 7을 방문한다.
7에서 4와 5는 방문했으므로 남은 8을 방문한다.
8에서 7은 방문했고, 방문하지 않은 6과 9 중 번호가 작은 6을 방문한다.
6에서 2, 5, 8은 방문했고, 방문하지 않은 3과 9 중 번호가 작은 3을 방문한다.
3과 연결된 0과 6은 모두 방문했으므로, 3의 호출을 마치고 호출자 6으로 돌아간다.
6으로 돌아오면 방문하지 않은 정점은 9만 남아 있으므로 9를 방문한다.
9와 연결된 6과 8은 모두 방문했으므로, 9의 호출을 마치고 호출자 6으로 돌아간다.
6과 연결된 2, 3, 5, 8, 9도 모두 방문했으므로, 6의 호출을 마치고 호출자 8로 돌아간다.
8과 연결된 6, 7, 9도 모두 방문했으므로, 8의 호출을 마치고 호출자 7로 돌아간다.
7과 연결된 4, 5, 8도 모두 방문했으므로, 7의 호출을 마치고 호출자 4로 돌아간다.
4와 연결된 1, 5, 7도 모두 방문했으므로, 4의 호출을 마치고 호출자 5로 돌아간다.
5와 연결된 2, 4, 6, 7도 모두 방문했으므로, 5의 호출을 마치고 호출자 2로 돌아간다.
2와 연결된 0, 1, 5, 6도 모두 방문했으므로, 2의 호출을 마치고 호출자 1으로 돌아간다.
1과 연결된 0, 2, 4도 모두 방문했으므로, 1의 호출을 마치고 호출자 0으로 돌아간다.
0과 연결된 1, 2, 3도 모두 방문했으므로, 0의 호출을 마치고 탐색을 종료한다.
여기서 돌아간다는 것은 정점을 다시 방문한다는 뜻이 아니다.
해당 정점의 재귀 호출이 끝나면 호출자 정점으로 돌아가, 중단했던 탐색을 이어 간다는 뜻이다.
소스 코드
앞서 DFS의 동작 원리에서 살펴본 그래프를 인접 행렬과 인접 리스트로 각각 구현해 보자.
두 구현 모두 정점 0에서 탐색을 시작하면 0 → 1 → 2 → 5 → 4 → 7 → 8 → 6 → 3 → 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 <stdbool.h>
#include <stdio.h>
#define VERTEX_COUNT 10
typedef struct
{
bool matrix[VERTEX_COUNT][VERTEX_COUNT];
} Graph;
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 current, bool visited[])
{
visited[current] = true;
printf("%d ", current);
for (int neighbor = 0; neighbor < VERTEX_COUNT; neighbor++)
{
if (graph->matrix[current][neighbor] && !visited[neighbor])
{
graph_dfs(graph, neighbor, visited);
}
}
}
int main(void)
{
Graph graph = { 0 };
bool visited[VERTEX_COUNT] = { false };
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, visited);
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
typedef struct VertexNode
{
int vertex;
struct VertexNode* next;
} VertexNode;
typedef struct
{
VertexNode* heads[VERTEX_COUNT];
VertexNode* tails[VERTEX_COUNT];
} Graph;
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* 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 current, bool visited[VERTEX_COUNT])
{
visited[current] = true;
printf("%d ", current);
const VertexNode* current_node = graph->heads[current];
while (current_node != NULL)
{
if (!visited[current_node->vertex])
graph_dfs(graph, current_node->vertex, visited);
current_node = current_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_print(&graph);
printf("\n");
bool visited[VERTEX_COUNT] = { false };
graph_dfs(&graph, 0, visited);
printf("\n");
graph_destroy(&graph);
return 0;
}