개요
여러 정점과 간선들로 이루어진 양방향 그래프가 있을때
부분 그래프가 최소한의 간선들로 이루어 졌을때 Spanning Tree, 신장트리라고 한다. 즉 Spanning Tree는 내부에 사이클이 없는 그래프를 의미하는것이다.
사이클이 생기는 순간 불필요한 간선이 하나 더 있는것이니까.
여기에서 모든 간선들의 가중치합이 최소가 될때
최소 신장 트리, Minimum Spanning Tree, MST라고 한다.
이러한 MST는 네트워크 라우팅, 통신망 설계등 실생활에서 자주 사용되는 개념이다.
작동원리
- 최소 가중치의 간선들로만 이루어져야하므로,
가중치에대해 오름차순으로 정렬한다.- 사이클이 형성되는순간 최소의 간선갯수(스패닝 트리 조건)에 위배 되므로 사이클이 형성되지 않도록 간선을 선택.
위 두 과정을 동시에 진행하면된다.
이때 2번과정은 DSU알고리즘의 일부인 find, union함수를 가져다가 쓸 것이다. (DSU알고리즘 >> https://velog.io/@cldhfleks2/Disjoint-Set-UnionFind)
아래의 그림을 보자.
그래프와 그 간선들의 가중치를 오름차순 정렬을 했을때의 모습이다. 앞으로 가중치를 앞에서부터 작은 순서대로 선택할 것인데
이때 사이클이 생기면 선택하지 않는다.
맨 처음으로 가중치가 1인 간선을 선택하게 된다.
이때 사이클이 생기지않았으므로 다음 가중치인 3을 선택한다.
선택한 간선도 사이클을 형성하지 않으므로 MST에포함된다. 다음 간선인 4를 선택한다.
4를 선택하는 순간 사이클이 생기므로, 이 간선은 선택하지 않는다. 다음 간선인 5를 선택한다.
사이클이 형성되지 않았으므로 MST에 포함된다. 다음엔 7을 선택
앞과 마찬가지로 사이클이 형성되니 제외하고 다음인 10을 선택한다.
다음에는 15를 선택하면 사이클이 형성되니 20을 선택해보자.
하지만 20또한 사이클을 형성하므로 더이상의 간선은 선택하지않는다.
따라서 최종적인 MST는 아래와 같다.
이것이 처음 그래프에서 찾을 수 있는 가중치의 합이 최소인 부분그래프 MST가 된다.
구현
0. 노드의 루트노드번호를 저장하는 1차원배열
P[x]는 노드x의 루트노드번호가 무엇인지 저장하는 배열이다.
이것은 초깃값을 자기자신을 가진다.
P[x] = x;
1. find함수
하나의 노드의 부모노드를 경로압축하며 찾아서 리턴하는 함수이다.
자세한것은 DSU알고리즘에서 설명했다.(>> https://velog.io/@cldhfleks2/Disjoint-Set-UnionFind)
2. union함수
두 노드를 하나의 집합(루트노드를 동일하게)으로 묶는 함수이다.
묶을때 노드 번호가 더 낮은것으로 묶었다.
3. 두 노드의 루트노드가 동일한지 확인하는 함수
위에서 작성한 두 함수를 생각하면 두 노드의 루트노드를 비교하면 된다.
중요!! 여기서 return P[x] == P[y]로 비교하면 한번이라도 getParent를 실행한적이 없는 노드는 P[x] = x로 초기화된 상태이므로
오작동한다.
따라서 무조건 getParent(x) == getParent(y)로 비교해야한다.
4. 활용 예
가장 먼저 연결정보를 구조체를 이용하여 저장할것이다.
구조체는 아래와 같이 정의하였다.
이때 연산자 재정의부분이 중요!
다음으로 전체 예제에 대한 설명을 코드에 주석으로 달아놓았다.
관련문제
https://www.acmicpc.net/problem/1197 >> https://velog.io/@cldhfleks2/1197
