깊이 우선 탐색(DFS) & 너비 우선 탐색(BFS)

깊이 우선 탐색(Depth First Search)

깊이 우선 탐색한 결과 : 0 - 1 - 3 - 5 - 7 - 6 - 8 - 4 - 2
깊이 우선 탐색은 루트 노드를 스택에 넣고 탐색을 시작한다.

스택 안에 있는 노드 0 을 꺼내 출력한 후, 출력한 노드(0)의 자식노드를 스택에 넣는다. (이미 스택 안에 있는 자식은 스택에 넣지 않는다)

스택에서 노드를 하나 꺼내 출력한 후, 해당 노드의 자식노드를 스택에 넣는다. 스택에 남는 노드가 없을 때까지 반복한다.

(트리 순회에서 다룬 전위/중위/후위 순회는 모두 깊이 우선 탐색에 속한다)

DFS 구현

def dfs1(graph, start_node):
    visit = list()  
    stack = list()

    # 첫 번째 노드는 스택에 넣고 dfs를 시작한다.
    stack.append(start_node)

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

    return visit

깊이 우선 탐색은 스택으로 구현한다.
visit 리스트는 방문(출력)을 완료한 노드를 의미한다.
우선 첫 번째 노드를 스택에 넣고 깊이 우선 탐색을 시작한다.
스택 안에 값이 있으면, 스택에서 노드를 하나 꺼내 출력하지 않은 노드이면 출력한 후, 자식노드를 스택에 넣는다.

전체 코드는 github에 있습니다.

def dfsR(graph, start_node, visit):
    visit.append(start_node)
    print(start_node, end=' ')

    for node in graph[start_node]:
        if node not in visit:
            dfsR(graph, node, visit)

dfsR()함수는 깊이 우선 탐색을 재귀적으로 구현한 함수이다.
첫 번째 노드를 스택에 넣고 시작하는 것은 위의 dfs()함수와 동일하다.

너비 우선 탐색(Breadth First Search)

너비 우선 탐색한 결과 : 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
너비 우선 탐색은 루트 노드를 큐에 넣고 탐색을 시작한다.
깊이 우선 탐색과 동일하게 큐에서 꺼낸 노드를 출력하고, 출력한 노드의 자식 노드를 큐에 넣는다. 큐에 데이터가 없을 때까지 연산을 반복한다.

BFS 구현

def bfs(graph, start_node):
    visit = list()  
    queue = list()

    # 첫 번째 노드는 큐에 넣고 bfs를 시작한다.
    queue.append(start_node)
    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])

    return visit

너비 우선 탐색은 큐로 구현한다. 큐를 사용한다는 점을 제외하면 DFS와 동일하다.

from collections import deque

def bfs_deque(graph, root):
    visit = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        if node not in visit:
            visit.append(node)
            queue += graph[node] - set(visit)

    return visit

collections 모듈의 deque 사용해 bfs_deque()함수를 구현했다.
queue의 오른쪽에서 데이터를 삽입하고 왼쪽에서 제거한다.

전체 코드는 github에 있습니다.