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>


<syntaxhighlight lang="c">

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

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

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

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

</syntaxhighlight>

==각주==