깊이 우선 탐색 (Depth-First Search)

깊이 우선 탐색 (Depth-First Search)

 

깊이 우선 탐색의 기본 원리

깊이 우선 탐색(DFS, Depth-First Search)은 그래프의 모든 정점을 탐색하는 효율적인 방법 중 하나이다. 이 알고리즘은 특정 시작 정점에서 출발하여, 가능한 한 깊이 있게 그래프를 탐색한다.

시작점에서의 탐색

DFS는 시작 정점 v에서 시작한다. 이 정점이 첫 방문 지점이다. 그런 다음에는 v에 인접한 미방문 정점 w를 찾아, w에서 다시 DFS를 시작한다. 이 과정은 모든 정점을 방문할 때까지 계속된다.

더 이상 방문할 정점이 없을 때

만약 현재 정점에 인접한 모든 정점을 방문했다면, 최근에 방문했던 정점 중에서 아직 방문하지 않은 인접 정점을 가진 정점으로 돌아가 탐색을 계속한다.

깊이 우선 탐색의 이해

DFS는 그 이름에서 암시하듯이, '깊이'를 우선으로 한다. 트리의 경우와 달리 그래프에서 '높이'나 '깊이'와 같은 개념이 명확하지 않다. 그럼에도 '깊이' 우선이다. 왜 그럴까?

 

예시 1

예를 들어, 아래와 같은 그래프에서 DFS를 수행해보자.

그림 1

[그림 1]
v1 v2 
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v4 v8
v5 v8
v6 v8
v7 v8

 

v1에서 시작하여 DFS를 수행하면, 방문 순서는 v1, v2, v4, v8, v5, v6, v3, v7이 된다. 이 과정에서 v1의 인접 정점인 v2와 v3 중 v2를 먼저 방문하며, 그 후 v2의 자식인 v4를 방문한다. 이렇게 하여 '깊이'를 우선으로 탐색이 진행된다.

탐색 경로의 이해

v1에서 시작한 탐색은 v2로 이동하고, 여기서 다시 v4로 진행한다. 이 순서는 더 깊은 레벨의 정점을 우선적으로 탐색하는 DFS의 특징을 보여주는 포인트다. 여기서 중요한 점은, v2와 v3가 같은 레벨에 있음에도 불구하고 v2의 자식인 v4로 먼저 이동한다는 것이다. 이것이 깊이 우선 탐색의 핵심 원리이다.

스택을 사용한 탐색 과정

DFS에서는 '스택'을 사용하여 탐색 경로를 관리한다. v1을 방문한 후, v2와 v3는 스택에 저장된다. v2를 방문하면서 그 자식인 v4와 v5가 스택에 추가된다. 이러한 방식으로 스택에 저장된 다음 방문 정점을 하나씩 꺼내어 방문함으로써, 깊이 우선으로 탐색을 진행한다. 좀 더 살펴보자.

 `v1`에서 시작할 때, 스택에는 처음에 `v1`이 푸시된다. `v1`을 방문한 후, 인접한 `v2`와 `v3`가 스택에 푸시된다. 이후, `v2`가 스택의 맨 위에 있으므로 `v2`를 방문하고, `v2`의 인접 정점인 `v4`와 `v5`가 스택에 추가된다.

 

 

순환적 탐색 과정

DFS는 순환적인 탐색 과정을 가진다. 이는 v8에 도달한 후, 이전에 방문하지 않은 v5, v6, v7로 이동하는 것에서 잘 나타난다. v8에서 v5를 방문한 후, 다시 이전에 방문하지 않았던 v6과 v7을 방문한다. 이 과정이 모든 정점을 방문할 때까지 계속된다.

깊이 우선 탐색의 종료

탐색은 v7을 방문함으로써 모든 정점을 방문하게 되고, 이로써 DFS 탐색이 종료된다. 이 시점에서 스택은 비어있게 되며, 빈 스택은 더 이상 방문할 정점이 없음을 의미한다.

깊이 우선 탐색의 순회 과정

DFS의 핵심은 '스택'을 이용한 탐색이다. 방문할 정점들을 스택에 저장하고, 더 이상 방문할 정점이 없을 때 스택에서 하나를 꺼내어 방문한다. 이 방식으로, 깊이 우선으로 탐색이 이루어진다.

예시 2 -> v4를 시작점으로

 

이제, 동일한 [그림 1] 그래프에서 시작 정점을 v4로 설정하여 깊이 우선 탐색을 수행해 보자.

 

위의 그림처럼 방향을 살짝 틀어서 보면 쉽게 보인다.

 

탐색 경로의 변화

v4에서 출발하면, 탐색 순서는 v4, v8, v7, v3, v1, v2, v5, v6이 된다. 이 예시는 DFS가 시작 정점에 따라 어떻게 다른 경로를 탐색하는지 보여준다. v4에서 시작함으로써, 이전 예시와는 다른 순서로 정점을 방문한다.

 

그래프의 방향성 이해

v4를 시작점으로 설정함으로써, 그래프의 방향성이 달라지는 것처럼 보일 수 있다. v4에서 v8으로 이동한 뒤, 다른 정점들을 방문하는 과정은 v1에서 시작했을 때와는 전혀 다른 패턴을 보인다. 이는 DFS가 그래프의 연결 구조에 깊이 의존한다는 것을 입증한다.

 

순환적 탐색의 중요성

이 예시에서도 DFS의 순환적 탐색 방식이 중요하다. v8에서 v7, v3, v1 등을 순차적으로 방문하는 과정은 스택을 이용한 탐색의 효율성을 보여준다. 각 정점에서 다음에 방문할 정점을 스택에 저장하고, 필요에 따라 이를 꺼내 탐색을 계속한다.

 

깊이 우선 탐색의 다양성

