BFS

루트노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

1. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
2. 즉 깊게 탐색하기 전에 넓게 탐색하는 것
3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함

EX) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 그 사이에 존재하는 경로를 찾는 겅우
깊이 우선 탐색을 사용하는 경우 - 모든 친구 관계를 다 살펴봐야할지도 모름
너비 우선 탐색의 경우 - 가장 가까운 관계부터 탐색

특징

BFS는 재귀적으로 동작하지 않는다.

이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다. 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

BFS는 방문한 노드들을 차례로 지정한 후 꺼낼 수 있는 자료구조인 큐를 사용함

즉 선입선출 FIFO 원칙으로 탐색

과정

깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

구현

• 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용하며, 구체적인 동작 과적은 다음과 같음

1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 수행할 수 없을 때까지 반복
   → 특정 조건에서의 최단경로 문제.

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

graph = [
	[],
	[2,3,8],
	[1,7]
]

visited = [False] * 9 

bfs(graph,1,visited)

출처
동빈나, 바킹독 블로그