최소 신장 트리

• Spanning Tree(신장 트리)란 Cycle이 없지만 모든 node들이 연결되어있는 그래프를 의미한다.
• Spanning Tree가 되기 위한 조건은 Tree가 그래프의 모든 node들을 포함하며 Tree의 속성인 Cycle이 없음을 만족해야한다.
• 아래의 사진은 Spanning Tree의 예시를 나타낸 사진이다.
  
• Minimun Spanning Tree(MST, 최소 신장 트리)는 Spanning Tree중에서 Edge(간선)의 가중치의 합이 최소인 Spanning Tree를 의미한다.
  • 대표적인 알고리즘으로는 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)이 있다.

Kruskal's algorithm

• Kruskal's algorithm은 대표적인 MST알고리즘으로 Edge를 가중치에 따라 정렬한 후 가중치가 낮은 Edge부터 cycle이 생기지 않는다면 연결하는 방법으로 진행된다.
• 전반적인 순서는 다음과 같다.
  1. 모든 Node를 독립적인 집합으로 만든다.
  2. 모든 Edge를 가중치 순으로 정렬후 가중치가 작은 Edge부터 연결된 node들을 비교한다.
  3. Edge에 연결된 두 Node의 Root node를 비교하고 Root node가 서로 다를 경우 두개의 Node를 연결한다. (Root Node가 같으면 cycle이 생긴다고 판단하고 패스)
• 크루스칼 알고리즘은 전반적으로 Greedy algorithm을 기반으로 현재 가장 작은 가중치를 가진 edge를 선책하여 최적의 솔루션을 찾으려고 한다.
• 구현을 하기 위해서는 Edge들의 집합을 합치는 Union알고리즘과 node의 root node를 찾아내는 Find알고리즘이 필요하다.
  
  

Union-Find Algorithm

• 구현을 하기 위해서는 Edge들의 집합을 합치는 Union알고리즘과 node의 root node를 찾아내는 Find알고리즘이 필요하다.
• 최악의 경우 링크드 리스트와 같은 형태가 되어 계산량이 O(N)이 될 수 있다. 이를 막기 위해 union-by-rank, path compression 기법을 사용한다.
  

union-by-rank

1. 두 Tree의 높이가 다를 경우 높이가 높은 Tree의 Root node에 낮은 Tree를 연결하여 하나의 Tree를 만든다.
   
2. 두 Tree의 높이가 같을 경우 한 쪽 Tree의 높이를 1 증가시켜준 후 다른 Tree를 붙여준다.
   

path compression

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법이다.
• Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있다
  

시간 복잡도

1. 크루스칼 알고리즘에서는 모든 Edge를 가중치를 기준으로 정렬하고 두 정점을 비교하게 되는데 이 경우 퀵소트를 사용한다면 시간복잡도는 $O(E logE)$가 된다.
2. 각각 Root node를 확인 후 다를 경우 두 node를 연결하는데 union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까워 $O(1)$이 된다.
3. 시간 복잡도는 가장 높은 수가 전체의 시간복잡도가 되어서 1,2중에서는 2번인 $O(E log E)$가 가장 커서 크루스컬 알고리즘의 시간 복잡도는 $O(E log E)$가 된다.

union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명되었음

• $O(M log^*{N})$
• $log^*{N}$ 은 다음 값을 가짐이 증명되었음
• N이 $2^{65536}$ 값을 가지더라도, $log^*{N}$ 의 값이 5의 값을 가지므로, 거의 $O(1)$, 즉 상수값에 가깝다고 볼 수 있다

👨🏻‍💻 Kruskal's algorithm 구현

package algorithm;
import java.util.*;


public class Kruskal {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char[] vertices = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		// 각각 node들의 parent node들을 저장
		HashMap<Character, Character> parent = new HashMap<>();
		// 각 node들의 rank를 저장
		HashMap<Character, Integer> rank = new HashMap<>();
		for (char c:vertices) {
			parent.put(c, c);
			rank.put(c, 0);
		}
		
		
		PriorityQueue<Edge> edges = new PriorityQueue<>();
		edges.add(new Edge(7, 'A', 'B'));
		edges.add(new Edge(5, 'A', 'D'));
		edges.add(new Edge(7, 'B', 'A'));
		edges.add(new Edge(8, 'B', 'C'));
		edges.add(new Edge(9, 'B', 'D'));
		edges.add(new Edge(7, 'B', 'E'));
		edges.add(new Edge(8, 'C', 'B'));
		edges.add(new Edge(5, 'C', 'E'));
		edges.add(new Edge(5, 'D', 'A'));
		edges.add(new Edge(9, 'D', 'B'));
		edges.add(new Edge(7, 'D', 'E'));
		edges.add(new Edge(6, 'D', 'F'));
		edges.add(new Edge(7, 'E', 'B'));
		edges.add(new Edge(5, 'E', 'C'));
		edges.add(new Edge(7, 'E', 'D'));
		edges.add(new Edge(8, 'E', 'F'));
		edges.add(new Edge(9, 'E', 'G'));
		edges.add(new Edge(6, 'F', 'D'));
		edges.add(new Edge(8, 'F', 'E'));
		edges.add(new Edge(11, 'F', 'G'));
		edges.add(new Edge(9, 'G', 'E'));
		edges.add(new Edge(11, 'G', 'F'));
		
		kruskal(edges, rank, parent);
	}
	
	// 2개의 node들의 집합을 합침
	public static void union(char node1, char node2, HashMap<Character, Integer> rank, HashMap<Character, Character> parent) {
		if (rank.get(node1) > rank.get(node2)) {
			parent.put(node2, node1);
		}
		else {
			parent.put(node1, node2);
			if (rank.get(node1) == rank.get(node2)) {
				rank.put(node2, rank.get(node2)+1);
			}
		}

	}
	
	// Root node를 탐색
	public static char find(HashMap<Character, Character> parent, char n) {
		if (parent.get(n) != n)
			parent.put(n, find(parent, parent.get(n)));
		return parent.get(n);
		
	}
	
	public static ArrayList<Edge> kruskal(PriorityQueue<Edge> edges, HashMap<Character, Integer> rank, HashMap<Character, Character> parent) {
		ArrayList<Edge> result = new ArrayList<>();
		Edge temp;
		int len = edges.size();
		for (int i=0; i<len; i++) {
			temp = edges.poll();
			if (find(parent, temp.node1) != find(parent, temp.node2)) {
				union(find(parent, temp.node1), find(parent, temp.node2), rank, parent);
				result.add(temp);
				System.out.println(temp.weight+", "+temp.node1+", "+ temp.node2);

			}
		}
		return result;
	}

}


class Edge implements Comparable<Edge> {
	int weight;
	char node1;
	char node2;
	
	public Edge(int weight, char node1, char node2) {
		this.weight = weight;
		this.node1 = node1;
		this.node2 = node2;
	}
	
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.weight < o.weight? -1:1;
	}
}

🔗 Reference

• Fast Campas - 한번에 끝내는 Java/Spring 웹 개발 마스터 초격차 패키지 Online.