[Algorithm/Greedy] 최소 신장 트리(Minimum Spanning Tree, MST) 문제 (크루스칼)

최소 신장 트리 문제란?

• 정의

"정점(vertex)의 집합 V와 가중치를 갖는 에지(edge)의 집합 E로 구성된 그래프 G = (V, E)가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오"

• 신장 트리 :  주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리
  • 정점의 수가 n 개이면 신장 트리의 간선 수는 n-1 개
• 최소 신장 트리(MST): 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분(간선)들의 가중치 합이 최소인 트리
• ex) 상수도관 네트워크, 도로 네트워크 설계

Example)

지도상에 여덟 개의 마을이 있고, 모든 마을이 서로 연결될 수 있도록 도로를 설계한다고 해보자.

 

• 연결된 도로는 사이클을 구성하면 안 된다.
• 연결된 도로의 전체 길이는 최소가 되어야 한다.
• 모든 도로는 양방향으로 상호 이동할 수 있다고 가정한다

이 문제를 표현하기 위해서는 그래프 자료구조를 사용하는 것이 좋다.

 

최소 신장 트리 T를 구하는 알고리즘(크루스칼 최소 신장 트리 알고리즘)

1. 그래프 G의 모든 에지를 최소 힙 H에 추가한다.
2. H로부터 에지 e를 하나 꺼낸다. 당연히 e는 모든 에지중에서 가장 가중치가 작은 에지이다.
3. e의 양 끝 정점이 이미 T에 있는 경우, e로 인해 T에서 사이클이 발생할 수 있으므로 이런 경우에는 e를 버리고 2단계로 이동한다.
4. 최소 신장 트리 T에 e를 추가하고 2단계로 이동한다.

• 2단계부터 4단계까지를 반복하면서 가장 작은 가중치의 에지를 찾고, 이 에지에 의해 사이클이 발생하지 않으면 해당 에지와 양 끝 정점을 최종 솔루션에 추가한다.
• 이렇게 선택된 에지와 정점은 최소 신장 트리를 구성한다.
• 매 반복 마다 최소 에지 가중치를 선택하기 때문에 그리디 방식이라고 한다.
• 이 알고리즘을 크루스칼 최소 신장 트리 알고리즘이라고 부른다.

슈도 코드

KruskalMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m
출력: 최소 신장 트리 T
1. 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자.
2. 𝑇 = ∅ // 트리 T를 초기화시킨다.
3. while ( T의 선분 수 < n-1 ) {
4. 	L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다.
5. 	if (선분 e가 T에 추가되어 사이클을 만들지 않으면) // feasibility check
6. 		e를 T에 추가시킨다.
7. 	else // e가 T에 추가되어 사이클이 만들어지는 경우
8. 		e를 버린다.
	}
9. return 트리 T // T는 최소 신장 트리이다.

 

최소 신장 트리 알고리즘은 그리디 알고리즘 요건을 만족할까?

• 최적 부분 구조
  • 증명하기 위해 귀류법을 사용해보자.
  • MST 문제가 최적 부분 구조 속성을 가지지 않는다고 가정해보자.
    • 즉, MST가 더 작은 MST 신장 트리의 집합으로 구성되지 않는다고 가정하는 것이다.

1. 그래프 G의 정점으로 구성된 최소 신장트리 T가 있다고 가정한다. T에서 에지 e를 하나 선택하여 제거한다. e를 제거하면 T가 더 작은 트리인 T1과 T2로 나눠진다
2. MST 문제가 최적 부분 구조 속성을 갖지 않는다고 가정했으므로 T1보다 더 작은 가중치를 갖는 신장트리 T1'이 존재해야 한다. 이 신장 트리 T1'과 T2를 에지 e로 연결한 새로운 신장 트리를 T'이라고 해보자
3. T'의 전체 가중치가 T의 전체 가중치보다 작기 때문에 처음에 T가 최소 신장 트리라고 가정했던 가설이 틀리게 된다. 따라서 MST 문제는 최적 부분 구조 속성을 만족해야 한다

• 그리디 선택
  • MST 문제가 그리디 선택 속성을 갖는다면 정점 v와 연결된 에지 중에서 최소 가중치 에지는 반드시 최소 신장 트리 T에 속해야 한다.
  • 귀류법을 이용해보자

1. 정점 v에 연결되어 있는 에지 중에서 최소 가중치를 갖는 에지를 (u, v)라고 가정한다
2. (u, v)가 T에 속하지 않는다면 T는 v와 연결되어 있는 다른 에지를 포함해야 한다. 이 에지를 (x, v)라고 가정한다. (u, v)가 최소 가중치 에지이기 때문에, (x, v)의 가중치는 (u, v) 가중치보다 커야 한다
3. T에서 (x, v)를 제거하고 (u, v)를 추가할 경우, 전체 가중치가 더 작은 트리를 얻을 수 있다. 이는 T가 최소 신장 트리라는 가정에 위배된다. 그러므로 MST 문제는 그리디 선택 속성을 만족해야 한다.

 

