📘[Tree] MST(최소신장트리)에 대해서…

MST(최소 신장 트리)에 대해서…

MST란 ‘최소신장트리’로, 가장 비용이 적은 경로로 이루어진 트리를 말한다.
MST를 알기 전에 Spanning Tree즉, 신장트리부터 먼저 알아야 한다.

---

1. Spanning Tree (신장트리)

Spanning Tree란 그래프 내의 모든 vertex를 포함하는 트리이다.

• Spanning Tree는 그래프의 ‘최소 연결 부분 그래프’이다. (즉, 그래프에서 일부 edge를 선택해서 만든 트리이다)
  • 최소 연결 = edge의 수가 가장 적음.
  • n개의 vertex를 갖는 그래프의 최소 edge의 수는 n-1개이다.
  • n-1개의 edge로 연결되어 있으면 반드시 트리형태가 되고, 이 것을 신장트리라고 한다.

1-1. Spanning Tree의 특징

• DFS(깊이우선탐색), BFS(너비우선탐색)을 이용하여 그래프에서 신장트리를 찾을 수 있다.
• 하나의 그래프에는 다양한 신장트리가 존재할 수 있고, 그 중 가장 적은 비용의 신장트리를 MST(최소신장트리)라고 한다.
• 신장트리는 특수한 형태의 트리이므로, 모든 vertex들이 connected되어 있어야 하며, cycle을 형성해서는 안된다.
• n개의 vertex를 정확히 n-1개의 간선으로 연결한다.

---

2. MST (최소신장트리)

Spanning Tree 중에서 사용된 edge의 weight(가중치)의 합이 가장 작은 트리이다.

• 그래프에 있는 모든 vertex들을 가장 적은 비용의 edge들로 연결함

[예시]

2-1. MST의 특징

• edge의 가중치의 합이 최소여야 한다.
• n개의 vertex를 가지는 그래프에 대해 반드시 n-1개의 간선만 사용한다.
• cycle이 있어선 안된다.
• 그래프 G의 MST T를 찾았다고 해서, 그 트리가 유일한 MST가 아닐 수 있다. 즉, 다른 MST T’이 존재할 수 있다.

2-2. MST의 확장

T : G의 MST, A는 T의 subtree라고 하자.  
A와 V-A를 연결하는 edge(u,v)를 `light edge`라고 했을 때, edge(u,v)는 MST-T에 종속된다.  

[과정]
edge(u,v)가 비용이 가장 적은 edge이면, V-A에서 노드(v)를 A로 가져온다. 이 과정을 반복하면 MST를 구할 수 있다.

safe edge란 “비용(cost)가 가장 저렴하면서 cycle을 형성하지 않는 edge”를 말한다.

• S : vertex 전체의 집합
• V : 전체 그래프 집합
• A : 전체 edge 집합
• Cut : 그래프를 Partition으로 나누는데 사용된다.
  • 예) S와 V-S의 파티션으로 분리
• Cross : edge(u,v)에서 u와 v는 각각 다른 파티션에 존재하고, 이를 연결하는 edge를 cross라고 한다.
• Respect : 어떤 edge-set에서 cut을 건너가지 않는 경우
• Light edge : cross-edge 중 가장 작은 edge이다.

2-3. MST 구현 알고리즘

2-3-1. Generic-MST 의사코드

2-3-2. Kruskal Algorithm (크루스칼 알고리즘)

Kruskal Algorithm이란 greedy algorithm(탐욕 알고리즘)을 이용하여 그래프의 모든 vertex를 최소 비용으로 연결하는 알고리즘이다.
즉, 비용이 가장 싼 edge를 선택해 트리를 만들어 나가는 알고리즘이다.

• greedy algorithm : 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 알고리즘 (자신의 선택이 최선의 선택이길 바라는 알고리즘)

[과정]

1. 그래프의 edge들을 weight의 오름차순으로 정렬한다.
2. 정렬된 edge리스트에서 순서대로 cycle을 형성하지 않는 edge를 선택한다.
   • 가장 낮은 가중치를 먼저 선택
   • cycle을 만드는 edge는 제외
3. 해당 edge를 현재의 MST의 집합에 추가한다.

[의사코드]

[예제코드] 코드는 다시 내가 짜볼겁니다..

• 파이썬(출처)

