DFS

상위 문서: 알고리즘 설계와 분석

개요

DFS(Depth-First Search) 알고리즘은 시작 정점에서 출발해서 한 방향으로 갈 수 있을 때까지 계속 이동하고, 더 이상 갈 곳이 없으면 바로 이전 단계로 되돌아(backtrack) 가서 다른 경로를 탐색하는 알고리즘이다. DFS 알고리즘의 핵심은 백트래킹(backtracking)이며, 모든 가능한 경로를 포괄적으로 탐색(exhaustive search)할 수 있다.

DFS Code

Data Structures for BFS

BFS를 구현하기 위해 필요한 자료구조는 3가지이다:

bool processed[MAXV+1];   // 이미 완전히 처리된 정점 
bool discovered[MAXV+1];  // 발견되었지만 방문되지 않은 정점 
int parent[MAXV+1];       // 해당 정점을 방문하기 전의 부모 노드

processed[] 배열은 어떤 정점 v의 모든 인접 노드들이 모두 발견되었을때 true로 설정된다. 즉, 이 노드로부터 나가는 간선들은 모두 처리 완료됐다는 의미이다. BFS에서 processed[] 배열은 중복된 간선 처리나 사이클 검출을 막는 역할을 한다.

Implementing DFS

DFS 알고리즘은 보통 재귀적으로 구현된다. 이에 따라 스택 자료구조를 명시적으로 사용할 필요가 없는데, 재귀 호출이 스택과 같이 동작하기 때문이다. 아래는 DFS 알고리즘을 구현하는 C언어 코드이다:

void dfs(graph *g, int v) {
    if (finished) return;     // 탐색 종료 조건 (예: 특정 목표를 찾은 경우)

    discovered[v] = true;     // v를 처음 방문
    process_vertex_early(v);  // v 방문 직후 처리

    p = g->edges[v];          // v의 인접 리스트 시작점
    while (p != NULL) {       
        y = p->y;             // v와 연결된 정점 y
        if (!discovered[y]) { // 아직 방문하지 않았다면
            parent[y] = v;    // 부모 설정
            process_edge(v,y);// 간선 처리
            dfs(g, y);        // 재귀 호출 (깊이 탐색)
        } else if ((...조건...)) {
            process_edge(v,y);// 이미 방문된 노드일 경우 (역방향 등)
        }
        if (finished) return; // 조기 종료
        p = p->next;          // 다음 간선으로
    }

    process_vertex_late(v);   // v에서 더 이상 갈 곳이 없을 때 처리
    processed[v] = true;      // 완전히 처리 완료
}

Finding Paths

DFS는 정점을 처음 발견했을 때 “누가 이 정점을 발견했는지”를 parent[] 배열에 기록한다:

• parent[i] = 정점 i를 처음 큐에 넣게 만든 “직전의” 정점(발견자).
  • 시작 정점 s는 보통 parent[s] = -1로 표시함.
• 모든 parent 화살표를 모으면, 시작 정점을 루트 노드로 하는 “발견 트리(discovery tree)”가 생김
  • 이 트리는 탐색 순서를 보존함. 즉, 어떤 정점이 어떤 정점을 통해 처음 도달되었는지를 담고 있어, 경로 복원 등에 사용됨.

아래는 parent[]를 이용해 끝점에서 시작점으로 거꾸로 따라가면 경로를 복원하는 함수이다:

void find_path(int start, int end, int parents[]) {
    if ((start == end) || (end == -1)) { //루트 노드에 도달
          printf("\n%d", start);
    } else {
        find_path(start, parents[end], parents); //end의 부모 쪽으로 한 칸 올라가서 해당 경로 출력
        printf(" %d", end);
    }
}

DFS with Graph

DFS 알고리즘은 탐색하는 그래프의 간선들의 구조를 조직화한다. DFS를 수행하면 그래프의 모든 간선이 “방문 순서”에 따라 방향성을 가진다. 즉, undirected 그래프를 탐색하더라도 “어떤 정점이 다른 정점을 처음 발견했는가”에 따라 간선의 방향이 결정된다. Figure 1은 원래의 undirected 그래프로부터 DFS 알고리즘을 수행하여 DFS 트리 자료구조를 만드는 것을 보여준다.

Edge Classification for DFS

DFS 알고리즘을 실행하여 어떤 그래프를 탐색하는 과정에서 탐색하는 그래프의 간선들은 아래와 같이 4가지로 분류된다:

1. Tree Edge: DFS 트리에서 새 정점을 발견하는 간선(해당 간선의 집합은 DFS 트리를 구성)
2. Forward Edge: 이미 방문한 정점으로 향하지만, 자신의 “자손”인 경우
3. Back Edge: 자신의 “조상”으로 되돌아가는 간선.(사이클이 존재함을 의미)
4. Cross Edge: DFS 트리의 서로 다른 가지(branch) 사이를 연결하는 간선

이와 같은 구분은 figure 2가 잘 보여준다. 아래는 DFS 실행 중 각 간선을 만날 때 호출되어, 간선의 성격을 자동으로 분류하는 함수이다:

int edge_classification(int x, int y) {
    if (parent[y] == x) return TREE;
    if (discovered[y] && !processed[y]) return BACK;
    if (processed[y] && entry_time[y] > entry_time[x]) return FORWARD;
    if (processed[y] && entry_time[y] < entry_time[x]) return CROSS;
    printf("Warning: self loop (%d,%d)\n", x, y);
    return -1;
}

이때 DFS가 undirected 그래프를 탐색하는 경우, forward/cross edges는 존재하지 않는다.

Applications of DFS

DFS는 단순히 “모든 노드를 탐색하는 알고리즘”에 그치지 않고, 그래프의 구조적 특성을 분석하는 도구로서 매우 강력하게 활용된다. 특히 Cycle Detection 문제와 Articulation Vertices 문제를 해결하는데에 자주 사용된다:

• Cycle Detection: 그래프에 cycle이 존재하는가를 판별.
• Articulation Vertices: 어떤 노드를 제거하면 그래프가 별개의 그래프들로 구분되는지.

Finding Cycles

DFS 알고리즘을 통해서 사이클을 찾는 방법은 DFS 중 발견되는 “Back Edge”를 활용하는 것이다. 이는 아래와 같은 과정을 필요로 한다:

1. DFS 알고리즘에 따라 어떤 정점 x를 방문한다.
2. 어떤 정점 x에서 아직 탐색이 완전히 끝나지 않은 조상 정점 y로 향하는 간선을 만나면, 해당 간선은 back edge에 해당한다.
3. Back edge의 존재는 cycle이 존재한다는 것을 의미한다.

아래는 이를 구현하는 C언어 코드이다:

void process_edge(int x, int y) {
    if (parent[y] != x) {   /* found back edge! */
        printf("Cycle from %d to %d:", y, x);
        find_path(y, x, parent);
        finished = true;
    }
}

위 코드에서 부모 자식 관계가 아닌데, 이미 방문한 노드를 만났다면 이는 back edge이므로 이에 따라 사이클이 발견되었음을 출력한다. 또한 find_path() 함수가 활용되었는데, 이는 DFS 트리 상에서 y에서 x로 이어지는 경로를 따라가며