[그래프] 최소 신장 트리 (minimum spanning tree)

이번에는 그래프의 최소 신장 트리(minimum spanning tree)를 알아보자.

 

최소 신장 트리가 무엇일까?

 

먼저 그래프는 익히 알고 있을 것이다.

 

그래프는 노드와 간선으로 구성된다.

 

지하철 노선도로 비유하자면 지하철 역이 노드이고

 

지하철 역과 역을 잇는 선이 간선이 될 것이다.

 

지하철 역처럼 노드는 무엇인가를 나타내기 위해 사용하고

 

간선은 노드와 노드의 관계를 나타낸다. (어느 역과 어느 역이 연결되어 있는지 등)

 

간선은 보통 비용을 포함하고 있다.

 

비용의 종류는 그래프의 용도에 따라 다양하게 결정된다.

 

거리가 될 수도 있고 금전적인 진짜 비용이 될 수도 있다.

 

여기서 노드들과 노드들을 제각기 잇는 간선이 있을 때

 

모든 노드들을 최소의 비용을 들여 연결한 그래프 모습을 최소 신장 트리라고 한다.

 

그렇다면 왜 트리라는 용어를 사용하는가?

 

최소 비용을 들여 모든 노드들을 연결하면 사이클(Cycle)을 형성하지 않고 트리 형태의 모습을 띄기 때문이다.

 

이제 우리가 알아볼 것은 노드와 간선의 집합이 주어졌을 때

 

최소 신장 트리를 구하는 알고리즘이다.

 

대표적으로 Kruskal과 Prim 알고리즘 두 가지가 있다.

 

알고리즘을 알아보기 전에 우선순위 큐(Priority queue)와 데이터 표현 방법에 대해 알아야 한다.

 

우선순위 큐는 말 그대로 데이터를 저장하는 큐이지만 데이터를 차례차례 꺼냈을 때

 

오름차순 또는 내림차순 순서로 정렬되도록 하는 큐이다.

 

(자세한 원리나 구현 방법은 검색하면 많이 나와 있다.)

 

두 알고리즘 모두 우선순위 큐를 사용한다.

 

그리고 우리는 최소 비용을 원하므로 오름차순의 우선순위 큐를 사용한다.

 

데이터 표현 방법은 그래프를 표현하는데 어떤 자료구조를 사용할 것인가이다.

 

그래프에서 노드와 간선을 표현하는 방법으로 2차원 배열이 가장 많이 사용된다.

 

연결 리스트(Linked list)도 표현이 가능하지만

 

메모리를 조금 더 차지하는 대신에 원하는 간선의 비용을 바로 찾을 수 있기 때문이다.

 

기본적으로 노드마다 인덱스가 주어져 있고

 

배열에서 사용되는 인덱스가 노드의 인덱스를 나타낸다.

 

그리고 배열 요소의 값은 노드와 노드를 연결하는 간선의 비용을 의미한다.

 

예를 들면 arr[1][2] = 10이라고 할 때

 

1번 노드에서 2번 노드로의 간선 비용이 10이라는 뜻이다.

 

(여기선 무방향성 그래프를 대상으로 한다.)

 

여기까지의 내용을 코드로 정리하면 다음과 같다.

 

struct Edge
{
	std::size_t from;
	std::size_t to;
	int value;
	Edge(std::size_t from, std::size_t to, int value)
		: from(from), to(to), value(value)
	{

	}
};

std::size_t _vertexCount;
std::size_t _edgeCount;
std::vector<std::vector<int>> _weights;

#define INFINITY_VALUE -1

 

Edge라는 구조체는 우선순위 큐에서 사용할 구조체이다.

 

Edge의 from은 노드를 잇는 간선의 첫 번째 노드이고 to는 두 번째 노드이다.

 

value는 간선의 비용이다.

 

vertexCount는 노드의 총개수를 의미한다.

 

edgeCount는 간선의 총개수를 의미한다.

 

weights는 위에서 예시로 표현한 arr과 같은 그래프를 나타낸다.

 

INFINITY_VALUE는 노드와 노드가 연결되지 않음(간선이 없음)을 나타내기 위해서 weights 요소의 값으로 사용된다.

 

