[Python] BFS(너비 우선 탐색 알고리즘)개념과 Python 예시

[ 출처- 위키피디아 ]

 

개념 정리

---

* 너비 우선 탐색 알고리즘(Breadth-First Search, BFS)

graph나 tree와 같은 자료 구조에 대한 탐색 알고리즘으로, 시작 노드에서 가장 가까운 노드들을 먼저 방문하고 그다음에 먼 노드들을 방문하는 방법입니다. BFS 알고리즘은 방문 순서 관리를 위하여 큐(Queue)라는 자료 구조를 사용하는데, 큐는 선입선출(FIFO), 즉 먼저 들어온 요소를 먼저 내보내는 방식입니다. 

* deque

deque는 'double-ended queue'의 약자로, 양쪽 끝에서 요소의 삽입과 삭제가 가능한 자료 구조입니다.
파이썬은 collections 모듈에서 deque를 import 하여 사용할 수 있습니다.

 

예시

---

1.  방문 탐색할 그래프

graph = {
    1: [2, 4],
    2: [1, 3, 6],
    3: [2, 4, 5],
    4: [1, 3, 7],
    5: [3, 6, 9],
    6: [2, 5],
    7: [4, 8],
    8: [7, 9],
    9: [5, 8]
}

 

2.  BFS로 그래프 탐색

from collections import deque

def bfs(graph, start):
    visited_node_set = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited_node :
            visited_node.add(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited_node_set)

    return visited_node_set


result = bfs(graph, 1)

print(result)  # 출력: {1, 2, 3, 4, 5, 6, 7, 8, 9}

 

 

---

https://en.wikipedia.org/wiki/Breadth-first_search

Breadth-first search - Wikipedia