특정 데이터를 탐색할 때 너비를 우선으로 탐색을 수해하는 탐색 알고리즘
특히 맹목적인 탐색을 하고자 할 때 사용가능한 탐색기법
최단경로 를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용
‘큐(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]
Python
복사
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
[그림으로 나타내면]
