[대학원-자료구조 6] MST : Kruskal's Alg., Prim's Alg.

 

 

본 게시물의 전문은 chatgpt 기반의(언어모델 : gpt 4o) 답변임을 알려드립니다.

---

1. Minimum Spanning Tree (MST)란?

• Spanning Tree (신장 트리):
  
  • 신장 트리란 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프를 뜻한다. 이 부분 그래프는 여러개가 존재할 수 있다. 
    • 주어진 그래프 G의 모든 정점을 포함하는 서브그래프입니다.
    • 이 서브그래프는 트리여야 하며, 즉 사이클이 없어야 합니다.
  • 예를 들어, 정점이 4개인 그래프의 모든 정점을 포함하면서 간선 수는 3개(=n-1)가 되어야 합니다.
• Minimum Spanning Tree (MST):
  
  • 최소 신장 트리 (MST, Minimum Spanning Tree) 란 가능한 여러 신장 트리 중에서 가중치의 합이 최소인 신장 트리를 의미합니다.
  • 즉, 여러 개의 부분 그래프 중 모든 정점이 최소 간선의 합으로 연결된 부분 그래프입니다.
  • 무향, 연결, 가중치가 있는 그래프에서 정의됩니다.
• MST의 특징:
  • 모든 정점을 포함합니다.
  • 사이클이 없습니다.
  • 최소 가중치를 가지는 트리입니다.

MST 예제

• 그래프에서 최소 신장 트리를 찾을 때, 각 간선에는 양수의 가중치가 부여됩니다.
• 예시로 두 가지 그래프가 주어졌습니다:
  • 첫 번째 MST: 가중치의 합이 3+4+1=8
  • 두 번째 MST: 가중치의 합이 4+4+1=9
• MST는 주어진 그래프에서 가중치의 합이 최소인 트리를 선택합니다.
• 이 예시에서는 가중치 합이 8인 첫 번째 트리가 최소 신장 트리(MST)가 됩니다.

2. Generic - MST 알고리즘 : Prim/Kruskal 알고리즘의 기본 틀

MST(Minimum Spanning Tree)를 찾는 일반화된 알고리즘(Generic-MST)의 구조를 설명하고 있습니다.

이 알고리즘은 Prim 또는 Kruskal 알고리즘과 같은 구체적인 MST 알고리즘의 기본 틀이 됩니다

 

 

동작 원리:

1. 초기화:
   • 시작할 때, 트리를 구성하는 간선의 집합 AAA는 공집합입니다.
2. 반복문:
   • A가 신장 트리(Spanning Tree)가 될 때까지 간선을 추가합니다.
   • 각 반복에서 "safe edge"를 선택합니다.
     • safe edge: 해당 간선을 추가해도 사이클이 발생하지 않고 최소 비용이 유지되는 간선.
3. 간선 추가:
   • 선택된 안전한 간선 (u,v)를 집합 A에 추가합니다.
4. 반복 종료:
   • 모든 정점을 포함하는 트리가 완성되면 A를 반환합니다.

"Safe Edge"의 의미:

• safe edge란:
  • 선택된 간선이 사이클을 만들지 않으며 트리의 최소 비용을 유지하는 간선입니다.
  • Prim과 Kruskal 알고리즘에서 각기 다른 방식으로 간선을 선택합니다.
  • Kruskal: 가중치가 가장 작은 간선부터 선택하며, Disjoint Set을 사용해 사이클 방지.
  • Prim: 이미 구성된 트리에서 가장 가까운 노드로 가는 최소 가중치 간선을 선택합니다.

3. MST-Kruskal, 

MST-Kruskal 알고리즘

 

• 초기화:
  • 간선 집합 A를 공집합으로 시작합니다.
• 모든 정점에 대해 make-set 수행:
  • 각 정점을 독립된 집합으로 초기화합니다. (Disjoint Set 사용)
• 간선 정렬:
  • 간선들을 가중치의 비오름차순(오름차순)으로 정렬합니다.
• 간선 선택:
  • 가중치가 작은 순서로 간선을 선택합니다.
  • 두 노드가 같은 집합에 속하지 않는 경우(즉, 사이클이 생기지 않을 경우) 그 간선을 A에 추가하고 union 연산으로 두 집합을 병합합니다.
