MST - 구현

Kruskal Algorithm

크루스칼 알고리즘을 구현한 이후 제대로 구현됐는지 확인하기가 어려워 백준 문제 중 하나를 푼다는 생각으로 구현했다.

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

class Edge implements Comparable<Edge> {
	// p1 - p2 사이 간선 길이가 len.
	// len 기준 오름차순 정렬해야 하므로 Comparable 인터페이스를 상속시킴
	int p1;
	int p2;
	int len;

	public Edge(int p1, int p2, int len){
		this.p1 = p1;
		this.p2 = p2;
		this.len = len;
	}

	@Override
	public int compareTo(Edge e){
		return this.len - e.len;
	}
}

class UnionFind{
	int[] parent;
	int[] rank;   // Union-by-Rank를 위한 배열
	int edgeNum;  
	int answerLen = 0; // Kruskal을 통해 만든 최소 간선 길이의 합

	public UnionFind(int len){
		parent = new int[len+1];
		rank = new int[len+1];

		for(int i =1;i<len+1;i++){
			parent[i] = i;
			rank[i] = 0;
		}
	}

	public int find(int x){
		if(parent[x]==x) return x;

		parent[x] = find(parent[x]);
		return parent[x];
	}

	public void union(int x, int y, int len){
		int pX = find(x);
		int pY = find(y);

		if(pX==pY) return;

		// 새로운 Edge가 ST에 추가되는 과정
		this.answerLen+=len;
		edgeNum++;
		if(rank[pX] > rank[pY]){
			parent[pY] = pX;
		}
		else{
			parent[pX] = pY;

			if(rank[pX]==rank[pY]){
				rank[pY]++;
			}
		}
	}
}

public class CodingApplication {

	public static void kruskal(List<Edge> list, int n){
		UnionFind unionFind = new UnionFind(n);

		for(Edge edge:list){
 			// UnionFind를 통해 만든 간선 개수가 N-1이라면 더 이상 Edge를 조회하지 않아도 됨
			if(unionFind.edgeNum==n-1) break;

			unionFind.union(edge.p1, edge.p2, edge.len);
		}
        
		System.out.println(unionFind.answerLen); // Kruskal을 통해 만든 최소 간선 길이
	}

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();

		List<Edge> list = new ArrayList<>();
		for(int i =0;i<m;i++) list.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));

		Collections.sort(list);

		kruskal(list, n);
	}

}

그렇다면 Kruskal에서 Union-Find 알고리즘을 사용하는 이유는 무엇일까?

이전에 설명했던 대로 Kruskal 알고리즘은 Greedy Algorithm을 사용하여 "사이클이 없는 최소 ST"를 만드는 과정이다.

 

여기서 중요한 것은 사이클이 없다는 것이다.

Union-Find 알고리즘을 사용할 경우 1개 Tree에 속해 있는 2개의 Node 사이 Edge가 선택되었을 경우 2개의 Node는 이미 같은 Set에 존재함으로 해당 Edge를 연결하지 않고 무시할 것이며 이를 통해 사이클이 만들어지지 않음을 보장받을 수 있다.

---

Prim's Algorithm

Prim 알고리즘은 위에서 말한 Kruskal 알고리즘과는 달리 "Node 선택 기반" 알고리즘이다.

즉, Edge보다는 현재 ST에 어떤 Node를 포함시킬지를 더 신경 쓰는 것이다. 

일단 바로 코드로 구현하도록 하겠다.

class Edge implements Comparable<Edge> {
	// Prim Algorithm은 Edge의 양 끝 점을 1개 Class에 담을 필요가 없음
	// 정점 기반 선택이므로 A라는 정점을 선택했을 때 A와 어떤 점이 연결되어 있는지가 중요함
	int point;
	int len;

	public Edge(int point, int len){
		this.point = point;
		this.len = len;
	}

	@Override
	public int compareTo(Edge e){
		return this.len - e.len;
	}
}

public class CodingApplication {

