MST 알고리즘(크루스칼, 프림)

최소비용 신장트리 (Minimum Spanning Tree, MST)

MST의 특징

1. 신장트리: 그래프의 모든 정점을 포함하며, 사이클이 없는 트리입니다.
2. 최소 비용: 간선 가중치의 합이 최소가 되는 트리입니다.
3. 유일성: 모든 간선의 가중치가 서로 다르면 MST는 유일합니다. 즉 여러 경로가 나올 수 없다는 것이다.

MST 알고리즘

MST를 구하는 알고리즘은 다음과 같은 두 가지 주요 방법이 있다.

1. 크루스칼 알고리즘 (Kruskal’s Algorithm)

출처:wikimedia

• 방법: 간단하게 생각하면 sort하고 sort순서대로 간선연결하고 cycle이 발생하는지 검증만 하면 끝이다.
  1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다.
  2. 최소 가중치의 간선부터 하나씩 추가합니다.
  3. 사이클이 발생하지 않는 경우에만 간선을 추가합니다.
  4. 모든 정점이 연결될 때까지 반복합니다.

• 시간 복잡도: O(Elog⁡E)O(E \log E)O(ElogE), EEE는 간선의 개수.
• 자료구조: Union-Find(Disjoint Set)을 사용해 사이클 여부를 확인.

2. 프림 알고리즘 (Prim’s Algorithm)

출처:위키피디아

• 방법:
  1. 임의의 시작 정점에서 출발합니다.
  2. 현재 트리에 연결된 간선 중 최소 가중치의 간선을 선택합니다.
  3. 선택한 간선의 반대편 정점을 트리에 추가합니다.
  4. 모든 정점이 트리에 포함될 때까지 반복합니다.
• 시간 복잡도: O(Elog⁡V)O(E \log V)O(ElogV), VVV는 정점의 개수.
• 자료구조: 우선순위 큐를 사용해 효율적으로 최소 가중치 간선을 선택.