Breadth-First Search, BFS
개요
시작 정점에서부터 모든 방향으로 한 칸 씩 뻗어나가며 탐색하는 방법입니다. 최단거리를 구할 때 쓰이기도 합니다.
구현
큐를 이용해 구현합니다. 큐에서 방문한 정점을 하나씩 뽑아서 아직 방문하지 않은 인접한 정점들을 큐에 넣는 방식입니다.
from collections import deque
def bfs(adj, start):
visited = [False] * len(adj)
visited[start] = True
queue = deque([start])
while queue:
current = queue.popleft()
for next_ in adj[current]:
if visited[next_]:
continue
visited[next_] = True # 방문
queue.append(next_)
