최소 신장 트리(MST)
신장 트리 (Spanning Tree)
최소 신장 트리에 앞서 신장 트리란 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프이다.
신장트리의 조건은 다음과 같다.
- 본래의 그래프의 모든 노드를 포함해야 함
- 모든 노드가 서로 연결
- 트리의 속성을 만족시킴 (사이클이 존재하지 않음)
최소 신장 트리 (Minimum Spanning Tree)
가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭한다.
최소 신장 트리의 특징은 다음과 같다.
- 간선의 가중치의 합이 최소여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
최소 신장 트리 알고리즘 중 대표적인 알고리즘이 크루스칼 알고리즘과 프림 알고리즘이다
크루스칼 알고리즘 (Kruskal Algorithm)
가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 스패닝 트리를 찾음으로써 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이다.
- 모든 간선들의 가중치를 오름차 순으로 정렬
- 가중치가 가장 작은 간선을 선택
- 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
- 이 과정을 반복
프림 알고리즘 (Prim Algorithm)
시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하며 신장 트리를 확장 시키는 알고리즘으로 정점 선택을 기반으로 한다.
- 임의의 간선을 선택
- 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택
- 모든 정점이 선택될 때까지 반복
참고
https://velog.io/@dnjscksdn98/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html