코드 13-2는 크루스칼 알고리즘을 수행하는 메서드입니다.

코드 13-2

    def MST_kruskal(self):
        # 최종으로 만들 MST
        mst = Graph(self.vertex_num)

        # 크루스칼 알고리즘 적용
        return mst

최종 목적인 최소 비용 신장 트리를 표현하고자 그래프 객체를 생성하고, 여기에 add_edge 메서드를 사용하여 E(T)를 채워 넣은 후 반환할 것입니다. 크루스칼 알고리즘은 에지를 가중치에 따라 정렬해야 합니다. 이를 위해 edge_list를 따로 두었지요 self.edge_list.sort(key=lambda e: e.w)로 가중치에 따라 정렬하면 될 것입니다. 에지를 하나씩 가져와 신장 트리가 완성될 때까지 삽입하면 됩니다. 이때 가장 문제되는 것이 어떻게 사이클이 생성되는지 확인할 것인가 하는 점입니다. 다음 절에서는 사이클 형성을 확인할 수 있는 자료 구조로 분리 집합을 알아보겠습니다.