[알고리즘] BFS(너비우선탐색)

🧐 BFS란?

• Breadth First Search
• 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘
• 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용
• 준비물 : Queue(FIFO)

🎈 BFS 방법

BFS는 아래와 같은 간단한 알고리즘에 따라 작동한다.

1. 큐에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

맨 처음 노드(1)을 큐에 삽입한다. (빨간색으로 표시한 노드는 방문한 노드)

노드(2)와 노드(3)을 방문한 적이 없으므로 큐에 넣어준다.

큐에서 2를 꺼낸 직후에는 인접한 노드(1), (3), (4), (5) 중에서 (1)과 (3)은 방문한 적이 있으므로 패스하고 (4)와 (5)를 큐에 삽입한다.

큐에서 노드(3)을 꺼낸 뒤 인접한 노드인 (6)과 (7)을 삽입한다. 모든 노드가 방문처리 되었다. 남은 노드들을 큐에서 꺼내기만 하면 된다.

(1)부터 가까운 노드들부터 탐색이 이루어진다는 점에서 너비우선탐색(BFS)라고 한다.

🎈 BFS 코드 (파이썬)

# 방향이 있는 유향그래프
graph_list = {1: set([3, 4]),
	2: set([3, 4, 5]),
    3: set([1, 5]),
    4: set([1]),
    5: set([2, 6]),
    6: set([3, 5])}
    
 
root_node = 1

# BFS
from collections import deque

def BFS_with_adj_list(graph, root):
	visited = []
    queue = deque([root])
    
    while queue:
    	n = queue.popleft()
        if n not in visited:
        	visited.append(n)
            queue += graph[n] - set(visited)
    return visited

print(BFS_with_list(graph_list, root_node))

---

위 내용은 https://blog.naver.com/ndb796/221230944971 를 참고하여 작성되었습니다.
이미지 참고 : Wikimedia Commons