기본적으로 weights 배열에 비용이 담겨 있는 상태에서 알고리즘을 구현하기로 한다.

 

Kruskal 알고리즘부터 알아보자.

 

• Kruskal 알고리즘

Kruskal 알고리즘은 처음에 모든 간선을 우선순위 큐에 넣고

 

하나씩 꺼내면서 사이클을 형성하지 않도록 노드들을 연결한다.

 

사이클을 형성하지 않게 하는 것이 매우 중요하다.

 

사이클 형성을 막기 위해 집합이라는 개념을 사용한다.

 

쉽게 말해 같은 집합에 속한(다른 경로를 통해 도달할 수 있는) 노드끼리 연결하면 사이클을 형성하므로

 

노드들이 속하는 집합을 만들고 이들을 구분하는 것이다.

 

집합을 표현하기 위한 자료구조는 아래와 같다.

 

struct SetTree
{
	SetTree* parent;
	int setNum;

	SetTree()
		: parent(nullptr), setNum(0)
	{

	}
};

 

멤버 변수인 setNum은 집합을 구분하기 위해 존재한다.

 

그리고 parent 변수가 있는데 이것은 해당 집합을 포함하고 있는 상위 집합을 나타내기 위해 사용한다.

 

즉 A와 B 집합이 있고 B가 A의 부분 집합이면 B의 parent는 A를 가리키게 된다.

 

parent가 널 포인터(null pointer)이면 해당 집합이 최상위 집합임을 의미한다.

 

여기서 질문!

 

왜 부분 집합 개념을 사용할까?

 

집합이 다르면 다른 거지 부분 집합까지 들먹이는 이유를 고민해보자.

 

답은 두 집합을 하나로 통일하기 위해 노드 하나하나마다 집합(setNum)을 바꿔주는 작업을 하지 않기 위함이다.

 

단순하게 한 집합을 대표하는 노드의 상위 집합(parent)을 합치는 또 다른 집합으로 지정하면 되기 때문이다.

 

어떤 노드의 최상위 집합을 찾으려면 parent를 계속 타고 올라가기만 하면 된다.

 

이제 알고리즘 초기에 하는 작업을 알아보자.

 

모든 간선 데이터를 우선순위 큐에 넣고 집합을 구성하는 것이다.

 

집합의 개수는 노드 개수가 될 것이다.

 

위의 두 가지 작업을 코드로 표현하면 다음과 같다.

 

SetTree* setTrees = new SetTree[_vertexCount];
for (std::size_t t = 0; t < _vertexCount; ++t)
{
	setTrees[t].parent = nullptr;
	setTrees[t].setNum = t;

	for (std::size_t u = t + 1; u < _vertexCount; ++u)
	{
		if (INFINITY_VALUE != _weights[t][u])
			queue.Push(new Edge(t, u, _weights[t][u]));
	}
}

 

코드를 보면 노드 개수만큼 집합을 만들고

 

노드 인덱스를 집합 구분을 위한 숫자로 사용한다.

 

그리고 안쪽 for문에서는 우선순위 큐에 간선 데이터를 삽입하는 모습이다.

 

INFINITY_VALUE가 아닌 유의미한 비용일 때만 넣는 것에 주의하자.

 

저렇게 모든 간선의 데이터를 우선순위 큐에 넣고 하나씩 추출하면

 

비용이 제일 적은 간선 데이터부터 추출되는 것이다.

 

본격적으로 우선순위 큐에서 간선을 하나씩 추출했을 때의 작업을 보자.

 

앞서 Edge라는 간선 데이터에는 두 개의 노드 인덱스가 있다.

 

각 노드의 최상위 집합을 알아낸 뒤

 

집합이 다르다면 두 집합을 합쳐주고 그 간선을 최소 신장 트리에 추가한다.

 

집합이 같다면 그 간선은 사용하지 않고 넘어간다.

 

그렇게 우선순위 큐에 데이터를 다 추출할 때까지

 

또는 최소 신장 트리의 간선 개수가 노드 개수보다 1개 작을 때까지 반복한다.

 

코드로 표현하면 다음과 같다.

 