사이클을 판단하는 방법

그래프 에지 정보를 저장할 자료 구조가 필요하고, 새로운 에지를 추가할 때 사이클이 발생하는지를 판단하는 기능이 필요하다.

• 디스조인트-셋 자료구조(분리 집합)를 사용하면 해결할 수 있다.

분리 집합 자료구조에 대한 내용은 [자료구조]에 따로 정리해 두긴 했지만, 복습차원에서 다시 살펴보자

• 디스조인트-셋(분리 집합) 또는 유니온 파인드(Union-Find) 자료구조는 트리 형태의 원소로 구성된 포레스트이다.
• 각각의 원소는 숫자 ID에 표현되며, 랭크와 부모에 대한 포인터를 가진다.
• 디스조인트-셋 자료 구조가 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성되며, 각 원소는 하나의 트리를 나타낸다
• 디스조인트-셋 연산
  • make-set(x) : x를 ID로 갖는 원소를 디스조인트-셋 자료구조에 추가한다. 추가한 원소의 랭크는 0이고, 원소의 부모 포인터는 자기 자신을 가리키도록 설정한다
  • find(x) : 원소 x에서 시작해서 부모 포인터를 따라 반복적으로 이동하여 트리의 루트를 반환한다. (루트의 부모는 루트 자신이다)
  • union(x, y) : 두 개의 원소 x와 y에 대해 union() 연산을 수행하면 먼저 x와 y의 루트를 찾는다.
    • 두 루트가 같다면 x와 y가 같은 트리에 속해 있음을 의미한다 --> 아무런 작업도 하지 않는다
    • 두 개의 루트가 다르다면 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정한다

 

이제, 디스조인트-셋 자료구조를 사용하여 크루스칼 MST를 구현하는 방법을 살펴보자

• 그래프의 정점 개수가 N이라면, 먼저 N개의 원소를 갖는 디스조인트-셋 자료 구조를 초기화한다.
  • 크루스칼 알고리즘 2, 3단계에선 최소 힙을 이용하여 가장 가중치가 작은 에지를 선택하고, 사이클 발생 여부를 검사한다
  • 이 때, 사이클 발생 여부를 검사하기 위해 디스조인트-셋의 union(x, y) 연산을 활용하자
    • x, y의 부모가 같다면, 사이클을 형성할 수 있다. 따라서 union(x, y)에서 x, y의 루트가 같으면 아무 작업 없이 그대로 종료하고, MST에 추가하지 않는다
    • union(x, y) 연산을 수행하여 실제로 두 트리가 병합하면 해당 에지를 MST에 추가한다

 

 

크루스칼 MST 알고리즘 구현(C++)

disjoint-set 클래스 정의

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

using namespace std;

class SimpleDisjointSet
{
private:
	struct Node
	{
		unsigned id;
		unsigned rank;
		unsigned parent;

		Node(unsigned _id) : id(_id), rank(0), parent(_id) {}

		bool operator!= (const Node& n) const
		{
			return this->id != n.id;
		}
	};

	// 디스조인트-셋 포레스트
	vector<Node> nodes; 

public:
	SimpleDisjointSet(unsigned N)
	{
		nodes.reserve(N);
	}

	void make_set(const unsigned& x)
	{
		nodes.emplace_back(x);
	}

	unsigned find(unsigned x)
	{
		auto node_it = find_if(nodes.begin(), nodes.end(),
			[x](auto n) { return n.id == x; });
		unsigned node_id = (*node_it).id;

		while (node_id != nodes[node_id].parent)
		{
			node_id = nodes[node_id].parent;
		}

		return node_id;
	}

	void union_sets(unsigned x, unsigned y)
	{
		auto root_x = find(x);
		auto root_y = find(y);

		// 만약 X와 Y가 같은 트리에 있다면 그대로 종료
		if (root_x == root_y)
			return;

		// 작은 랭크의 트리를 큰 랭크의 트리 쪽으로 병합
		if (nodes[root_x].rank > nodes[root_y].rank)
			swap(root_x, root_y);

		nodes[root_x].parent = nodes[root_y].parent;
		nodes[root_y].rank++;
	}
};

 

 

그래프 자료 구조를 표현을 위해 에지 리스트 방식을 사용한다.

 

Edge 구조체

template <typename T>
struct Edge
{
	unsigned src;
	unsigned dst;
	T weight;

	// Edge 객체 비교는 가중치를 이용
	inline bool operator< (const Edge<T>& e) const
	{
		return this->weight < e.weight;
	}