	public static void prim(int start, int n, List<Edge>[] edges){

		boolean[] visit = new boolean[n+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.add(new Edge(start, 0));

		int total = 0;
		int visitNum = 0;
		while(!pq.isEmpty()){
			Edge edge = pq.poll();

			int point = edge.point;
 			// 방문 Node가 N개라면 Tree가 완성된 것이므로 더 이상 볼 필요 없음
			if(visitNum==n) break;
            
			// 이미 방문한 Point로 현재 ST에 포함되어 있으므로 무시함
			if(visit[point]) continue;

			visit[point] = true;
			total += edge.len;
			visitNum++;

			// 추가한 Node인 point와 연결된 모든 Edge를 PriorityQueue에 추가
			for(Edge e:edges[point]){
				if(!visit[e.point]) pq.add(e);
			}
		}
		System.out.println(total);
	}

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();

		// lists[A] : A Node와 연결된 정점들
		List<Edge>[] lists = new ArrayList[n+1];
		for(int i =1;i<n+1;i++) lists[i] = new ArrayList<>();
        
		for(int i =0;i<m;i++){
			int p1 = sc.nextInt();
			int p2 = sc.nextInt();
			int len = sc.nextInt();

			lists[p1].add(new Edge(p2, len));
			lists[p2].add(new Edge(p1, len));
		}

		prim(1, n, lists);
	}

}

Kruskal 알고리즘과 Prim 알고리즘의 가장 큰 차이라면 아마 PriorityQueue 사용 여부일 것이다.

 

Kruskal 알고리즘은 "Edge 선택 기반" 알고리즘이기 때문에 모든 Edge에 대하여 1번만 정렬을 수행하면 추가 정렬을 수행할 필요가 없다.

 

하지만 Prim's Algorithm은 "정점 선택 기반" 알고리즘이다.

따라서 정점을 ST에 추가했다면 추가한 정점과 연결되어 있는 모든 Edge 또한 새로 추가되어 비교 대상이 되어야 하는 것이다.

즉, 계속해서 Sorting 작업이 이뤄져 최솟값을 뽑는 작업을 수행해야 하므로 간선의 가중치가 작을수록 우선순위가 높도록 만든 우선순위 큐를 사용하는 것이다.

---

시간 복잡도

Prim's Algorithm과 Kruskal Algorithm은 MST를 구하는 알고리즘이긴 하지만 정점 기반인지 Edge 기반인지 차이가 존재하기 때문에 시간 복잡도가 다르며 상황에 따라 적절하게 사용해야 한다.

 

결론부터 말하자면 Kruskal Algorithm의 시간 복잡도는 O(ElogE), Prim Algorithm의 시간 복잡도는 O(ElogV)이다.

(E : Edge 개수, V : 정점 개수)

 

Kruskal Algorithm을 먼저 보자면 Union-Find 알고리즘은 시간 복잡도가 상수이기 때문에 사실상 무시된다.

따라서 가중치 기준 정렬하는데 필요한 시간 복잡도에 의존하게 되는데 일반적인 경우 정렬 알고리즘은 O(Nlog(N))의 시간 복잡도를 가지며 "간선 기준 정렬"임을 고려하면 O(Elog(E))임을 알 수 있다.

 

Prim's Algorithm은 모든 Node에 대해 탐색을 진행하므로 O(V)의 시간 복잡도를 가지며 모든 노드마다 최소 간선을 찾아야 하므로 O(logV)의 시간 복잡도를 가진다.

또한 추가한 Node와 연결된 Edge들을 PriorityQueue에 넣을 때 필요한 시간은 O(logV)이며 노드의 인접 간선을 찾는 시간은 O(2E) = O(E)가 된다.

즉, O(VlogV + ElogV)이며 일반적으로 E는 V보다 크므로 O(ElogV)로 간주한다.

 

이 둘을 비교했을 때 Edge가 매우 클 경우 Prim Algorithm이, V가 매우 클 경우 Kruskal Alogrithm이 좋다고 말할 수 있다.