탐색기반 알고리즘 설계_3.깊이우선탐색(DFS)

3. 깊이우선탐색(Depth first search, dfs)

그래프 중 회로(cycle)가 없는 그래프를 트리라고 한다. 이 트리의 가장 위에 있는 정점에서 출발하여 모든 정점들을 깊이 우선으로 탐색한다.

출발 정점을 트리의 가장 위에 있는 정점으로 하고, 한 정점에서 이동 가능한 정점이 여러개 있을 경우 왼쪽 정점부터 방문한다고 가정하면, 단계별 탐색 과정은 다음과 같다.

탐색과정에서 3단계 이후 더이상 진행할 정점이 없어 더이상 진행하지 않는다.

이처럼 더이상 진행할 수 없을 때 다시 이전 정점으로 되돌아가는 과정이 필요한데, 일반적으로 이러한 과정을 백트랙(backtrack)이라고 한다.

백트랙은 비선형구조의 탐색에서 매우 중요하다. 백트랙은 스택(stack)이나 재귀함수(recursion)을 이용하면 쉽게 구현할 수 있다.

깊이우선 탐색 완료

※ 깊이우선탐색(DFS)은 먼저 시작 정점에서 간선을 하나 선택하여 진행할 수 있을 때까지 진행하고 더 이상 진행할 수 없다면 백트랙하여 다시 다른 정점으로 진행하여 더 이상 진행할 정점이 없을 떄까지 이 과정을 반복하는 탐색법. 간선으로 연결된 모든 정점을 방문할 수 있는 탐색법.

-소스

void dfs(int k)
{
    for (int i = 1; i <= n; i++)
    {
        if (arr[k][i] && !visited[arr[k][i]])
        {
            visited[arr[k][i]];
            dfs(arr[k][i]);
        }
    }
}