Today I Learned

오늘은 그리디 알고리즘 문제를 풀다가 본 최소신장트리의 개념에 대해 정리해보고자 한다.

참고 사이트 : gmlwjd9405

Spanning Tree

신장트리, 그래프의 모든 정점을 포함하는 트리로 최소 연결 부분 그래프.

• 최소 연결 : 간선의 수가 가장 적다.

• N개의 정점을 가질 때 정점이 모두 연결되는 최소 간선 수는 N-1로 무조건 트리 형태가 되는데 이 트리를 신장트리라 한다.

• 하나의 그래프에는 많은 신장트리가 존재한다.

• 모든 정점이 연결되어있어야 하지만 Cycle(원형으로 계속 순회)이 되면 안된다.

MST(Minimum Spanning Tree)

최소신장트리, Spanning Tree 중에서 사용된 간선의 가중치의 합이 가장 적은 트리

• 네트워크에 있는 모든 정점을 가장 적은 수의 간선과 비용(가중치)로 연결하는 것

• 조건 :
  Cycle이 되면 안된다.
  n-1개의 간선만 사용해 모든 N개의 정점을 연결해야한다.
  간선의 가중치의 합이 최소여야한다.

MST 구현 방법

Kruskal Algorithm

간선을 기준으로 MST를 형성하는 알고리즘

이미지 출처 : gmlwjd9405

• 가중치가 적은 간선부터 선택해나가는 방식

• Greedy방식을 사용해 순간순간의 최적 해를 선택해나가는 방식이다. Kruskal 알고리즘은 이런 Greedy방식을 사용해도 전체의 최적해가 된다는 것이 이미 증명되어 있다.

• 그래프의 간선을 오름차순으로 정렬해 사이클을 형성하는 간선을 제외하고 가장 적은 가중치의 간선을 차례대로 선택해나간다.

• 이전 단계로 형성된 신장트리는 전혀 생각하지 않고 사이클 형성 여부만 본 채 최소비용의 간선을 선택해나가는 방법

• 사이클 생성 여부는 Union-Find 알고리즘을 통해 확인한다.(TIL #155에 정리 예정)

• 시간복잡도는 간선의 수를 E, 정점의 수를 V라 하면,
  먼저 간선을 오름차순으로 정렬할 때 효율적인 정렬 알고리즘을 사용하면 O(E log E).
  Union-Find 알고리즘에 O(E log V).
  따라서 최악의 경우 시간복잡도는 O(E log E) or O(E log V)이다.

Prim Algorithm

정점을 기준으로 MST를 형성하는 알고리즘

이미지 출처 : gmlwjd9405

• 시작정점에서 부터 신장 트리를 점점 확장해나가는 방식

• 정점 하나를 골라 가장 가중치가 적은 간선을 고르고 다음 정점으로 이동.

• 앞단계에서 형성된 MST집합을 가중치가 작은 간선을 성택해 정점을 연결해나가는 방식. 모든 정점을 방문하면 MST가 형성된다.

• 시간복잡도는 인접행렬과 선형검색을 사용하면 정점 수 V에 대해 O(V^2).
  하지만 최소 힙(우선순위 큐)를 사용하면 간선 수 E와 정점 수 V에 대해 O(E log V).

두 알고리즘의 선택 기준

• 일반적으로 간선의 수가 정점에 비해 적은 희소그래프의 경우 Kruskal이 더 유리하다.
  간선을 정렬하는 시간에 O(E log E)가 소모되기 때문에 간선이 적으면 더 빠르다.

• 반면 간선의 수가 정점의 수와 비슷한 밀집그래프의 경우 Prim이 더 유리하다.
  각 단계에서 최소 가중치의 간선을 선택하는 방식으로 동작하기 때문에 O(E log V)이고, 크루스칼은 정렬에 시간이 더 소모되기 때문이다.