1197 최소 스패닝 트리(MST)
문제 : 그래프가 주어졌을 때 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중 그 가중치의 합이 최소인 트리인 최소 스패닝 트리를 구하여라.
입력
- V (1 <= V <= 10000) - 정점의 개수
- E (1 <= E <= 100000) - 간선의 개수
가중치의 값의 range(-2,147,483,648 ~ 2,147,483,647)
출력
- MST의 가중치를 출력
Kruskal 알고리즘을 이용하였다. 이 알고리즘은 그리디 방식으로 간선 중에서 가장 가중치가 작은 것부터 탐색하게 된다.
주의할 점은 사이클이 생기면 안된다는 것이다.(트리의 정의)
이를 해결하기 위해 유니온 파인드를 같이 사용한다.
각 정점을 집합으로 두고 간선에 의해 합쳐지면 그 두 정점이 속한 집합을 하나의 집합으로 다시 묶는 방식이다.
a b w
1 - 1 2 1
2 - 2 3 2
3 - 3 1 3 이렇게 입력이 주어진 상태에서 가중치(w)가 가장 작은 것은 1번 째 간선일 것이다.
1과 2는 현재 다른 집합이므로 합쳐준다.
다음 에는 2번 째 간선을 체크한다. 2번 째 간선의 경우 2와 3은 다른 집합이므로
1과 2가 속해있는 집합과 3을 합쳐준다.
마지막으로 3번 째 간선을 보면 1과 3은 같은 집합에 있으므로 무시한다.
coding chobo