std::size_t order = 0;
Edge* edge = nullptr;
_result.Reset();
while (nullptr != (edge = (Edge*)queue.Pop()) && order < _vertexCount)
{
	SetTree* from = &setTrees[edge->from];
	while (nullptr != from->parent)
		from = from->parent;
	SetTree* to = &setTrees[edge->to];
	while (nullptr != to->parent)
		to = to->parent;
	if (from->setNum != to->setNum)
	{
		_result[edge->from][edge->to] = ++order;
		to->parent = from;
	}
	delete edge;
}

while (nullptr != (edge = (Edge*)queue.Pop()))
	delete edge;

delete[] setTrees;

 

result 변수는 weights 변수와 동일한 타입이지만

 

최소 신장 트리에 추가되는 간선과 그 순서를 저장한다.

 

이제 Prim 알고리즘을 알아보자.

 

• Prim 알고리즘

Prim 알고리즘은 시작할 노드를 정하고

 

비용이 적은 간선과 연결된 노드들을 하나씩 집합에 추가하는 방법을 사용한다.

 

여기서도 마찬가지로 사이클을 형성하지 않는 것이 중요하다.

 

다행히도 Kruskal 알고리즘보다 덜 복잡하다.

 

단순하게 하나의 집합에 포함되는지 아닌지만 구분하면 되기 때문이다.

 

그래서 처음에 노드마다 집합에 추가되었는지 여부를 구분할 플레그 데이터를 초기화한다.

 

그리고 시작 노드와 연결된 간선들만 우선순위 큐에 추가한다.

 

코드로 표현하면 다음과 같다.

 

#define CHECKED 1
#define TO_BE_CHECKED 0
		
std::size_t* check = new std::size_t[_vertexCount];
memset(check, TO_BE_CHECKED, sizeof(std::size_t) * _vertexCount);
check[vertexNum] = CHECKED;

for (std::size_t t = 0; t < _vertexCount; ++t)
	if (t != vertexNum && INFINITY_VALUE != _weights[vertexNum][t])
		queue.Push(new Edge(vertexNum, t, _weights[vertexNum][t]));

 

vertexNum 변수는 시작할 노드 인덱스를 나타낸다.

 

CHECKED는 최소 신장 트리에 추가된 것을 의미하며

 

TO_BE_CHECKED는 그 반대를 의미한다.

 

시작 노드를 CHECKED로 세팅하고

 

시작 노드와 연결된 간선 데이터만 우선순위 큐에 넣는 것을 확인할 수 있다.

 

다음 작업은 우선순위 큐에서 간선 데이터를 하나씩 추출하는 작업을 한다.

 

Kruskal 알고리즘과 다르게 집합에 속한 노드들 중에서 가장 비용이 적은 간선의 데이터가 추출된다는 것이다.

 

주의할 점은 간선 데이터의 from이 집합에 이미 속한 노드이고 to가 새로 추가할 노드인 것이다.

 

to에 해당하는 노드가 집합에 추가되지 않았다면 그 노드를 집합에 추가하고

 

그 노드와 연결된 아직 집합에 추가되지 않은 노드와의 간선을 우선순위 큐에 추가한다.

 

코드로 표현하면 다음과 같다.

 

std::size_t order = 0;
Edge* edge = nullptr;
while (nullptr != (edge = (Edge*)queue.Pop()) && order < _vertexCount)
{
	if (TO_BE_CHECKED == check[edge->to])
	{
		check[edge->to] = CHECKED;
		_result[edge->from][edge->to] = ++order;
		for (std::size_t t = 0; t < _vertexCount; ++t)
			if (t != edge->to && INFINITY_VALUE != _weights[edge->to][t])
				if (TO_BE_CHECKED == check[t])
					queue.Push(new Edge(edge->to, t, _weights[edge->to][t]));
	}
	delete edge;
}

while (nullptr != (edge = (Edge*)queue.Pop()))
	delete edge;

delete[] check;

 

지금까지 최소 신장 트리를 구현하는 두 가지 알고리즘 Kruskal과 Prim 알고리즘에 대해 알아보았다.

 

알고리즘은 구현 방법만 아는 것과 직접 구현해 보는 것은 천지 차이이므로 꼭 구현해 보길 바란다.