개념

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS를 구현할 떄 사용한 queue를 stack으로만 바꿔주면 똑같이 작동하므로 상세한 구현은 생략한다.

Python

BFS에서는 Queue를 구현하기 위해 deque 를 사용했지만, DFS에서는 stack을 그냥 list로 구현해도 된다.

기본 Pseudo Code

from collections import deque

def BFS(graph, root):
    visited = []
    stack = [root]
    while stack:
        n = stack.pop()
        if n not in visited:
            print("visit {}".format(n))
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

graph = {
    1: {2, 3},
    2: {3, 4},
    3: {4, 5},
    4: {2},
    5: set()
}
BFS(graph, 1)

back_to_top