개요

그래프나 나무의 탐색에 이용되는 폭 우선 탐색과 깊이 우선 탐색에 대해서, Python에서의 구현을 이용하면서 소개합니다.

폭 우선 검색(Breadth First Search: BFS)

폭 우선 탐색(BFS)은 그래프에 있어서의 검색 방법의 일종으로, 주어진 node로부터 가까운 node를 순서대로 탐색해 갑니다. 깊이 우선 탐색(DFS)에서는 스택을 사용하는 반면, BFS는 큐를 사용하여 구현할 수 있습니다. 노드간의 최단 거리를 요구하고 싶을 때 등에 사용할 수 있습니다(변의 가중치의 유무, 유향/무향 등의 성질에 의해 실장이 바뀌어 오므로 주의). 다음은 파이썬 구현의 예입니다.

구현

BFS

# Make tree as follows:
#     1
#    / \
#   2   3
#  / \ / \
# 4  5 6  7

from collections import deque

class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

node1 = Node(1) # Root node
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

# キューを作成して初期ノード(root)を入れる
q = deque()
q.append(node1)

# キューが空になるまで繰り返す
while len(q) > 0:
    # キューの先頭（左端）からnodeを取り出す
    node = q.popleft()

    if node is not None:
        print(node.val)
        # nodeの子要素をキューの末尾（右端）に入れる
        q.append(node.left)
        q.append(node.right)

출력 결과

1
2
3
4
5
6
7

깊이 우선 검색(Depth First Search: DFS)

깊이 우선 탐색(DFS)은 그래프에 있어서의 검색 방법의 일종으로, 주어진 node로부터 가능한 한 멀리까지 탐색해 가는 수법입니다. 폭 우선 검색(BFS)에서는 대기열을 사용하는 반면 DFS는 스택 또는 재귀를 사용하여 구현할 수 있습니다. 다음은 파이썬 구현의 예입니다.

구현

DFS

# Make tree as follows:
#     1
#    / \
#   2   5
#  / \ / \
# 3  4 6  7

class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)

node1.left = node2
node1.right = node5
node2.left = node3
node2.right = node4
node5.left = node6
node5.right = node7

def traverse(node):
    if node is not None:
        print(node.val)
        # 子要素に対して再帰的に呼び出していく
        traverse(node.left)
        traverse(node.right)

traverse(node1)

출력 결과

1
2
3
4
5
6
7

보충

위와 같이 나무를 탐색하는 기법을 선행순회(pre-order)라고도 합니다. 그 밖에도 중간순순회(in-order), 후행순순회(post-order)등의 수법이 있으므로, 신경이 쓰이는 분은 조사해 보세요.