더북(TheBook)

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)

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.