[알고리즘] MST (최소 신장 트리)

Spanning Tree(신장 트리) ?

개념

• 그래프 내의 모든 노드을 포함하는 트리

• 모든 노드를 사이클 없이 연결하는 간선들을 모아놓은 트리

• 그래프의 최소 연결 부분 그래프

  • 최소 연결 = 최소의 간선

    n개의 노드를 n-1개의 간선으로 연결

특징

• DFS, BFS를 이용해서 찾을 수 있다.
  • 탐색 도중에 이용된 간선 모으기
• 하나의 그래프 -> 여러개의 spanning tree
• 사이클 X

MST(Minimum Spanning Tree) ?

개념

• Spanning Tree중에 간선의 가중치 합이 최소인 트리
• 단순히 가장 가중치가 작은 간선을 이용한다고 해서 최소 비용이 얻어지는 것은 아님

특징

• 간선의 가중치의 합이 최소
• n개의 노드을 가지는 그래프, n-1개의 간선만 이용
• 사이클 X

구현 방법

1. Kruskal(크루스칼) MST 알고리즘

• greddy method를 이용하여 최적의 MST를 구하는 것

각 단계마다 아래 조건에 근거하여 최소 비용 간선을 선택한다

1. MST가 최소 비용의 간선으로 구성됨
2. 사이클을 포함하지 않음

• 간선 선택을 기반으로 하는 알고리즘
• 이전 단계까지 만들어진 신장 트리와는 상관 없이 무조건 최소 간선만을 선택

과정

1. 그래프의 모든 간선들을 오름차순으로 정렬
2. 정렬된 간선들 중에서, 순서대로 사이클을 형성하지 않는 간선을 선택
   • 작은 간선을 먼저 선택
   • 사이클 형성하는 간선 제외
     • Union-find 알고리즘 이용
     • 추가할 새로운 간선의 양 끝 노드이 같은 집합에 속해있는지 확인해야 함
       • 같은 집합에 속해있으면 사이클이 형성됨
3. 2에서 선택된 간선을 MST의 집합에 추가한다

시간 복잡도

• 사이클 생성 여부를 union-find 알고리즘을 통해 검사하면, 시간복잡도는 간선들을 정렬하는 과정에 의해 좌우된다

  • 효율적인 퀵 정렬을 이용하면 O(eloge)

    간선 개수 e개

2. Prim(프림) 알고리즘

• 시작 노드에서부터 MST집합을 단계적으로 확장해나가는 방법
• 노드 선택을 기반으로 하는 알고리즘
• 이전 단계까지 만들어진 신장 트리를 확장

과정

1. 시작 노드만이 MST집합에 포함
2. 지금까지 만들어진 MST집합에 인접한 노드들 중에서 가중치가 최소인 간선으로 연결된 노드 선택, 트리 확장
   • 낮은 가중치 먼저 선택
3. MST집합이 n-1개의 간선을 가질 때 까지 반복

시간 복잡도

• 중첩되있는 반복문이 각각 n번씩 반복

• O(n^2)

  노드 개수 n개

참고 자료

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html