[Python] 최소 스패닝 트리(MST), 크루스칼 알고리즘 (Kruskal Algorithm)
신장 트리 (Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 N개의 노드로 만드는 스패닝 트리는 N-1개의 노드로 구성되어 있다. 유니온 파인드 알고리즘을 활용하여 사이클을 검사할 수 있고, 이를 활용하여 스패닝 트리를 만들 수 있다. 이중 최소한의 비용으로 구성된 스패닝 트리를 최소 스패닝 트리 (MST) 라고 한다. 최소 스패닝 트리를 구하는 알고리즘으로 크루스칼, 프림 알고리즘이 있는데 크루스칼 알고리즘을 다뤄보겠다. 크루스칼 알고리즘 (Kruskal Algorithm) 핵심 원리 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다. 다만 사이클을 발생시키는 간선은 제외하고 연결한다. [1] 간선 비용에 따라 오름차순으로 정렬 [2..
