6. Graph (2)

Graph(이어서)

1.  Minimum Spanning Tree

: 가중치 그래프(Weighted Graph)에서 모든 정점을 포함하면서 사이클이 없고, 간선의 가중치 합이 최소인 트리를 말함.

연결성	모든 정점이 연결되어야 함
무사이클성	사이클이 없어야 함
최소 비용	전체 간선의 가중치 합이 최소

 

가중치 그래프의 예를 들

   (2)
A------B
|\     |
| \    |
(3)\   |(1)
|   \  |
|    \ |
C------D
   (4)

가능한 신장 트리는 여러 개지만,
MST는 (A-B)(B-D)(A-C)로 구성되며 총 비용 = 2 + 1 + 3 = 6.

---

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

• 간선을 중심 접근
• 가중치가 가장 작은 간선부터 하나씩 선택
• 단, 사이클이 생기지 않도록 주의
• Union-Find (Disjoint Set) 자료구조로 사이클 여부를 판별함
• 희소 그래프(Sparse Graph)에 유리

 

알고리즘 절차

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬
2. 가장 작은 간선부터 하나씩 선택
3. 사이클이 생기지 않으면 그 간선을 MST에 추가
4. MST에 (V - 1)개의 간선이 포함되면 종료

Kruskal(G):
  MST = ∅
  간선들을 가중치 기준으로 정렬
  for (u, v) in E:
    if Find(u) ≠ Find(v):     // 사이클 없음
      MST에 (u, v) 추가
      Union(u, v)             // 두 정점 연결
  return MST

 

 

시간 복잡도

간선 정렬	Union-Find 연산	전체
O(E log E)	거의 O(1) (경로 압축 사용 시)	O(E log E)

---

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

• 정점 중심 접근
• 하나의 정점에서 시작해, 이미 선택된 정점 집합에서 가장 작은 가중치 간선을 통해 새로운 정점을 연결함.
• 밀집 그래프(Dense Graph)에 유리
• 다익스트라 알고리즘과 구조가 유사함 (둘 다 “가장 가까운 정점” 선택)

 

알고리즘 절차

1. 임의의 정점 하나를 시작점으로 선택
2. 현재 트리에 연결된 간선 중 가장 작은 가중치의 간선 선택
3. 새로 연결된 정점을 트리에 추가
4. 모든 정점이 연결될 때까지 반복

Prim(G, start):
  visited[start] = true
  for i in range(V - 1):
    (u, v) = 최소 가중치 간선 (u는 방문됨, v는 방문 안 됨)
    MST에 (u, v) 추가
    visited[v] = true

 

시간 복잡도

구현방식	복잡도
인접 행렬	O(V²)
인접 리스트 + Min Heap	O(E log V)

 

예를 들면, 

시작: A
→ A-B(2)
→ B-D(1)
→ A-C(3)

총 비용 = 6 (Kruskal과 동일한 결과)

---

4.  Sollin’s Algorithm (Borůvka’s Algorithm)

• Kruskal과 Prim의 중간적인 성격
• 각 정점(혹은 각 연결 요소)이 가장 가까운(가중치 최소) 간선을 동시에 선택하는 방식.
• 선택된 간석으로 여러 개의 부분 트리가 한 번에 병합됨.
• 병렬 처리에 유리하고, MST의 초기 형태를 빠르게 형성함. 

 == 초기 단계에서 병렬 수행 가능, 큰 그래프의 MST를 빠르게 근사할 때 유용

 

알고리즘 절차

1. 각 정점을 개별 트리로 초기화
2. 각 트리가 가장 작은 간선을 선택
3. 선택된 간선으로 구성된 트리들을 병합 (Union)
4. 병합된 새로운 트리 집합에 대해 1~3를 반복
5. 트리가 하나로 합쳐질 때까지 수행

Boruvka(G):
  각 정점을 개별 트리로 초기화
  while (트리 개수 > 1):
    각 트리마다 최소 간선 선택
    선택된 간선들을 이용해 트리 병합
  return MST

 

시간 복잡도

각 단계에서 간선 검사	로그 단계 수(병합 횟수)	전체
O(E)	O(log V)	O(E log V)

 

---

정리!

• MST는 최소 비용으로 모든 정점을 연결하는 그래프의 뼈대

알고리즘	Kruskal	Prim	Sollin (Borůvka)
접근방식	간선 중심	정점 중심	병렬 간선 선택
알고리즘	간선 하나씩 추가하며 병합 (Union-Find)	정점 하나씩 확장 (Heap 사용)	모든 컴포넌트가 동시에 확장 (병렬형)
자료구조	Union-Find	Min Heap	Union-Find
시간 복잡도	O(E log E)	O(E log V)	O(E log V)
특징	희소 그래프에 유리	밀집 그래프에 유리	병렬 처리에 적합