DFS 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[Graph|알고리즘 설계와 분석]]

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

==DFS Code==
===Data Structures for BFS===
BFS를 구현하기 위해 필요한 자료구조는 3가지이다:
<syntaxhighlight lang="c">
bool processed[MAXV+1];   // 이미 완전히 처리된 정점 
bool discovered[MAXV+1];  // 발견되었지만 방문되지 않은 정점 
int parent[MAXV+1];       // 해당 정점을 방문하기 전의 부모 노드
</syntaxhighlight> 
processed[] 배열은 어떤 정점 v의 모든 인접 노드들이 모두 발견되었을때 true로 설정된다. 즉, 이 노드로부터 나가는 간선들은 모두 처리 완료됐다는 의미이다. BFS에서 processed[] 배열은 중복된 간선 처리나 사이클 검출을 막는 역할을 한다.

===Implementing DFS===
DFS 알고리즘은 보통 재귀적으로 구현된다. 이에 따라 스택 자료구조를 명시적으로 사용할 필요가 없는데, [[Procedure call|재귀 호출]]이 스택과 같이 동작하기 때문이다. 아래는 DFS 알고리즘을 구현하는 C언어 코드이다:
<syntaxhighlight lang="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;      // 완전히 처리 완료
}
</syntaxhighlight>

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

===Edge Classification for DFS===


===Edge Classification Implementation===

<syntaxhighlight lang="c">

</syntaxhighlight>
<syntaxhighlight lang="c">

</syntaxhighlight>
<syntaxhighlight lang="c">

</syntaxhighlight>
<syntaxhighlight lang="c">

</syntaxhighlight>
<syntaxhighlight lang="c">

</syntaxhighlight>

==각주==