DFS 알고리즘(깊이 우선 탐색)

그래프 탐색은 어떤 정점을 찾거나 아니면 단순히 그래프를 순회하는 데 쓰인다.

어떤 그래프 탐색 이론이든 핵심은 지금까지 어떤 정점을 방문했는지 기록하는 것이다. 이렇게 하지 않으면 무한 사이클에 빠지고 만다.

 

사이클이 없는 트리에서는 발생하지 않지만, 그래프에서는 사이클이 있을 수 있으므로 이 문제를 해결해야 한다.

방문 배열을 사용하면 해결 할 수 있다.

 

* 깊이 우선 탐색 알고리즘의 동작

1. 그래프 내 임의의 정점에서 시작한다.

2. 현재 정점을 방문 배열에 표시한다.

3. 현재 정점의 인접 정점을 순회한다.

4. 방문했던 인점 정점이면 무시한다.

5. 방문하지 않았던 인접 정점이면 그 정점에 대해 재귀적으로 깊이 우선 탐색을 수행한다.

 

* 코드 구현

void DFS(int v) {
    // 정점을 방문배열에 방문표시한다.
    visited[v] = true;

    // 현재 정점의 인접 정점을 순회한다.
    for (int i=1; i<=N; i++) {
        if (visited[i]) continue; // 이미 방문한 정점이면 무시한다.
        if (A[v][i] == 0) continue; //값이 0이면 간선이 없으므로 무시한다.
        DFS(i); // 인접 정점에 대해 재귀 호출을 한다.
    }
}