	inline bool operator> (const Edge<T>& e) const
	{
		return this->weight > e.weight;
	}
};

 

 

Graph 클래스 정의

template <typename T>
class Graph
{
public:
	// N개의 정점으로 구성된 그래프
	Graph(unsigned N) : V(N) {}

	// 그래프의 정점 개수 반환
	auto vertices() const { return V; }

	// 전체 에지 리스트 반환
	auto& edges() const { return edge_list; }

	// 정점 v에서 나가는 모든 에지를 반환
	auto edges(unsigned v) const
	{
		vector<Edge<T>> edges_from_v;
		for (auto& e : edge_list)
		{
			if (e.src == v)
				edges_from_v.emplace_back(e);
		}

		return edges_from_v;
	}

	void add_edge(Edge<T>&& e)
	{
		// 에지 양 끝 정점 ID가 유효한지 검사
		if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
			edge_list.emplace_back(e);
		else
			cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
	}

	// 표준 출력 스트림 지원
	template <typename U>
	friend ostream& operator<< (ostream& os, const Graph<U>& G);

private:
	unsigned V;		// 정점 개수
	vector<Edge<T>> edge_list;
};

template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
	for (unsigned i = 1; i < G.vertices(); i++)
	{
		os << i << ":\t";

		auto edges = G.edges(i);
		for (auto& e : edges)
			os << "{" << e.dst << ": " << e.weight << "}, ";

		os << endl;
	}

	return os;
}

 

크루스칼 최소 신장 트리 알고리즘 구현

// 트리도 그래프로 표현할 수 있으므로 최소 신장 트리도 Graph 객체로 반환합니다.
// 다만 여기에는 사이클이 있으면 안됩니다.
template <typename T>
Graph<T> minimum_spanning_tree(const Graph<T>& G)
{
	// 에지 가중치를 이용한 최소 힙 구성
	priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> edge_min_heap;

	// 모든 에지를 최소 힙에 추가
	for (auto& e : G.edges())
		edge_min_heap.push(e);

	// 정점 개수에 해당하는 크기의 디스조인트-셋 자료 구조 생성 및 초기화
	auto N = G.vertices();
	SimpleDisjointSet dset(N);
	for (unsigned i = 0; i < N; i++)
		dset.make_set(i);

	// 디스조인트-셋 자료 구조를 이용하여 최소 신장 트리 구하기
	Graph<T> MST(N);
	while (!edge_min_heap.empty())
	{
		// 최소 힙에서 최소 가중치 에지를 추출
		auto e = edge_min_heap.top();
		edge_min_heap.pop();

		// 선택한 에지가 사이클을 생성하지 않으면 해당 에지를 MST에 추가
		if (dset.find(e.src) != dset.find(e.dst))
		{
			MST.add_edge(Edge <T>{e.src, e.dst, e.weight});
			dset.union_sets(e.src, e.dst);
		}
	}

	return MST;
}

 

테스트 코드

int main()
{
	using T = unsigned;

	// 그래프 객체 생성
	Graph<T> G(9);

	map<unsigned, vector<pair<unsigned, T>>> edge_map;
	edge_map[1] = {{2, 2}, {5, 3}};
	edge_map[2] = {{1, 2}, {5, 5}, {4, 1}};
	edge_map[3] = {{4, 2}, {7, 3}};
	edge_map[4] = {{2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5}};
	edge_map[5] = {{1, 3}, {2, 5}, {4, 2}, {8, 3}};
	edge_map[6] = {{4, 4}, {7, 4}, {8, 1}};
	edge_map[7] = {{3, 3}, {6, 4}};
	edge_map[8] = {{4, 5}, {5, 3}, {6, 1}};

	for (auto& i : edge_map)
		for (auto& j : i.second)
			G.add_edge(Edge<T>{ i.first, j.first, j.second });

	cout << "[입력 그래프]" << endl;
	cout << G << endl;

	Graph<T> MST = minimum_spanning_tree(G);
	cout << "[최소 신장 트리]" << endl;
	cout << MST;
}

 

시간 복잡도

• Disjoint-Set을 사용하지 않는 크루스칼 알고리즘의 시간 복잡도는 O(E log E)이다.
• 그러나 디스조인트-셋 자료 구조를 사용하면 O(Ea(V))로 줄어들며, a(v)는 아커만 함수의 역함수이다.
  • 아커한 함수의 역함수는 로그 함수보다 훨씬 느리게 증가한다.
  • 정점이 많은 그래프에서 큰 성능 차이가 발생할 수 있다.

이 외에도 최소 신장 트리를 찾는 프림 알고리즘이 존재하는데, 그래프 파트에서 다룰 예정이다

 

Ref) 코딩 테스트를 위한 자료 구조와 알고리즘 with C++