BFS (Breadth First Search) 설명

BFS의 경우 DFS와 달리 재귀적으로 처리되지 않고 queue를 사용하여 탐색할 노드의 순서를 저장한다.

이번 포스팅에서는 BFS를 통해 어떻게 node를 탐색하는지에 대해 알아보도록 한다.

 

Binary Tree 기반 BFS

기본적인 Binary Tree 형태로 넓이 우선으로 탐색하는 과정을 살펴보자.

Tree는 좌측에 있는 그림과 같은 형태라고 하면, 우측의 화살표 순으로 탐색을 해야한다.

 

1. 먼저 탐색해야할 node queue에 root node를 추가한다.

 

2. 탐색해야할 node queue를 보고 node 탐색 iteration이 시작된다.

2.1) (왼쪽) queue를 pop하니 node1을 탐색해야하기 때문에 node1을 탐색한다.

       (오른쪽) 탐색한 뒤 node1과 연결된 node들(node2, node3)을 탐색해야할 node queue에 추가한다.

 

2.2) (왼쪽) queue를 pop하니 node2를 탐색해야하기 때문에 node2를 탐색한다.

        (오른쪽) 탐색한 뒤 node2와 연결된 node들(node4, node5)을 탐색해야할 node queue에 추가한다.

 

2.3) (왼쪽) queue를 pop하니 node3를 탐색해야하기 때문에 node3를 탐색한다.

        (오른쪽) 탐색한 뒤 node3과 연결된 node들(node6, node7)을 탐색해야할 node queue에 추가한다.

 

2.4) (왼쪽) queue를 pop하니 node4를 탐색해야하기 때문에 node4를 탐색한다.

                  하지만 leaf node 이기 때문에 추가로 탐색할 노드가 없어 queue에 node를 추가하지 않는다.

        (오른쪽) queue를 pop하니 node5를 탐색해야하기 때문에 node5를 탐색한다.

                     하지만 leaf node 이기 때문에 추가로 탐색할 노드가 없어 queue에 node를 추가하지 않는다.

 

2.5) (왼쪽) queue를 pop하니 node6를 탐색해야하기 때문에 node6를 탐색한다.

                  하지만 leaf node 이기 때문에 추가로 탐색할 노드가 없어 queue에 node를 추가하지 않는다.

        (오른쪽) queue를 pop하니 node7을 탐색해야하기 때문에 node7을 탐색한다.

                     하지만 leaf node 이기 때문에 추가로 탐색할 노드가 없어 queue에 node를 추가하지 않는다.

 

3. queue가 비어있어 탐색이 종료된다.

 

위 탐색 과정을 코드로 나타내면 아래와 같다.

우선 위 Tree를 코드로 옮기자.

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


node_1 = Node(1)

node_2, node_3, node_4 = Node(2), Node(3), Node(4)
node_1.left, node_1.right = node_2, node_3

node_4, node_5 = Node(4), Node(5)
node_2.left, node_2.right = node_4, node_5
node_6, node_7 = Node(6), Node(7)
node_3.left, node_3.right = node_6, node_7

 

그리고나서 탐색을 수행한다.

코드를 따로 옮겨놓고 위에 그림 설명을 보며 각 iteration을 머릿 속에 그려가면서 이해해도 좋다.

from collections import deque


def bfs(root):
    queue = deque()
    queue.append(root)  # 1) 탐색해야할 node queue에 root node 추가

    while queue:
        node = queue.popleft()  # 2) 탐색해야할 node 가져오기
        print(f"node: {node.val}")

        # 3) 연결된 node를 탐색해야할 node queue에 추가
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

    # 4) 탐색해야할 node가 없으면 종료

bfs(node_1)

 

Graph 기반 BFS

Graph 기반의 BFS도 동일하게 queue를 사용하여 탐색할 node의 순서를 관리한다.

 

하지만 앞서 살펴본 Binary Tree의 경우 root에서 leaf로의 단방향 탐색이기 때문에 단순한 편인 반면,

Graph의 경우 방향성없이 여러 노드가 서로 연결되어있기 때문에 중복으로 탐색하지 않게하는 연산이 추가된다.

 

