[그래프 #6] MST (Minimum Spanning Tree)를 활용한 문제 풀이 방법

MST (Minimum Spanning Tree)

그래프의 모든 정점을 포함하면서, 가장 적은 비용으로 모든 정점을 연결하는 트리

 

MST 응용 분야

1. 네트워크 설계(Network Design)
   • MST는 여러 대상들 간의 연결을 최소 비용으로 설계하기 위해 사용
   • 도시 간의 도로 연결이나, 컴퓨터 네트워크의 노드 연결 등에 사용됩니다.

 

1. 클러스터링(Clustering)
   • 그래프를 여러 개의 클러스터로 분할하고, 각 클러스터 간의 비용을 최소화하는 목적으로 사용

 

1. 전기 회로(Electrical Circuit)
   • 전기 회로에서 전선을 연결할 때, 최소한의 비용으로 전선을 연결하기 위해 사용

 

1. 이미지 분할(Image Segmentation)
   • 이미지 분할 알고리즘에서 인접한 픽셀을 연결하는 최소 비용 경로를 찾아서 이미지를 분할

 

1. 군집 분석(Cluster Analysis)
   • 데이터셋에서 각 데이터간의 거리를 계산하고, MST를 만들어 군집을 형성하는 데 사용

 

---

 

MST가 되기 위한 조건

1. 그래프 내의 모든 정점을 포함하는 트리여야 한다.
2. 간선의 가중치 합이 최소여야 한다.
3. 트리이므로 사이클이 없어야 한다.
4. 간선의 수는 (정점의 수 - 1)과 같아야 한다.
   • 모든 노드는 단 하나의 경로만 생성하기 때문
5. MST는 양방향 연결에서만 유효

 

---

 

최소 신장 트리를 만드는 방법

대표적으로 Kruskal 알고리즘과 Prim 알고리즘이 있음

 

 

Kruskal 알고리즘과 Prim 알고리즘의 차이

1. 구현 방식
   • Kruskal 알고리즘: 간선 중심의 알고리즘
     • 그래프의 간선들을 가중치 오름차순으로 정렬
     • 순서대로 최소 비용의 간선을 추가하는 방식
   • Prim 알고리즘: 노드 중심의 알고리즘
     • 임의의 시작 노드를 선택
     • 해당 노드와 연결된 간선 중 가장 작은 가중치를 가진 간선을 선택
     • 위 방식을 반복하며 최소 비용 신장 트리를 만드는 방식

 

1. 시간 복잡도
   • Kruskal 알고리즘: 시간 복잡도는 O(E log E)로, 간선의 수에 비례
   • Prim 알고리즘: 시간 복잡도는 O(E log V)로, 노드의 수에 비례

 

1. 구하는 해
   • Kruskal 알고리즘: 모든 노드를 연결하는 최소 비용 신장 트리를 구함
   • Prim 알고리즘: 임의의 시작 노드로부터 최소 신장 트리를 구함

 

1. 구현 방법
   • Kruskal 알고리즘: Union-Find 자료구조를 이용하여 구현
   • Prim 알고리즘: 우선순위 큐나 힙 자료구조를 이용하여 구현

 

---

 

1. Kruskal algorithm

 

방법

1. 그래프의 간선들을 가중치의 오름차순으로 정렬
2. Union-Find 자료구조를 초기화합니다. 모든 노드를 각자의 집합으로 만듦
3. 정렬된 간선 리스트를 순회하며 다음을 반복
   • 현재 간선을 이루는 두 노드의 집합을 찾음
   • 두 노드가 이미 같은 집합에 속해 있다면, 해당 간선은 사이클을 생성하므로 무시
   • 두 노드가 다른 집합에 속해 있다면, 두 집합을 합쳐주고, 해당 간선을 최소 비용 신장 트리에 추가
4. 최소 비용 신장 트리를 반환

---

구현

최소 신장 트리의 간선의 합 구하기

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Edge {
	int a, b, cost; // 노드의 정보, 간선의 가중치 정보
};

bool cmp(Edge left, Edge right) {
	if (left.cost < right.cost)
		return true;
	if (left.cost > right.cost)
		return false;
	return false;
}

int parent[1001]; // union-find를 이용하기 위한 parent 선언

vector<Edge>v; // 정렬된 간선 정보를 넣기 위한 벡터 선언

int N, M; // 노드의 개수, 간선의 개수

int Find(int now){
	if (now == parent[now]) return now;

	return parent[now] = Find(parent[now]);
}

void Union(int a, int b) {
	int root_A = Find(a);
	int root_B = Find(b);

	if (root_A != root_B) {
		parent[max(root_A, root_B)] = min(root_A, root_B);
	}	
}

int kruskal() {
	// 1
	sort(v.begin(), v.end(), cmp);
	
	// 2
	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}

	int size_ = v.size();

	int sum_cost = 0; // MST의 최종 비용

	for (int i = 0; i < size_; i++) {
		Edge now = v[i]; // 3-a
		
		// 연결했을 때, cycle이 발생하는 지 확인 -> Union-Find를 이용
		if (Find(now.a) == Find(now.b)) continue; // 3-b

		sum_cost += now.cost;  // 3-c

		// a 노드와 b 노드를 연결
		Union(now.a, now.b);
	}

	// 4 : 해당 코드에서는 MST의 가중치 합을 반환
	return sum_cost;
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++){
		int from, to, cost;
		cin >> from >> to >> cost;

		// 그래프 구성
		v.push_back({ from, to, cost });
	}

	cout << kruskal();

}

 

