DFS(Depth First Search, 깊이 우선 탐색)는 그래프를 순회하며 모든 노드를 방문하는 대표적인 그래프 탐색 알고리즘입니다. 두 노드 사이에 경로가 존재하는지 여부를 판별하는 데에도 활용할 수 있습니다.
이름 그대로 그래프나 트리를 한쪽 경로를 끝까지 따라 내려간 뒤, 더 이상 갈 곳이 없으면 되돌아오는 '깊이 우선' 방식으로 탐색을 수행합니다.
알고리즘 동작 순서
DFS를 구현하기 위한 알고리즘은 다음과 같습니다.
1단계 — 초기 상태에서 스택은 비어 있습니다.
2단계 — 방문할 노드가 스택에 없다면, 해당 노드를 스택에 push하고 방문 처리(visited)합니다.
3단계 — 현재 노드가 찾고자 하는 조건과 일치하는지 확인합니다.
3.1단계 — 조건과 일치한다면 탐색을 종료합니다.
4단계 — 일치하지 않는다면, 현재 노드에 인접한 모든 노드를 살펴봅니다.
4.1단계 — 인접 노드들을 임의의 순서로 방문하며 탐색을 계속 진행합니다.
5단계 — 인접한 모든 노드가 이미 방문된 상태라면 막다른 길(dead end)에 도달한 것입니다.
6단계 — 이전에 방문했던 노드로 되돌아가고, 스택에서 최근 노드를 pop하여 제거합니다.
7단계 — 모든 노드를 탐색했거나 원하는 답을 찾았을 때 알고리즘이 종료됩니다.
C 언어 구현 코드
다음은 DFS(깊이 우선 탐색)을 C 언어로 구현한 전체 프로그램입니다.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
void addVertex(char);
void addEdge(int,int );
void displayVertex(int);
void depthFirstSearch();
int getAdjUnvisitedVertex(int);
struct Vertex {
char label;
bool visited;
};
//스택 변수
int stack[MAX];
int top = -1;
//그래프 변수
//정점 배열
struct Vertex* lstVertices[MAX];
//인접 행렬
int adjMatrix[MAX][MAX];
//정점 개수
int vertexCount = 0;
//스택 함수
void push(int item) {
stack[++top] = item;
}
int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty() {
return top == -1;
}
//그래프 함수
//정점 목록에 정점 추가
void addVertex(char label) {
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}
//간선 추가
void addEdge(int start,int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//정점 출력
void displayVertex(int vertexIndex) {
printf("%c ",lstVertices[vertexIndex]->label);
}
//인접한 미방문 정점 찾기
int getAdjUnvisitedVertex(int vertexIndex) {
int i;
for(i = 0; i < vertexCount; i++) {
if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {
return i;
}
}
return -1;
}
void depthFirstSearch() {
int i;
//첫 번째 노드를 방문 처리
lstVertices[0]->visited = true;
//정점 출력
displayVertex(0);
//정점 인덱스를 스택에 push
push(0);
while(!isStackEmpty()) {
//스택 최상단 정점의 미방문 인접 정점 가져오기
int unvisitedVertex = getAdjUnvisitedVertex(peek());
//인접 정점이 없는 경우
if(unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}
//스택이 비면 탐색 완료, 방문 플래그 초기화
for(i = 0;i < vertexCount;i++) {
lstVertices[i]->visited = false;
}
}
int main() {
int i, j;
for(i = 0; i < MAX; i++) // 인접 행렬을 0으로 {
for(j = 0; j < MAX; j++) // 초기화
adjMatrix[i][j] = 0;
addVertex('S'); // 0
addVertex('A'); // 1
addVertex('B'); // 2
addVertex('C'); // 3
addVertex('D'); // 4
addEdge(0, 1); // S - A
addEdge(0, 2); // S - B
addEdge(0, 3); // S - C
addEdge(1, 4); // A - D
addEdge(2, 4); // B - D
addEdge(3, 4); // C - D
printf("Depth First Search: ");
depthFirstSearch();
return 0;
}실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
Depth First Search: S A D B C
코드 핵심 정리
이 구현의 핵심 요소를 간단히 정리하면 다음과 같습니다.
주요 자료구조
- struct Vertex: 정점의 라벨(label)과 방문 여부(visited)를 저장합니다.
- adjMatrix: 정점 간 연결 관계를 나타내는 인접 행렬입니다.
- stack: 탐색 경로를 추적하기 위한 스택 자료구조입니다.
동작 흐름
시작 정점 S를 방문 처리한 후 스택에 넣고, 스택 최상단 정점의 미방문 인접 정점을 찾아 깊이 들어갑니다. 더 이상 갈 수 없으면(pop) 이전 정점으로 되돌아가며, 스택이 빌 때까지 반복합니다. 탐색이 끝나면 재사용을 위해 모든 visited 플래그를 초기화합니다.