[알고리즘] 최소 신장 트리(Minimum Spanning Tree / MST) 개요 및 개념

임의의 정점(Vertex or Node)에서 다른 정점으로 연결된 모든 간선(Edge)들이 가중치를 가졌을 때, 모든 정점을 연결한 가장 적은 가중치의 합을 가지는 트리(Tree)를 만들려면 어떻게 해야할까요?

트리(Tree)란 순환(Cycle)을 가지지 않는 연결 그래프이며 임의의 두 정점에 대해 경로는 반드시 1개만 존재합니다. 

최소 신장 트리(MST)란?

신장 트리(Spanning Tree)는 무향 연결 그래프 G가 있을때, G의 부분 그래프이며, G의 모든 정점을 포함하는 트리(Tree) 구조인 그래프라고 할 수 있습니다. 

신장 트리(Spanning Tree) 개념

위 그림과 같이 무향 그래프 G의 모든 정점을 포함하는 트리를 신장트리, Spanning Tree 라고 합니다. 그리고 만약 여기서 간선들이 가중치를 가졌다면 가중치의 합을 최소 비용으로 만든 신장 트리를 최소 신장 트리 또는 최소 비용 신장 트리라고 합니다. Minimum Spanning Tree (MST)

최소 신장 트리 특징

최소 신장 트리에는 다음과 같은 특징이 있습니다.

• 한 그래프에는 여러 가지 최소 신장 트리가 존재할 수 있습니다. 즉, 해결 답안이 여러개일 수 있습니다.
• N개의 정점을 가지는 그래프에 대해 (N-1)개의 간선을 가져야만 합니다.
• 최소 신장 트리를 구하는 대표적인 알고리즘으로 크루스칼 알고리즘(Kruskal's Algorighm)과 프림 알고리즘(Prim's Algorigthm) 등이 있습니다.

---