• 종료:
  • 모든 정점이 연결되어 신장 트리가 형성되면, A를 반환합니다.

핵심 자료구조:

• Disjoint Set: 각 정점이 어느 연결 성분에 속하는지 추적하여 사이클을 방지합니다.
  
  

예제

 

 

 

• 이 예제에서는 Kruskal 알고리즘이 사이클을 방지하며 최소 가중치 간선을 선택하는 과정을 보여줍니다.
• 최종적으로 선택된 간선들이 모든 정점을 포함하며 최소 가중치를 가지는 신장 트리를 형성합니다.

 

 

4. MST-Prim 알고리즘

이 장표는 Prim 알고리즘을 사용해 최소 신장 트리 (MST)를 구하는 과정과 개념을 설명합니다.

이 알고리즘은 탐욕적 알고리즘(Greedy Algorithm)의 하나로, 매 단계에서 가장 적은 가중치의 간선을 선택하면서 점진적으로 신장 트리를 확장해 나갑니다.

 

 

• 입력
  • 무향, 연결, 가중치가 있는 그래프 G=(V,E)G = (V, E)G=(V,E).
  • 시작 정점 rrr을 선택해 트리를 시작합니다.
• 초기화:
  • 모든 정점의 key 값을 ∞로 설정하고, 시작 정점 r의 key 값을 0으로 만듭니다.
  • 모든 정점을 포함하는 우선순위 큐 Q를 준비합니다.
• 반복문:
  • 큐 Q에서 가장 작은 key 값을 가진 정점 u를 추출합니다 (EXTRACT-MIN).
  • 정점 u의 인접한 정점 v들에 대해:
    • v가 아직 큐에 있고, 간선 w(u,v)의 가중치가 v의 현재 key 값보다 작으면:
      • v의 key 값을 업데이트하고, u를 v의 부모로 설정합니다.
• 종료:
  • 큐가 비게 되면 최소 신장 트리가 완성됩니다.

 

예제

- 이 장표의 예제에서는 정점 b를 시작점으로 하여 Prim 알고리즘을 수행합니다. 각 단계에서 가장 작은 가중치의 간선을 선택하며, 트리를 확장해 나가는 과정을 보여줍니다.

Prim 알고리즘의 실행 과정 (시작 정점: b)

1. 초기화:
   • 시작 정점은 b.
   • 트리에 포함된 정점의 집합 A={b}
   • 모든 정점의 key 값을 초기화하고, 시작 정점 b의 key는 0으로 설정됩니다.
   • 사용된 자료구조: 우선순위 큐 (Priority Queue)로 최소 가중치의 간선을 빠르게 선택.

실행 과정 – 단계별 간선 선택

1. 첫 번째 간선 선택:
   • 트리 A={b}A = \{b\}A={b}.
   • 인접한 간선:
     • (a,b)=1(a, b) = 1(a,b)=1
     • (b,e)=2(b, e) = 2(b,e)=2
     • (b,d)=4(b, d) = 4(b,d)=4
   • 최소 가중치 간선: (a,b)=1(a, b) = 1(a,b)=1
     • 정점 aaa가 트리에 추가됩니다: A={a,b}A = \{a, b\}A={a,b}.
2. 두 번째 간선 선택:
   • 트리 A={a,b}A = \{a, b\}A={a,b}.
   • 인접한 간선:
     • (b,e)=2(b, e) = 2(b,e)=2
     • (b,d)=4(b, d) = 4(b,d)=4
   • 최소 가중치 간선: (b,e)=2(b, e) = 2(b,e)=2
     • 정점 eee가 추가됩니다: A={a,b,e}A = \{a, b, e\}A={a,b,e}.
3. 세 번째 간선 선택:
   • 트리 A={a,b,e}A = \{a, b, e\}A={a,b,e}.
   • 인접한 간선:
     • (e,f)=3(e, f) = 3(e,f)=3
     • (b,d)=4(b, d) = 4(b,d)=4
   • 최소 가중치 간선: (e,f)=3(e, f) = 3(e,f)=3
     • 정점 fff가 추가됩니다: A={a,b,e,f}A = \{a, b, e, f\}A={a,b,e,f}.
