[Graph] Kruskal’s algorithm (크루스칼 알고리즘)

크러스컬 알고리즘(Kruskal’s algorithm)은 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 O(ElogV) 의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 크러스컬 알고리즘은 아래의 순서대로 작동한다. 그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F 을 만든다. 모든 변을 원소로 갖는 집합 S 를 만든다. S가 비어있지 않는 동안 가장 작은 가중치의 변을 S 에서 하나 빼낸다. 그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다. 그렇지 않다면 그 변은 버린다. 알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래..