코드 13-12는 프림 알고리즘을 구현한 코드입니다. BFS와 매우 유사하죠. 최소 힙에 시작 정점의 w를 0으로 넣어 준 후 최소 힙이 빌 때까지 정점을 계속 하나씩 꺼내 와 TV에 포함합니다. 인접 정점 중 트리 밖 정점에 대해 새로운 가중치가 기존 가중치보다 작다면 decrease_weight 연산을 하면 됩니다. 그림과 비교하면서 알고리즘을 살펴보기 바랍니다.
테스트 코드를 만들고 실행해 봅시다. 코드 13-13은 테스트 코드입니다.
코드 13-13
def print_edges(self):
for edge in self.edge_list:
print("({}, {}) : {}".format(edge.u, edge.v, edge.w))
if __name__ == "__main__":
g = Graph(6)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 2)
g.add_edge(0, 3, 8)
g.add_edge(1, 2, 5)
g.add_edge(1, 4, 12)
g.add_edge(2, 3, 7)
g.add_edge(2, 4, 17)
g.add_edge(3, 4, 4)
g.add_edge(3, 5, 14)
mst = g.MST_prim()
mst.print_edges()