4. 네 번째 간선 선택:
   • 트리 A={a,b,e,f}A = \{a, b, e, f\}A={a,b,e,f}.
   • 인접한 간선:
     • (b,d)=4(b, d) = 4(b,d)=4
   • 최소 가중치 간선: (b,d)=4(b, d) = 4(b,d)=4
     • 정점 ddd가 추가됩니다: A={a,b,e,f,d}A = \{a, b, e, f, d\}A={a,b,e,f,d}.
5. 모든 정점 연결 완료:
   • 마지막으로 트리에 포함되지 않은 정점 모두 연결됩니다.

안전한 간선(Safe Edge)의 정의

• 매 단계에서 두 개의 집합을 연결하는 최소 가중치 간선을 선택합니다.
  • 하나의 집합은 현재까지의 트리에 포함된 노드들이고,
  • 다른 집합은 트리에 포함되지 않은 노드들입니다.
• 선택된 safe edge는:
  • 사이클을 만들지 않고,
  • 가장 작은 가중치를 가지는 간선이어야 합니다.

Prim 알고리즘의 일반적인 설명

본 절에서는 Prim 알고리즘에서 안전한 간선(Safe Edge)의 선택과 key 값 관리 방식을 좀 더 구체적으로 설명합니다. 이 알고리즘은 트리 외부에 있는 노드들과의 최소 가중치 간선을 선택하며, 단계적으로 트리를 확장해 나가는 과정을 시각적으로 보여주고 있습니다.

 

5. Prim 알고리즘의 핵심 개념

1. 트리 확장:
   • Prim 알고리즘은 점진적으로 트리를 확장합니다.
   • 초기 트리는 시작 정점만 포함하고, 이후에 안전한 간선을 선택해 트리에 포함되지 않은 정점을 추가합니다.
   • 결과적으로 모든 노드를 포함하는 신장 트리가 완성됩니다.

Prim 알고리즘에서 key 값의 역할

• key(u):
  • 노드 uuu에 대해, 트리 외부에 있는 노드와 연결된 가장 작은 가중치의 간선의 가중치를 의미합니다.
  • 이 값은 **우선순위 큐(Priority Queue)**에서 사용되며, 각 단계에서 최소 가중치 노드를 선택할 때 참고합니다.

key 값 업데이트 과정 :

1. 각 단계에서, 트리에 새로 포함된 노드와 인접한 노드들의 key 값을 갱신합니다.
2. key(u) 값이 감소하면, 새로운 최소 가중치 간선이 발견된 것이므로 우선순위 큐에서 이를 반영합니다.

예제

 

 

 

• 초기 상태:
  • 하나의 노드가 트리에 포함됩니다.
  • 이때 key 값은 인접한 간선 중 최소 가중치 간선의 값을 가집니다.
    예: key(u)=1key(u) = 1key(u)=1
• 두 집합 연결:
  • 두 개의 노드 집합이 최소 가중치 간선을 통해 연결됩니다.
  • 매번 트리 외부에 있는 노드들과 연결된 **최소 가중치 간선(safe edge)**를 선택합니다.
• 점진적 트리 확장:
  • 트리가 확장됨에 따라 key 값과 연결 상태가 갱신됩니다.
  • 최종적으로 모든 노드가 트리에 포함될 때까지 이 과정을 반복합니다.

 

Prim 알고리즘의 데이터 구조와 역할

1. 우선순위 큐 (Min Priority Queue):
   • 각 노드의 key 값을 관리합니다.
   • 최소 key 값을 가진 노드를 빠르게 추출하여 트리에 추가합니다.
2. key 값 관리:
   • 노드와 인접한 간선의 가중치가 기존 key 값보다 작으면 key 값을 갱신합니다.

p.22 ~ 23 Not Yet

6. Kruskal vs Prim

• 우선순위 큐(Priority Queue): Prim 알고리즘은 최소 가중치 정점을 빠르게 선택하기 위해 Min-Heap 또는 Priority Queue를 사용합니다.

 

 

(시험 출제 예정) Prim's Algorithm에서 데이터 구조 min PQ를 어떻게 쓰는가?

 

(시험 출제 예정) Prim's 알고리즘과 Kruskal 알고리즘 각각에 적합한 자료구조는?

 

---

Reference

- https://roytravel.tistory.com/348

- Korea University - CVO101