[자료구조] 최소 신장 트리 (MST; Minimum Spanning Tree)

신장 트리 (Spanning Tree)

신장 트리는 그래프 내의 모든 정점을 포함하는 트리입니다. 다만 아래의 조건들을 만족해야 합니다.

• 모든 정점들이 연결되어 있어야 함
• 사이클을 포함하면 안 됨
• n개의 정점을 n-1개의 간선으로 연결해야 함

 

해당 조건만 만족하면 되므로 하나의 그래프에는 다양한 신장 트리가 존재할 수 있습니다.

한 그래프에서 나올 수 있는 신장 트리 중 일부

 

최소 신장 트리 (MST; Minimum Spanning Tree)

최소 신장 트리는 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결한 트리입니다. 최소 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 고안한 알고리즘이 대표적으로 사용되고 있습니다.

 

Union-Find

최소 신장 트리를 구하기 위해서 union-find라는 연산을 해야 합니다.

union-find 연산은 union 연산과 find 연산으로 나눌 수 있습니다.

• union(x, y): 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만듬.
• find(x): 원소 x가 속해있는 집합을 반환함.

찾으려는 다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지 안 하는지 체크해야 합니다.

간선이 서로 다른 집합에 속하는 정점을 연결하면 사이클이 형성되지 않습니다. 그래서 추가하려는 간선의 양끝 정점이 같은 집합에 속해있는지 검사해야 합니다.

int parent[MAX_VERTICES] // 부모 노드

void set_init(int n) {
	for (int i = 0; i < n; i++) {
		parent[i] = -1;
	}
}

// curr가 속한 집합 반환
int set_find(int curr) {
	if(parent[curr] == -1) {
		return curr;
	}
	while(parent[curr] != -1) curr = parent[curr];
	return curr;
}

// 두 개의 원소가 속한 집합을 합침
void set_union(int a, int b) {
	int root1 = set_find(a); // 노드 a의 루트를 찾는다.
	int root2 = set_find(b); // 노드 b의 루트를 찾는다.
	if(root1 != root2) { // 합한다.
		parent[root1] = root2;
	}
}

 

시간 복잡도 분석

Kruskal과 Prim 알고리즘의 시간 복잡도를 알아보겠습니다.

Kruskal은 연결되어 있는 간선들의 가중치를 오름차순으로 정렬해야 하므로 퀵 정렬의 소요 시간인 $e \times log_{2} e$ 만큼의 시간이 소요 됩니다. 따라서 $O(e log_{2} e)$의 시간 복잡도를 가집니다.

Prim은 위의 코드에서는 이중 반복문에 의해 $O(n^2)$의 시간 복잡도를 가집니다. 하지만 distance 배열을 우선순위 큐로 변경한다면 최소 힙을 구성하는 시간인 $O(E log V)$의 시간 복잡도를 가집니다.