코드 13- 7은 크루스칼 알고리즘을 구현한 코드입니다. 주목할 부분은 while 문의 조건입니다. 에지 개수가 정점 개수보다 1 작으면 트리가 완성되므로 이 조건을 만족하면 while 문을 빠져나옵니다. 사이클이 형성되는지 여부를 판단하는 collapsing_find 함수와 두 집합을 병합하는 weighted_union 함수를 주의 깊게 살펴보기 바랍니다.
테스트 코드를 작성해서 잘 작동하는지 확인해 봅시다.
코드 13-8
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_kruskal()
mst.print_edges()