크루스칼 알고리즘(Kruskal's Algorithm)

크루스칼 알고리즘은 탐욕적인 방법(Greedy Method)으로 가중치가 적은 순서대로 간선을 선택해나가는 방식으로 MST를 만듭니다. 그리고 이렇게 탐욕적으로 간선을 선택하며 구축한 최소 신장 트리는 최적의 해답임이 증명되어 있습니다.

크루스칼 알고리즘 구현 과정

크루스칼 알고리즘의 구현 과정은 다음과 같습니다.

1. 그래프의 모든 간선을 가중치(또는 비용) 오름차순으로 정렬하거나 최소힙에 저장합니다.
2. 정렬된 리스트 또는 최소힙에서 순서대로 간선을 선택합니다.
   1. 이때, 사이클을 형성하지 않기 위해 두 정점이 이미 연결 되어있으면 선택하지 않습니다.
   2. 두 정점이 연결되어 있지 않다면 간선을 선택합니다.
   3. 선택한 간선의 개수가 (N-1)개가 되면 리스트 순회를 종료합니다.

이때, 두 정점이 이미 연결 되어있는지 확인(Find)하는 과정과 간선을 선택하고 연결(Union)하는 과정에서 유니온-파인드 자료구조가 사용되게 됩니다.

유니온-파인드에 대한 설명과 구현은 다음 링크에서 확인할 수 있습니다.
https://devluce.tistory.com/14

[알고리즘] 유니온-파인드(Union-Find) & 서로소 집합(Disjoint Set) 개요 및 개념

크루스칼 구현 (C++)

이제부터 크루스칼 알고리즘을 C++ 언어로 구현합니다. 유니온-파인드를 사용한 함수(서로소 초기화, Union, Find)는 생략하도록 하겠습니다. 만약 유니온-파인드 구현 코드를 확인하고 싶다면 위 링크 포스트에서 확인해주시기 바랍니다.

간선 정보 및 최소힙 구현을 위한 구조체 정의

저는 최소힙(우선순위큐)를 사용하여 최소 가중치 간선을 가져오기 위해 다음과 같이 구조체를 정의하였습니다. Edge는 간선 정보를 저장하는 구조체이고 operator 오버로딩을 통해 최소힙 구현을 위해 가중치 비교를 반환합니다.

struct Edge {
	int start, target, weight; // 시작점, 끝점, 가중치
	Edge(int s, int t, int w) : start(s), target(t), weight(w) {};

	bool operator<(const Edge &edge) const {
		return weight > edge.weight; // 최소힙 정렬을 위한 가중치 비교
	}
};

크루스칼 알고리즘

이제 크루스칼 알고리즘을 작성합니다. 최소힙 자료구조를 사용하였으므로 최소힙 정의 부분도 추가하였습니다. 그리고 최소힙을 탐색하며 Find를 통해 사이클이 아닌 간선들을 연결(Union) 짓습니다. 최종적으로 연결지은 간선이 (정점의 갯수-1)이면 종료합니다.

priority_queue<Edge> pq; // 간선 최소힙

int cnt = 0; // 간선 갯수 카운트
while(!pq.empty()){
	if(cnt == N-1) break; // N-1개를 찾으면 break
	Edge cur = pq.top();
	pq.pop();
	if(find(cur.start)!=find(cur.target)){ // 사이클 확인 (Find)
		cnt++;
		cunion(cur.start, cur.target); // 연결 (Union)
	}
}

크루스칼 시간복잡도

이제 크루스칼 알고리즘의 시간복잡도를 확인하겠습니다. 우선순위큐 삽입, 삭제 연산의 시간복잡도는 \( O(\textbf{log}N) \) 입니다. 따라서 while문이 최악의 경우 모든 간선을 탐색하며 삭제한다고 했을 때 \( O(N\textbf{log}N) \) 의 수행시간이 소요됩니다. 따라서 유니온-파인드의 시간복잡도는 거의 상수 시간으로 수렴하므로 크루스칼 알고리즘의 시간복잡도는 \( O(N\textbf{log}N) \) 이라 할 수 있겠습니다.

 

---

프림 알고리즘(Prim's Algorithm)

프림 알고리즘은 임의의 시작점에서 시작하여 이 정점과 연결된 간선들 중에 비용이 적은 간선을 단계적으로 업데이트하는 방식으로 MST를 만듭니다. 간선을 기준으로 탐색하는 크루스칼 알고리즘과 다르게 하나의 정점부터 업데이트를 진행하는 프림 알고리즘 또한 탐욕적인 방법(Greedy Method)라고 할 수 있습니다.

프림 알고리즘 구현 과정

1. 임의의 정점을 시작점으로 선택하고 최소 신장 트리 집합에 포함 시킵니다.
2. 최소 신장 트리 집합에 포함된 정점과 인접한 간선들의 비용 중 가장 적은 비용의 간선을 선택하고 연결된 정점을 집합에 포함 시킵니다. 만약 집합에 포함된 정점을 선택한다면 사이클이 발생합니다.
3. (정점의 갯수-1) 만큼 위 과정을 반복하며 정점 사용 여부를 업데이트 합니다.

프림 알고리즘 구현 (C++)

이제부터 프림 알고리즘을 C++ 언어로 구현합니다. 여기서 간선 구조체와 최소힙 구현을 위한 코드는 위 크루스칼 알고리즘 코드에 구현되어 있으니 생략하겠습니다.

자료구조 초기화

정점을 기준으로 탐색할 수 있도록 간선 리스트가 아닌 인접 리스트로 정점의 정보를 저장합니다. 또한 최소 신장 트리를 만들었는지 확인하기 위한 배열도 선언합니다. 그리고 임의의 정점(여기서는 1)을 선택하여 mst 배열에 사용 체크를 하고 최소 간선을 선택할 수 있도록 최소힙에 추가합니다.

vector<pair<int, int> > node[MAX]; // 인접 리스트 벡터
bool mst[MAX]; // 최소 신장 트리에 사용되었는지 체크하는 배열

priority_queue<Edge> pq; // 간선 최소힙

int V, E;
cin >> V >> E;
	
for (int i = 0; i < E; i++){ // 인접 리스트 초기화
	int s, e, w;
  cin >> s >> e >> w;
  node[s].push_back(make_pair(e, w));
  node[e].push_back(make_pair(s, w));
}
    
mst[1] = true; // 임의의 정점(1) 사용
for(int i=0; i<node[1].size(); i++){
	pq.push(Edge(1, node[1][i].first, node[1][i].second)); // 최소힙에 추가
}

프림 알고리즘

이제 프림 알고리즘을 작성합니다. (정점의 갯수-1) 만큼 반복하며 최소힙에서 꺼낸 간선이 사이클을 만족하지 않는다면 최소 신장 트리로 선택하는 과정입니다. 그리고 선택이 이뤄졌다면 다시 추가된 정점의 인접 간선들을 다시 최소힙에 삽입합니다. 

for(int i=0; i<V-1; i++){ // (정점의 갯수-1) 만큼 반복
	while(!pq.empty()){
		Edge cur = pq.top();
		pq.pop();
		if(!mst[cur.target]){ // 사이클 확인 (최소 신장 트리에 사용된 정점 여부)
			mst[cur.target] = true; // 최소 신장 트리 사용
			int tmp = cur.target;
			for(int j=0; j<node[tmp].size(); j++){ // 추가된 정점의 인접 정점 최소힙에 추가
				pq.push(Edge(tmp, node[tmp][j].first, node[tmp][j].second));
			}
			break; // 간선 연결 완료 후 break
		}
	}
}

프림 시간복잡도

이제 프림 알고리즘의 시간복잡도를 확인하겠습니다. 정점의 갯수가 N일 때, 우선 순위 큐에서 최소 비용을 갖는 정점을 찾는데 수행 시간은 최악의 경우  \( O(\textbf{log}N) \) 의 수행시간이 소요됩니다. 그리고 연결 그래프의 모든 간선의 갯수를 M이라 할 때, 최악의 경우 모든 간선을 탐색하게 되므로 총 시간복잡도는 \( O(M\textbf{log}N) \) 의 수행시간이 소요되겠습니다.

 

---

크루스칼 알고리즘과 프림 알고리즘 비교

크루스칼 알고리즘은 간선을 중심으로 탐색하여 최소 신장 트리를 만드는 알고리즘이고, 프림 알고리즘은 정점을 중심으로 탐색하여 최소 신장 트리를 순차적으로 만드는 알고리즘임을 알게 되었습니다. 따라서 주어진 무향 연결 그래프의 간선이 매우 많을 경우에는 프림 알고리즘이 효과적이고, 그게 아니라면 보통 크루스칼 알고리즘을 선택하여 활용하는 것이 적합하겠습니다.

희소 그래프(Sparse Graph)는 크루스칼 알고리즘(Kruskal's Algorithm)
밀집 그래프(Dense Graph)는 프림 알고리즘(Prim's Algorithm)

결론

도시를 연결하는 도로 길이의 최소화, 전화선의 길이를 최소화하여 통신망 구축, 라우팅 경로 최적화 등과 같은 문제를 해결할 때 최소 신장 트리 알고리즘을 이용하여 해결할 수 있음을 알게 되었습니다. 또한 크루스칼 알고리즘과 프림 알고리즘이 존재하여 상황에 맞게 적재적소에 활용할 수 있습니다.

단, 최단 경로 문제와 헷갈리거나 혼동할 수 있으니 주의가 필요할 것 같습니다. 최소 신장 트리는 모든 노드를 연결한 가장 적은 비용의 합을 구하는 알고리즘입니다.

다음 포스팅에서는 최소 신장 트리를 사용한 예제 문제들을 살펴보고 풀이하겠습니다.