14.2 BFS와 프림 알고리즘, 그리고 데이크스트라 알고리즘
BFS와 프림 알고리즘, 데이크스트라 알고리즘은 그 구조가 굉장히 비슷합니다. BFS에서는 큐를 사용하고 프림 알고리즘과 데이크스트라 알고리즘에서는 우선순위 큐를 사용한다는 정도의 차이만 있습니다. 이 절에서는 코드 분석에 불필요한 부분을 제거하고 싣겠습니다. 얼마나 닮아 있는지 직접 비교해 보기 바랍니다.
코드 14-5는 BFS 알고리즘입니다.
코드 14-5
def bfs(self, v):
q = Queue()
q.put(v)
while not q.empty():
v = q.get()
adj_v = self.adj_list[v]
for u in adj_v:
if not self.visited[u]:
q.put(u)