[자료구조] MST

🎞️ Spanning Tree

Spanning Tree (신장 트리): 그래프 내의 모든 정점을 포함하는 트리

• 그래프의 최소 연결 부분 그래프
  • 최소 연결: 간선의 수가 최소
  • n개의 정점을 갖는 그래프의 최소 간선 수는 n-1
  • n-1개의 간선으로 연결하면 필연적으로 트리 형태가 됨
• 즉, 그래프에서 일부 간선을 선택해 만든 트리

특징

• DFS, BFS을 이용해 그래프에서 신장 트리를 찾을 수 있음
  • 탐색 중에 사용된 간선만 모으면 만들 수 있음
• 하나의 그래프에 다수의 신장 트리가 존재할 수 있음
• 사이클을 포함하면 안됨

사용 사례: 통신 네트워크 구축

🎞️ Minimum Spanning Tree

Minimum Spanning Tree: Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소 인트리

• 각 간선의 가중치가 동일하지 않을 때 단순히 가장 작은 잔선을 사용한다고 해서 최소 비용이 얻어지지는 않음
• MST는 간선에 가중치를 고려하여 최소 비용의 신장 트리 선택
• 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결해야 함

특징

• 간선의 가중치의 합이 최소
• n개의 정점을 갖는 그래프에 대해 반드시 n-1개의 간선 사용
• 사이클 포함하면 안됨

🎞️ MST 구현하기

Kruskal MST 알고리즘, Prim MST 알고리즘

🎞️ Kruskal MST 알고리즘

Krusal MST: 그리디 메서드를 이용해 네트워크(간선에 가중치를 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답 구하기

• 간선 선택 기반
• 이전 단계에서 만들어진 신장 트리와 상관없이 무조건 최소 간선만을 선택

과정
1. 그래프의 간선들은 가중치의 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택
- 가장 낮은 가중치 먼저 선택
- 사이클을 형성하는 간선은 제외
- 사이클: 새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결할 때 생성됨
- 추가할 간선의 양끝 정점이 같은 집합에 속해 있는 경우
- 사이클 생성 여부 확인은 union-find 알고리즘 이용
3. 해당 간선을 현재 MST의 집합에 추가

시간 복잡도

• union-find 알고리즘을 이용하면 시간복잡도는 간선들을 정렬하는 시간에 좌우됨
• 퀵 정렬 등을 사용하면 시간복잡도는 O(e*log e)

용도: 그래프 내 적은 숫자의 간선만을 가지는 희소 그래프(Sparse graph)에 적합

Union-Find 자료구조

Disjoint Set

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

• 공통 원소가 없는 부분 집합들로 나눠진 원소들의 자료구조
• Disjoint set: 서로소 집합 자료구조

Union-Find

Disjoint set을 표현하는 알고리즘

• 집합을 구현하는 여러 방법 중 트리 구조로 구현

연산
1. make-set(x) - 초기화: x를 유일한 원소로 갖는 새로운 집합 생성
2. union(x, y) - 합하기: x가 속한 집합과 y가 속한 집합을 합치는 연산
3. find(x) - 찾기: x가 속한 집합의 대표값(루트 노드값)을 반환

• 배열로 구현하면:
  • arr[i]: i번 원소가 속하는 집합의 번호 (루트 노드의 번호)
  • 시간복잡도:
    • union - O(N)
      • 배열의 모든 원소를 순회하면서 y의 집합 번호를 x의 집합 번호로 변경
    • find - O(1)
      • 배열의 인덱스로 x가 속한 집합 번호 찾기
• 트리로 구현하면:
  • 같은 집합 = 하나의 트리
  • 집합 번호 = 루트 노드
  • 시간복잡도:
    • union - O(N)보다 작음
      • x, y의 루트 노드를 찾고 다르면 y를 x의 자손으로 넣어 두 트리를 합침
      • 시간복잡도는 O(N)보다 작고, find 연산에 전체 수행시간 좌우됨
    • find - O(N-1)
      • 노드의 집합 번호 = 루트 노드
      • 루트 노드를 확인해 같은 집합인지 확인
      • 시간복잡도는 트리의 높이와 시간 복잡도가 동일

🎞️ Prim MST 알고리즘

Prim MST: 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

• 정점 선택 기반
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법

과정
1. 시작 단계에서는 시작 정점만이 MST 집합에 포함됨
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장
- 가장 낮은 가중치 먼저 선택
3. 위의 과정을 트리가 N-1개의 간선을 가질 때까지 반복

시간복잡도: O(n^2)

• 주 반복문이 정점의 수 n만큼 반복
• 내부 반복문이 n번 반복

용도: 그래프 내 적은 숫자의 간선만을 가지는 밀집 그래프(Dense graph)에 적합

---

참고

• [알고리즘] Kruskal 알고리즘 이란
• [알고리즘] Prim 알고리즘 이란
• [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란
• [알고리즘] Union-Find 알고리즘