알고리즘/크루스칼알고리즘

크루스칼 알고리즘

MST : Minimum spaaning tree

그래프에서 최소비용으로 모든 구간을 연결한 트리

MST의 특징

1. 트리이기 때문에 CYCLE이 존재하면 안된다.
2. 여러개의 답이 나올 수 있다.

크루스칼 알고리즘 < KRUSKAL >

MST를 구하는 대표적인 알고리즘

시간복잡도는 O(NlogN) 여기서 N은 연결되는 간선의 수를 의미한다.

크루스칼 알고리즘 순서

1. 가중치 값을 기준으로 정렬을 먼저 한다.
2. UnionFind 자료구조를 이용하여 간선을 선택해준다.

과정

1. 그래프를 하드코딩한다.
2. V1,V2의 순서는 반대여도 상관 없다.

1. 정렬

1. 간선 선택