[알고리즘] C++로 이해하는 MST

참고 : Introduction to Algorithm

참고 : https://www.geeksforgeeks.org/what-is-minimum-spanning-tree-mst/

---

☑️ C++로 이해하는 MST

전자 회로는 여러 전자 부품들로 구성되는데, 이 중에서 '핀'이란 이름의 금속 연결부가 있다. 핀들을 서로 연결하여 전기가 흐를 수 있는 경로를 만드는 것이 회로 설계의 기본인데, N개의 핀을 연결하기 위해서는 최소 N-1개의 전선을 사용한다.

 

전선 연결 문제를 해결하기 위해서 최소 신장 트리(Minimum Spanning Tree)를 사용할 수 있다. 핀은 그래프의 Node에 해당하고 전선은 그래프의 Edge에 해당하기 때문이다.

 

1️⃣ 신장 트리(Spanning Tree) ?

신장 트리는 순환이 존재하지 않는 부분 그래프를 의미한다. 아래와 같이 그래프가 존재한다면 여러 신장 트리가 존재한다.

 

 

☑️ MST란 무엇일까?

최소 신장 트리는 아래 예시처럼 그래프의 모든 정점을 연결하면서 순환을 만들지 않고 간선의 가중치 합이 최소가 되는 부분 그래프, 결론적으로는 신장 트리 중에서 최소 가중치를 가지고 있는 그래프를 의미한다. 최소 신장 트리를 찾는 대표적인 알고리즘은 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있다.

1️⃣ MST의 특징

• N개의 정점을 가진 그래프의 최소 신장 트리는 N-1개의 간선을 가진다.
• 모든 정점 간에 경로가 존재한다.
  • 간선이 없는 정점은 존재하지 않는다. (=고립된 정점이 없다.)
• 어떤 간선을 하나 추가하면 반드시 순환이 생겨난다.

 

2️⃣ 크루스칼 알고리즘 VS 프림 알고리즘

최소 신장 트리를 찾기 위해서 사용되는 대표적인 알고리즘은 크루스칼과 프림이다. 크루스칼 알고리즘은 간선 중심이며, 프림은 정점 중심이다. 

 

📌 크루스칼 알고리즘

• 간선 중심 접근 알고리즘
• 서로소 집합 구조(Union Find)가 필요하다.
• 간선이 상대적으로 적은 경우 적합하다.
• 간선 중심으로 데이터를 관리한다.

 

📌 프림 알고리즘

• 정점 중심 알고리즘
• 우선순위 큐 혹은 이진 힙이 필요하다.
• 간선이 많은 경우 적합하다.
• 정점 중심으로 데이터를 관리한다.

 

☑️ 크루스칼 알고리즘에 대해서 알아보자.

1. 그래프의 모든 간선을 가중치에 따라서 정렬한다.
2. 각 정점을 서로소 집합으로 초기화한다.
3. 정렬된 간선 목록에서 가중치가 작은 간선부터 검사한다.
4. 검사 중인 간선이 서로 다른 두 트리를 연결하는 경우 간선을 선택한다.
	4-1. 같은 트리에 속한 정점들을 연결하는 간선은 순환을 만들기 때문에 선택 X
5. 정점 수 - 1개의 간선이 선택되거나 모든 간선을 검사했다면 종료한다.

크루스칼 알고리즘은 간선 검사 시, 가중치가 낮은 간선부터 높은 간선으로 이어진다. 이 중에서 조건에 부합하지 않으면 선택하지 않으므로 탐욕적(Greedy)인 접근 방법을 사용한다.

 

📌 작동 방식은 아래 링크에서 일러스트레이션 확인

Kruskal’s Minimum Spanning Tree (MST) Algorithm - GeeksforGeeks

 

☑️ 프림 알고리즘에 대해서 알아보자.

1. 시작 정점을 선택하고 MST 집합에 추가한다.
2. 현재 MST 집합에 포함된 정점과 포함되지 않은 정점 중에서 가중치가 낮은 간선을 선택한다.
3. 간선이 연결하는 정점 중, MST 집합에 포함되지 않은 정점을 추가한다.
4. 정점 수 - 1개의 간선이 선택될 때 까지 반복한다.

프림 알고리즘은 항상 하나의 연결된 트리를 유지하면서 정점을 하나씩 추가해 나가는 특징이 있다. 가장 가중치가 낮은 간선을 선택하고 이미 MST에 포함된 정점 집합과 포함되지 않은 정점 집합 사이의 간선만 고려하는게 특징이다.

 

📌 작동 방식은 아래 링크에서 일러스트레이션 확인

Prim’s Algorithm for Minimum Spanning Tree (MST) - GeeksforGeeks