최소 신장 트리(MST) 크루스칼 알고리즘

해당 알고리즘을 구현하기 위해서는 Union -Find를 먼저 이해하셔야 합니다! 보러가기 -- > https://blog.naver.com/steadydeveloper/223291558708 최소 신장 트리란?

Minimum Spanning Tree : 모든 노드가 연결되어 있으면서 엣지의 가중치를 최소한으로 사용하는 트리를 말합니다. 이렇게 말하면 이해가 잘 안될테니 만약 섬이 5개 있고 각각 한 섬에서 다른 모든 섬까지 갈 수 있도록 다리를 놓는다고 할 때 이 다리의 길이 합이 최소가 되도록 짓는 경우를 생각하면 이해가 편하실거에요.

N개의 섬을 연결한다면 N-1개의 다리를 놓는것이 모든 섬을 연결할 수 있으면서 최소한의 비용이 듭니다. 트리는 사이클이 없는 그래프로 정의 할 수 있죠?

즉, 사이클이 발생하면 안됩니다. 사이클이 발생했다면 결국 모든 섬을 연결하는데 N개 이상의 다리가 필요하고 그것은 최소가 아니기 때문 그렇기에 최소 신장 그래프가 아니라 최소 신장 트리인가봅니...