예제는 크루스칼과 프림을 중심으로 살펴보자.
여기서는 구체적인 코드나 원리보다는, 그냥 스패닝 트리를 만들어 가는 과정을 살펴볼 것이다.
크루스칼과 프림의 큰 차이점은, 전체 그래프 어디서든 최소 비용 간선을 고르는 것과, 이미 만들어진 트리와 연결된 트리 중에서 고르는 것의 차이가 있다.
- 전체에서 최소 비용 간선 부터 만들어간다.
- 사이클을 만들 경우 트리에 추가하지 않는다.
- 전체에서 가장 비용이 작은 10으로 시작을 끊는다.
- 12, 14, 16 순으로 (f)까지 계속 완성
- 3번 노드와 6번 노드를 이어주는 18의 차례이나, 사이클을 형성하므로 폐기
- 다음으로 큰 숫자인 22를 선택한다
- 4, 6 노드를 잇는 24 코스트 간선도 사이클을 형상하므로 고르지 않음
- 계속 진행하여 완성..
- 시작 노드를 정한다.
- 이미 완성된 트리의 노드들과 연결된 간선 중 최소 비용 간선을 꺼낸다.
- 간선의 두 노드가 모두 트리에 속해있다면, 그 간선은 버린다.
프림은 모든 수행을 마치고 최소 스패닝 트리가 완성되지 않을 수도 있다!
즉, 수행이 끝나고도 n-1개의 간선이 사용되지 않을 수도 있다!! (주의)
노드 3에서 부터 시작한다.
- 3과 이어진 12, 18, 22 중에 가장 코스트가 작은 12 간선 부터 시작한다
- 2번 노드가 추가되면서 16 코스트 간선이 추가
- 이런 방식이 계속 반복된다.
- c에서 원래는 3번 6번 노드를 잇는 18이 선택 되는 것이 옳으나, 사이클을 형성하므로 22 코스트인 3-4 노드가 선택됐다.
직접 해본 예제
- 6번 노드에서 시작한다.
- 위와 같은 진행. 완성된 트리와 이어져있는 간선들 중 가장 코스트가 작은 것을 고른다
- 사이클을 만들면 다음 간선을 살핀다
- 계속 반복..
각 단계에서 여러 간선을 동시에 선택한다.
포레스트 안의 각 트리에 대해 하나의 간선을 선택한다. 선택하는 간선은 한 트리에 오직 하나의 정점만 속해야 한다. 선택된 간선은 구축중인 신장트리에 추가하고 오직 하나의 트리만이 존재하거나, 더 이상 선택할 간선이 없을 때 종료한다.
복잡하지만 성능이 좋다!
- Fundamentals of Data Structures in C++ <HOROWITZ, SAHNI, MEHTA 저>