from collections import deque
 
 
def mst():
    def upward(buf, idx):
        parent = mst_nodes[idx]
        if parent < 0:
            return idx
        buf.append(idx)
        return upward(buf, parent)
 
    def find(idx):
        buf = []
        result = upward(buf, idx)
        for i in buf:
            mst_nodes[i] = result
        return result
 
    def union(x, y):
        x, y = find(x), find(y)
        if x == y:
            return False
        if mst_nodes[x] < mst_nodes[y]:
            mst_nodes[y] = x
        elif mst_nodes[x] > mst_nodes[y]:
            mst_nodes[x] = y
        else:
            mst_nodes[x] -= 1
            mst_nodes[y] = x
        return True
 
    V, E = 6, 9
    edges = [[1, 2, 6], [1, 3, 3], [2, 3, 2], [2, 4, 5],
             [3, 4, 3], [3, 5, 4], [4, 5, 2], [4, 6, 3], [5, 6, 5]]
    edges.sort(key=lambda x: x[2])
    mst_graph = [[0] * V for _ in range(V)]
    mst_nodes = [-1 for _ in range(V)]
    mst = []
    cost = 0
    q = deque(edges)
    while True:
        u, v, w = q.popleft()
        udx, vdx = u - 1, v - 1
        if union(udx, vdx) is False:
            continue
        mst.append((u, v))
        mst_graph[udx][vdx] = 1
        mst_graph[vdx][udx] = 1
        cost += w
        if len(mst) == V - 1:
            break
    print(f'mst cost is {cost}')
    print(mst)
    for row in mst_graph:
        print(*row)
 
 
mst()

• 자바(출처)

import java.util.Arrays;  
import java.util.Scanner;
/*
sample input(첫 줄의 첫 숫자는 정점의 개수, 두 번째 숫자는 간선의 개수).
6 9
1 6 5
2 4 6
1 2 7
3 5 15
5 6 9
3 4 10
1 3 11
2 3 3
4 5 7
 */
public class Kruskal {
	static int V, E;
	static int[][] graph;
	// 각 노드의 부모
	static int[] parent;
	// 최종적으로 연결된 최소 신장 트리 연결 비용.
	static int final_cost;

	public static void main(String[] args) {
		// 그래프의 연결상태(노드1, 노드2, 비용)를 초기화.
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();
		graph = new int[E][3];
		for (int i = 0; i < E; i++) {
			graph[i][0] = sc.nextInt();
			graph[i][1] = sc.nextInt();
			graph[i][2] = sc.nextInt();
		}
		parent = new int[V];
		final_cost = 0;

		// 간선 비용 순으로 오름차순 정렬
		Arrays.sort(graph, (o1, o2) -> Integer.compare(o1[2], o2[2]));

		// makeSet
		for (int i = 0; i < V; i++) {
			parent[i] = i;
		}
		// 낮은 비용부터 크루스칼 알고리즘 진행
		for (int i = 0; i < E; i++) {
			// 사이클이 존재하지 않는 경우에만 간선을 선택한다(여기서는 최종 비용만 고려하도록 하겠다).
			if (find(graph[i][0] - 1) != find(graph[i][1] - 1)) {
				System.out.println("<선택된 간선>");
				System.out.println(Arrays.toString(graph[i]));
				union(graph[i][0] - 1, graph[i][1] - 1);
				final_cost += graph[i][2];
				System.out.println("<각 노드가 가리키고 있는 부모>");
				System.out.println(Arrays.toString(parent) + "\n");
				continue;
			}
		}
		
		System.out.println("최종 비용 : " + final_cost);
		sc.close();
	}

	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a > b) {
			parent[a] = b;
		} else {
			parent[b] = a;
		}
	}

	private static int find(int x) {
		if (parent[x] == x)
			return x;
		else
			return find(parent[x]);
	}
}

2-3-3. Prim Algorithm (프림 알고리즘)

Prim Algorithm이란 시작 노드에서 노드를 추가해가며 단계적으로 트리를 확장해나가는 알고리즘이다.

[의사코드]

[예제코드]

from collections import defaultdict
import heapq
 
def mst():
    V, E = 6, 9
    edges = [[1, 2, 6], [1, 3, 3], [2, 3, 2], [2, 4, 5],
             [3, 4, 3], [3, 5, 4], [4, 5, 2], [4, 6, 3], [5, 6, 5]]
    graph = defaultdict(list)
    for srt, dst, weight in edges:
        graph[srt].append((dst, weight))
        graph[dst].append((srt, weight))
    mst_graph = [[0] * V for _ in range(V)]
    mst_nodes = [-1 for _ in range(V)]
    visited = [True for _ in range(V)]
    q = [(0, 1, 1)]
    while q:
        cost, node, prev = heapq.heappop(q)
        if visited[node - 1] is False:
            continue
        visited[node - 1] = False
        mst_graph[node - 1][prev - 1] = 1
        mst_graph[prev - 1][node - 1] = 1
        mst_nodes[node - 1] = cost
        for dst, weight in graph[node]:
            if visited[dst - 1] is True:
                heapq.heappush(q, (weight, dst, node))
    print(f'MST cost is {sum(mst_nodes)}')
    mst_graph[0][0] = 1
    for row in mst_graph:
        print(*row)
 
mst()

2-3-4. 두 알고리즘의 시간복잡도 비교

Kruskal Algorithm의 시간복잡도 : O(eloge)
Prim Algorithm의 시간복잡도 : O(n^2)

[비교] 그래프에 edge가 적은 그래프인 희소그래프(Sparse Graph)인 경우에는 Kruskal Aogorithm이 유리하다.
그래프에 edge가 많은 그래프인 밀집 그래프(Dense Graph)인 경우에는 Prim Algorithm이 유리하다.