Kruskal, Prim, Sollin 알고리즘

최소비용 신장트리

- 최저의 비용을 갖는 신장트리

- Kruskal, Prim, Sollin 알고리즘이 있습니다.

갈망법(Greedy method)

- 최적의 해를 단계별로 구함

- 단계별로 판단 기준에 따라 최고의 결정을 내림

- 한번 내려진 결정은 롤백 불가하므로, 각 결정이 가능한 해를 도출해낼 수 있는지 확인

신장트리 제한 조건

- 그래프내에 있는 간선만 사용

- n-1개의 간선만을 사용

- 사이클을 생성하는 간선을 사용 금지

Kruskal 알고리즘

사이클을 생성하지 않는 간선들 중에서 가장 작은 가중치를 가지는 간선을 선택하여 만드는 알고리즘입니다.

Prim 알고리즘

최초 선택된 정점에 연결된 간선들 중에서 작은 가중치를 가지는 간선을 선택하여 만드는 알고리즘입니다.

Sollin 알고리즘

각 정점에 대해서, 정점에 연결된 가장 가중치 낮은 간선을 선택하여 단계별로 진행하여 만드는 알고리즘입니다.