[Python] 깊이 우선 탐색 (Depth-First Search, DFS)

DFS란?

DFS는 깊이 우선 탐색 (Depth-First Search)로 그래프 탐색 알고리즘 중 하나입니다. 정점에서 자식들을 우선으로 탐색하는 알고리즘입니다. 자세한 내용은 https://brownbears.tistory.com/395 에서 설명이 되어 있습니다.

예제

아래와 같은 그래프가 있다고 가정합니다.

이 그래프를 DFS 알고리즘을 사용하여 모든 노드를 방문한다면 아래와 같은 구조로 탐색을 할 수 있습니다. 무조건 아래와 같은 결과가 나온다고 보장은 할 수 없습니다. (주어진 그래프(연결 노드의 순서)에 따라 방문 순서는 달라질 수 있습니다.)

여기선 방향을 아래, 왼쪽, 오른쪽 우선순위로 진행했는데 아래, 오른쪽, 왼쪽 순으로 진행해도 괜찮습니다. 아래 예시에서는 아래, 오른쪽, 왼쪽 의 우선순위를 가지고 설명합니다.

• 자세하게는 방문 → 오른쪽 자식 노드 이동 → (오른쪽 자식 노드가 없을 때) 왼쪽 자식 노드 이동 순입니다.

이러한 그래프를 만들기 위해 아래와 같은 형태로 주어졌다고 가정합니다.

graph = {
    'A': ['B', 'F', 'I'],
    'B': ['A', 'E', 'C'],
    'C': ['B', 'E', 'D'],
    'D': ['C', 'G', 'H'],
    'E': ['B', 'C', 'G'],
    'F': ['A', 'G'],
    'G': ['E', 'F', 'D'],
    'H': ['D'],
    'I': ['A']
}

DFS는 시작 노드에서 오른쪽 자식 노드를 방문해 나가다가 더이상 오른쪽 자식 노드가 없을 경우, 해당 부모의 왼쪽 자식 노드를 방문해 나가는 방식입니다. 이를 구현할 때, stack을 사용하면 구현이 간단해집니다.

def dfs(graph, start):
    visited_nodes = []
    adjacency_nodes = [start]

    while adjacency_nodes:
        node = adjacency_nodes.pop()
        if node not in visited_nodes:
            visited_nodes.append(node)
            adjacency_nodes.extend(graph[node])

    return visited_nodes

graph = {
    'A': ['B', 'F', 'I'],
    'B': ['A', 'C', 'E'],
    'C': ['B', 'D', 'E'],
    'D': ['C', 'G', 'H'],
    'E': ['B', 'C', 'G'],
    'F': ['A', 'G'],
    'G': ['D', 'E', 'F'],
    'H': ['D'],
    'I': ['A']
}

dfs(graph, 'A')
['A', 'I', 'F', 'G', 'E', 'C', 'D', 'H', 'B']

해당 결과는 위 예시 결과와 다른데 그 이유는 주어진 연결 노드의 리스트 순서가 어떻냐에 달려있습니다. 위 예시처럼 주어졌을 때, 아래와 같이 노드들을 깊이 탐색으로 진행한 것임을 알 수 있습니다.

만약 위에서 예시를 보여준 결과 순서대로 진행하려면 아래처럼 그래프를 반대로 설정해 주면 됩니다.

graph = {
    'A': ['I', 'F', 'B'],
    'B': ['E', 'C', 'A'],
    'C': ['E', 'D', 'B'],
    'D': ['H', 'G', 'C'],
    'E': ['G', 'C', 'B'],
    'F': ['G', 'A'],
    'G': ['F', 'E', 'D'],
    'H': ['D'],
    'I': ['A']
}

DFS의 시간 복잡도는 노드(N) 개수 + 탐색한 간선(E) 개수로 O(N+E) 입니다.