크루스칼1
[알고리즘] MST / Disjoint set / 크루스칼 알고리즘
MST 알고리즘크루스칼과 프림 알고리즘은 MST 를 구하는 알고리즘 의 2종류이며, 그리디 알고리즘을 이용한다. MST 와 그리디 알고리즘의 정보는 : https://programming119.tistory.com/78 크루스칼 알고리즘 나무와 숲 -> 크루스칼 알고리즘은 각각의 노드를 나무로 생각하고, 모든 노드의 집합을 숲 이라고 생각한다. 숲에 나무들이 많다. 이 숲은 마법의 숲이라 나무끼리 손을 잡는다. 나무들끼리는 손을 잡을 수 있을 수도 있고, 나무들끼리 손을 잡으려면 마력을 소비하고 각각 나무들끼리 몇의 마력이 드는지는 정해져 있다. 예시) A 와 B 나무는 손을 잡을 때 3의 마력이 들고 , A와 C는 손을 잡을 때 10의 마력이 들고, B와 C는 손을 못 잡는다. 나무 : 노드 숲 : 노..