[알고리즘] BFS 알고리즘

정의

루트 노드에서 시작해서 가장 가까운 노드부터 찾는 알고리즘

BFS (Breadth First Search) 약자로 한국어 표기로는 "넓이 우선 탐색" 또는 "너비 우선 탐색" 이라고 한다.

코드 구현

from collection import deque

def bfs(index, graph, visited):

	queue = deque([index])
	
	while queue:
		v = queue.popleft()	
		visited[v] = True
		for i in range(len(graph)):
			if visited[i] == False:
				queue.append(i)
	return visited

DFS vs BFS

그림으로 보면 차이점이 명확해질 것이다.

출처 : 나무위키