[보기 쉬운 Algorithm] 너비 우선 탐색(BFS) - Python

너비 우선 탐색(Breadth First Search)은 연결된 노드를 연속적으로 쫓아서 찾는 것이 아닌 연결된 노드들을 모두 탐색한 후 그다음 연결 노드를 탐색한다.

 

[graph]

예를 들어 위와 같은 경우 'A'에서 탐색을 시작하면 'A'와 연결된 'B', 'D', 'F'를 먼저 찾고, 다음 'B'와 연결된 'C', D와 연결된 'G', 'C'와 연결된 'E'를 찾는 것이다. 따라서 순서는 ['A', 'B', 'D', 'F', 'C', 'G', 'E']가 된다.

<구현>

def bfs(graph, start_node):
    visit = []
    queue = []

    queue.append(start_node)

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

    return visit

 

visit는 방문한 노드를 저장한다. 이는 방문했던 노드를 다시 방문하지 않게 하기 위함이다.

queue는 다음 방문할 노드를 저장한다. 즉, queue에 아무 내용이 없다면 모든 연결 노드를 방문한 것이다.

 

시작을 위해 처음 방문할 노드인 start_node를 queue에 넣는다.

 

방문할 노드인 queue에 있는 노드를 빼와서 이미 방문했는지 visit에서 확인한다. 없다면 visit에 해당 노드를 넣어 지금 방문함을 알리고, 해당 노드와 연결된 노드를 이어서 방문해야 하므로 graph [node]에서 연결된 노드를 찾아 queue에 넣어준다.

 

큐에 들어가고 나오는 순서를 보면 BFS와 DFS의 차이가 있다. queue에 앞에 있는 것 부터 빠져나간다. 예를 들어 A를 탐색하면 연결된 [B, D, F]가 큐에 들어간다. 앞에 있는 B를 탐색하면 연결된 C가 queue에 추가되어 [D, F, C] 순서가 된다. 따라서 이러한 방법으로 연속적으로 연결된 노드를 찾는 것이 아닌, queue에 추가한 순서대로 빠지게 된다.

<예시>

graph = {
    'A': ['B', 'D', 'F'],
    'B': ['C'],
    'C': ['E'],
    'D': ['C', 'G'],
    'E': [],
    'F': ['G'],
    'G': ['E']
}

print(dfs(graph, 'A'))

 

위 그림과 같은 그래프이다.

 

<결과>

['A', 'B', 'D', 'F', 'C', 'G', 'E']

 

참고

깊이 우선 탐색(DFS)은 아래의 링크를 참고

 

2021.03.19 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 깊이 우선 탐색(DFS) - Python

[보기 쉬운 Algorithm] 깊이 우선 탐색(DFS) - Python