Graph가 좌측에 있는 그림과 같은 형태라고 하면, 우측의 화살표 순으로 탐색을 해야한다.

 

 

1. 먼저 탐색해야할 node queue에 root node를 추가한다.

   추가로 중복 탐색을 막기위해 확인한 node 목록 에도 root node를 추가한다.

 

2. 탐색해야할 node queue를 보고 node 탐색 iteration이 시작된다.

2.1) (왼쪽) queue를 pop하니 node1을 탐색해야하기 때문에 node1을 탐색한다.

       (오른쪽) 탐색한 뒤 node1과 연결된 node들(node2, node3, node4)을 탐색해야할 node queue에 추가한다.

                     중복 탐색을 막기위해 확인한 node 목록 에 node2, node3, node4를 추가한다.

 

2.2) (왼쪽) queue를 pop하니 node2를 탐색해야하기 때문에 node2를 탐색한다.

       (오른쪽) 탐색한 뒤 node2과 연결된 node들(node1, node5, node6)을 탐색해야할 node queue에 추가한다.

                     하지만 이미 node1은 확인하였기 때문에 추가하지 않는다. (node5, node6 만 추가)

                     중복 탐색을 막기위해 확인한 node 목록 에는 node2, node3만 추가한다.

 

2.3) (왼쪽) queue를 pop하니 node3를 탐색해야하기 때문에 node3를 탐색한다.

       (오른쪽) 탐색한 뒤 node3와 연결된 node들(node1, node6)을 탐색해야할 node queue에 추가한다.

                     하지만 이미 node1, node6는 확인하였기 때문에 아무 node도 추가하지 않는다.

                     중복 탐색을 막기위해 확인한 node 목록 에도 아무 node도 추가하지 않는다.

 

2.4) (왼쪽) queue를 pop하니 node4를 탐색해야하기 때문에 node4를 탐색한다.

       (오른쪽) 탐색한 뒤 node4와 연결된 node들(node1)을 탐색해야할 node queue에 추가한다.

                     하지만 이미 node1은 확인하였기 때문에 아무 node도 추가하지 않는다.

                     중복 탐색을 막기위해 확인한 node 목록 에도 아무 node도 추가하지 않는다.

 

2.5) (왼쪽) queue를 pop하니 node5를 탐색해야하기 때문에 node5를 탐색한다.

       (오른쪽) 탐색한 뒤 node5와 연결된 node들(node2)을 탐색해야할 node queue에 추가한다.

                     하지만 이미 node2는 확인하였기 때문에 아무 node도 추가하지 않는다.

                     중복 탐색을 막기위해 확인한 node 목록 에도 아무 node도 추가하지 않는다.

 

2.6) (왼쪽) queue를 pop하니 node6를 탐색해야하기 때문에 node6를 탐색한다.

       (오른쪽) 탐색한 뒤 node6와 연결된 node들(node2, node3)을 탐색해야할 node queue에 추가한다.

                     하지만 이미 node2, node3는 확인하였기 때문에 아무 node도 추가하지 않는다.

                     중복 탐색을 막기위해 확인한 node 목록 에도 아무 node도 추가하지 않는다.

 

3. queue가 비어있어 탐색이 종료된다.

 

위 탐색 과정을 코드로 나타내면 아래와 같다.

from collections import deque


graph = {
    "1": ["2", "3", "4"],
    "2": ["1", "5", "6"],
    "3": ["1", "6"],
    "4": ["1"],
    "5": ["2"],
    "6": ["2", "3"]
}

def bfs():
    visited = []

    queue = deque()
    queue.append("1")  # 1) 탐색해야할 node queue에 root node 추가
    visited.append("1")

    while queue:
        node = queue.popleft()  # 2) 탐색해야할 node 가져오기
        print(f"node: {node}")

        connections = graph[node]
        for connection in connections:  # 3) 인접 노드 확인
            if connection not in visited:  # 4) 인접 노드가 이미 확인한 노드인지 확인
                queue.append(connection)  # 5) 방문해야할 노드 queue에 추가
                visited.append(connection)  # 6) 확인한 노드 목록에 추가
                
    # 7) 탐색해야할 node가 없으면 종료

bfs()