특정 데이터를 탐색할 때 너비를 우선으로 탐색을 수해하는 탐색 알고리즘

깊이/너비 우선탐색(DFS/BFS) 참고

특히 맹목적인 탐색을 하고자 할 때 사용가능한 탐색기법

최단경로 를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용

‘큐(Queue)'를 활용해 반복 구조로 구현

def iterative_bfs(graph, start_v): # start_v = 시작 정점
	'''모든 인접 간선을 추출 후 도착점인 정점을 큐에 삽입하는 코드'''
	discovered = [start_v] # discovered에는 이미 방문한 정점을 넣어준다
	queue = [start_v] # queue에는 다음으로 가야하는 점들을 넣어준다고 생각
	while queue: # queue에 요소가 있으면
		v = queue.pop(0) # 맨 앞 요소 추출
		for w in graph[v]:
			if w not in discovered:# w가 방문하지 않은 정점이라면
				discovered.append(w) # discovered에 넣고
				queue.append(w)# 다음 방문할 곳을 정하기 위해 큐에도 넣어줌
	return discovered

iterative_bfs(graph, 1) # [1, 2, 3, 4, 5, 6, 7]

1. discovered = [1]

   queue=[1]

   v = 1, queue=[ ]

   for w in graph[1]=[2, 3, 4]:

   discovered = [1, 2] → [1, 2, 3] → [1, 2, 3, 4]

   queue = [2] → [2, 3] → [2, 3, 4]

2. v = 2, queue = [3, 4]

   for w in graph[2]=[5]:

   discovered = [1, 2, 3, 4, 5]

   queue : [3, 4, 5]

3. v = 3, queue = [4, 5]

   for w in graph[3]=[5]:

   5 in discovered → if문 실행 x

4. v = 4, queue=[5]

   for w in graph[4]=[]

5. v = 5, queue=[]

   for w in graph[5] = [6, 7]:

   discovered = [1, 2, 3, 4, 5, 6]→ [1, 2, 3, 4, 5, 6, 7]

   queue = [6, 7]

6. v=6, queue=[7]

   for w in graph[6]=[ ]

7. v=7, queue = [ ]

   for w in graph[7] = [3]:

   3 in discovered → if문 실행 x

[그림으로 나타내면]