---

 

구현

간선 가중치의 최소를 제한하여 MST를 만들 수 있는 지 여부 판별

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Edge {
	int a, b, cost;
};

bool cmp(Edge left, Edge right) {
	if (left.cost < right.cost)
		return true;
	if (left.cost > right.cost)
		return false;
	return false;
}

int parent[1001];

vector<Edge>v;

int N, M;

int Find(int now){
	if (now == parent[now]) return now;

	return parent[now] = Find(parent[now]);
}

void Union(int a, int b) {
	int root_A = Find(a);
	int root_B = Find(b);

	if (root_A != root_B) {
		parent[max(root_A, root_B)] = min(root_A, root_B);
	}	
}

int kruskal() {
	sort(v.begin(), v.end(), cmp);

	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}

	int size_ = v.size();

	int sum_cost = 0;

	for (int i = 0; i < size_; i++) {
		Edge now = v[i];
		
		if (Find(now.a) == Find(now.b)) continue;

		sum_cost += now.cost;

		Union(now.a, now.b);
	}

	return sum_cost;
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++){
		int from, to, cost;
		cin >> from >> to >> cost;

		v.push_back({ from, to, cost });
	}

	cout << kruskal();
}

 

---

 

2. Prim algorithm

 

방법

1. 임의의 시작 노드를 선택
2. 선택한 노드와 연결된 간선들 중 가장 작은 가중치를 가진 간선을 선택
3. 선택된 간선의 반대쪽 노드를 현재 집합에 추가
4. 현재 집합에 속한 노드들과 그래프에 속한 다른 노드들을 연결하는 간선 중 가장 작은 가중치를 가진 간선을 선택
5. 선택된 간선의 반대쪽 노드가 현재 집합에 속하지 않는다면, 해당 노드와 선택된 간선을 현재 집합에 추가
6. 위의 과정을 모든 노드가 포함될 때까지 반복

 

---

구현

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
	int to, cost;

	bool operator < (Edge next) const {
		if (cost < next.cost)
			return false;
		if (cost > next.cost)
			return true;
		return false;
	}
};

int N, M;

vector<Edge>al[101]; // 인접 리스트 선언

int prim(int start) {

	// priority Queue 준비
	priority_queue<Edge>pq;
	pq.push({ start, 0 });

	// connected DAT 준비

	int connected[101] = { 0, };

	int sum_cost = 0;

	while (!pq.empty()) {
		// 간선 값이 가장 작은 것부터 빼옴
		Edge now = pq.top();
		pq.pop();

		// 이미 now가 MST의 일원이면, 연결할 필요 없음
		if (connected[now.to] == 1) continue;

		// MST의 일원으로 새로 확보가 되는 노드
		connected[now.to] = 1;
		
		// 지금 이 노드까지 오는 길 = MST의 일원
		// 이 길의 비용을 누적

		sum_cost += now.cost;

		// now에서 갈 수 있는 노드를 priority queue에 삽입
		for (int i = 0; i < al[now.to].size(); i++) {
			Edge next = al[now.to][i];

			// 만약 이미 가려고 하는 노드가 MST의 일원이면, pass
			if (connected[next.to] == 1) continue;

			pq.push(next);
		}
	}

	return sum_cost;
}

int main() {
	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;

		// 양방향 입력
		al[from].push_back({ to, cost });
		al[to].push_back({ from, cost });
	}

	cout << prim(1);
}