최소 스패닝 트리

최소 스패닝 트리는 그래프를 이루는 에지 중 일부를 제거하여 트리 모양으로 만드는 것을 의미한다. 최소 스패닝 트리를 만드는 방법은 두 가지가 있는데, 하나는 크루스칼 알고리즘이고 다른 하나는 프림 알고리즘이다.

크루스칼 알고리즘은 모든 에지를 가중치 순으로 정렬한 뒤, 가중치가 작은 에지부터 그래프에 추가해 트리를 만드는 방식이다. 이 때 트리를 추가하는 기준이 오로지 에지의 가중치뿐이므로 잘못하면 사이클을 만들 수 있다. 사이클 방지를 위해선 각 노드의 부모 노드를 저장해야 하는데, 에지를 하나 추가할 때마다 에지에 연결된 두 노드에 대해 조상 노드, 즉 각 노드가 속한 트리의 루트 노드를 계산해야 한다. 만일 두 노드의 조상 노드가 같다면 에지를 추가했을 때 두 노드를 이동하는 경로가 둘 이상 생기게 되므로 해당 에지를 추가해선 안되고, 그렇지 않다면 어느 한 루트 노드의 부모 노드를 다른 루트 노드로 설정해 트리를 병합한 뒤 에지를 추가한다. 위 과정을 모든 에지에 대해 반복한다면 최소 스패닝 트리를 얻을 수 있다.

프림 알고리즘은 다익스트라 알고리즘의 변형으로, 랜덤한 노드 i를 시작 노드로 잡고 가중치가 작은 노드부터 차례로 트리에 더해 최소 스패닝 트리를 만드는 알고리즘이다. 이 때 이미 방문한 적 있는 노드로 이동하는 에지가 발견됐다면, 해당 에지를 추가했을 때 사이클이 생기므로 추가하지 않고 넘어간다. 이 과정을 모든 에지에 대해 반복한다면 최소 스패닝 트리를 얻을 수 있다.

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획