5.3.2 깊이 우선 검색

BFS는 레이어별로 버텍스를 방문합니다. 이와 달리 깊이 우선 검색(Depth-First Search, DFS)은 개별 경로를 하나씩 끝까지 탐색합니다. 선택한 경로의 끝에 도달하면 DFS는 그 과정에서 방문한 모든 버텍스들을 방문 완료 처리합니다. 그리고 걸어온 길을 되돌아 나와 경로를 시작한 버텍스로 이동합니다. 이 버텍스에 아직 방문하지 않은 또 다른 경로가 있다면 이에 대한 탐색을 시작합니다. 더 이상 새로운 경로가 없다면 알고리즘을 종료합니다.

어떤 그래프는 순환 경로를 가지기도 합니다. 불(boolean) 플래그를 사용하여 버텍스 방문 기록을 관리하면 순환 경로에 빠지는 것을 방지할 수 있습니다.

DFS는 2장에서 다룬 스택을 사용합니다. 스택은 후입선출 방식으로 데이터를 관리합니다. BFS가 사용하는 큐는 선입선출 방식입니다.

DFS의 코드 구현은 다음과 같습니다.

[in :]

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited