Breadth-First Search(BFS)

특징

• 너비 우선 탐색: 그래프에서 가까운 노드부터 우선적으로 탐색
• 큐 자료구조 이용
• 최단 경로 문제해결에 효과적

• 각 정점 방문 때마다 모든 인접 정점들을 검사
• 처음 보는 정점 발견 시 방문 예정 으로 기록
• 인접한 모든 정점 모두 검사하고 나면, 기록된 목록에서 다음 정점을 꺼내서 방문

동작 예시 및 파이썬 소스 코드

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True 	# 현재 노드 방문처리
    
    while queue: 		# 큐가 빌 때까지 반복
    	v = queue.popleft()	# 큐에서 원소 뽑아 출력
        print(v, end=' ')
        
        for i in graph[v]:	# 아직 방문하지 않은 원소들 큐에 삽입
        	if not visited[i]
            	queue.append(i)
                visited[i] = True

References

• 동빈나, 이코테 2021 강의 몰아보기 3.DFS & BFS, https://www.youtube.com/watch?v=7C9RgOcvkvo&list=LL&index=1&t=966s
• 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략