이 예시를 통해 알 수 있는 중요한 점은, DFS가 그래프의 다양한 부분을 탐색할 수 있다는 것이다. 시작 정점을 변경함으로써, 우리는 그래프의 다른 영역을 먼저 탐색할 수 있다. 이는 DFS가 매우 유연한 탐색 방법임을 의미한다.

 

방향 그래프에서의 깊이 우선 탐색

 

 

그림 2

v1 v3
v1 v2
v3 v4
v4 v7 
v7 v8
v2 v5
v2 v6

 

이제, 방향이 있는 그래프에 깊이 우선 탐색을 적용해 보자. 

 

방향 그래프 탐색의 특징

방향 그래프에서 DFS를 수행할 때, 각 간선은 한 방향으로만 탐색이 가능하다. 이는 탐색 경로가 그래프의 간선 방향에 의존한다는 것을 의미한다.

 

그림 2의 DFS 예시

[그림 2]의 그래프에 v1을 출발점으로 설정하고 깊이 우선 탐색을 수행하면, 방문 순서는 v1, v3, v4, v7, v8, v2, v5, v6이 된다. 이 순서는 각 정점에서 가능한 방향으로만 이동할 수 있음을 보여준다.

 

순환적 탐색의 중요성

방향 그래프에서의 순환적 탐색은 특히 중요하다. 일단 v8에 도달하면, 다시 v2로 돌아가야 하는데, 이는 간선의 방향성에 따라 결정된다. 이 과정에서 스택의 사용은 다음 방문할 정점을 효과적으로 관리하는 데 중요한 역할을 한다.

 

코드 구현

1) 순환 호출을 이용하는 경우

void DFS(Graph* g, int s) {
    int i, adjacent;
    g -> visited[s] = 1;
    printf("%d", s);

    for (adjacent = 0; adjacent < g -> nv; adjacent++){
        if (g->adj[s][adjacent] && !g ->visited[adjacent]) {
            g-> visited[adjacent] = 1; 
            DFS(g, adjacent);
        }
   }
}

 

여기서 visited[]는 방문한 노드를 나타내기 위한 배열이다. 모든 정점 v에 대해 visited[v] = 1 이면 탐색을 종료한다.

 

인접 리스트를 통해 구현한 자바 코드는 다음과 같다.

 

import java.util.*;

class Graph {
    private int V;   // 정점의 개수
    private LinkedList<Integer> adj[]; // 인접 리스트

    // 생성자
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    // 간선 추가
    void addEdge(int v, int w) {
        adj[v].add(w); // v 정점에 w 정점을 인접 리스트로 추가
    }

    // DFS를 수행하는 함수
    void DFSUtil(int v, boolean visited[]) {
        // 현재 노드를 방문 처리하고 출력
        visited[v] = true;
        System.out.print(v + " ");

        // 현재 노드와 인접한 모든 노드들을 탐색
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // DFS 탐색을 시작하는 함수
    void DFS(int v) {
        // 방문 여부를 체크하기 위한 배열
        boolean visited[] = new boolean[V];

        // 재귀적으로 DFS 수행
        DFSUtil(v, visited);
    }
}

코드 설명

• Graph 클래스는 그래프의 인접 리스트를 표현한다. 정점의 수 V와 각 정점에 대한 인접 리스트 adj를 갖는다.
• addEdge 메소드는 그래프에 간선을 추가하는 기능을 수행한다.
• DFSUtil 메소드는 실제 깊이 우선 탐색을 재귀적으로 수행한다. 방문하지 않은 인접 정점들을 찾아 재귀적으로 탐색을 계속한다.
• DFS 메소드는 탐색을 시작하는 정점을 받아서 DFSUtil 메소드를 호출한다.

 

2) 스택을 직접 운영하는 경우

void DFS(int s){
    int v, w;
    extern struct stack *st;
    extern int visited[];
    InitializeStack(st);
    push(st, s);
    visited[s] = 1; 

    while((v=pop(st)) >= 0){
        visited[v] = 1;
        while(v에 인접한 모든 노드 w) {
            if (!visited[w]) {
                push(st,w);
            }
        }
    }
}

자바 코드는 다음과 같다.

import java.util.*;

class Graph {
    private int V;   // 정점의 개수
    private LinkedList<Integer> adj[]; // 인접 리스트

    // 생성자
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    // 간선 추가
    void addEdge(int v, int w) {
        adj[v].add(w); // v 정점에 w 정점을 인접 리스트로 추가
    }

    // DFS 탐색을 시작하는 함수 (스택 사용)
    void DFS(int s) {
        // 방문 여부를 체크하기 위한 배열
        boolean visited[] = new boolean[V];

        // 스택을 이용한 DFS
        Stack<Integer> stack = new Stack<>();
        stack.push(s);

        while (!stack.empty()) {
            s = stack.pop();
            if (!visited[s]) {
                visited[s] = true;
                System.out.print(s + " ");

                // 인접한 모든 정점을 스택에 푸시
                Iterator<Integer> itr = adj[s].listIterator();
                while (itr.hasNext()) {
                    int n = itr.next();
                    if (!visited[n])
                        stack.push(n);
                }
            }
        }
    }
}

코드 설명

• Graph 클래스는 그래프의 인접 리스트를 표현한다. 이 클래스는 정점의 수 V와 각 정점에 대한 인접 리스트 adj를 갖는다.
• addEdge 메소드를 통해 간선을 추가한다.
• DFS 메소드는 스택을 이용하여 깊이 우선 탐색을 수행한다. 방문하지 않은 정점을 스택에서 꺼내 방문하고, 그 정점에 인접한 모든 정점을 스택에 푸시한다.

 

 

---

 

참고 자료: 자료구조 (강태원, 정광식 공저, KNOU press 출판)