5. Kruskal Algorithm

목차

1. 개념
2. Spanning Tree
3. Sort by cost
4. Union-Find
5. Kruskal Algorithm 구현

1. 개념

• Krushkal Algorithm 그래프에서 MST(Minimum Spanning Tree)를 찾기 위한 Greedy 알고리즘

• 간선을 하나씩 추가하면서 MST(최소 신장 트리)를 만드는 방식

2. Spanning Tree

Tree 사이클이 없는 그래프
Spanning Tree 신장 트리, 모든 vertex를 포함 + 사이클이 없는 edge
MST 최소 신장 트리, Weight가 최소인 Spanning Tree

3. Sort by cost

• edge의 weight를 기준으로 정렬하기

• implements comparator의 int compare(Edge e, Edge f)를 사용하여 비교 기준 선언하기

• 빨리 추가=-1 / 늦게 추가=1

• weight가 클수록 늦게 추가

	static class Weight_Comparison implements Comparator<Edge> { // weight를 기준으로 우선순위 큐를 사용하기 위해
		public int compare(Edge e, Edge f) {
			if (e.weight > f.weight) return 1;
			else if (e.weight < f.weight) return -1;
			return 0;
		}
	}

4. Union-Find Algorithm

• Union-Find 사이클이 생기는지 확인하기 위한 자료구조

• Find vertex가 속한 set의 대표 node(=parent) 찾기

• Union 두 vertex가 속한 집합을 하나로 합치기

• 사이클 조건 두 vertex의 대표 node(=parent)가 동일 = 이미 같은 집합 = 사이클 발생

• 구현

  	- 부모가 동일한지 확인(종료조건)

  • 트리의 depth(=rank) 확인 -> 추가하기

public class UnionFind {
	protected int[] p; // 배열 크기는 정점의 수 N이고, p[i]는 i의 부모를 저장
	protected int[] rank; // level을 저장(depth)

	...
    
	//i가 속한 집합의 루트를 순환으로 찾고, 최종적으로 경로상의 각 원소의 부모를 루트로 경로 압축
	protected int find(int i) {
		/* 구현 */
		//초기조건
		if(p[i]==i) return i;
		
		//p[i]는 i의 대표 vertex를 저장하므로 p[i]가 i(본인)이 될 때까지 find 수행하기ㄴ
		p[i]=find(p[i]);
		return p[i];
	}

	//i와 j가 같은 트리에 있는지를 검사
	public boolean isConnected(int i, int j) {
		return find(i) == find(j);
	}

	public void union(int i, int j) { // Union 연산
		/* 구현 */
		// 부모가 동일한지 확인하기
		int parent_i = find(i);
		int parent_j = find(j);
		
		// 동일하면 return
		if(parent_i == parent_j) return;
		
		// 트리의 depth(=rank)를 비교 -> 업데이트(간선 하나씩 묶기)
		// 낮은 트리 -> 높은 트리 (트리의 전체 높이가 늘어나는 것을 방지)
		// 같으면 아무쪽에 붙이고 반대쪽에 rank++ 해주기
		if(rank[parent_i]<rank[parent_j]) p[parent_i] = parent_j;
		else if(rank[parent_i]>rank[parent_j]) p[parent_j] = parent_j;
		else {
			p[parent_i]=parent_j;
			rank[parent_j]++;
		}
	}
}

5. Kruskal Algorithm 구현

[구현]
1. weight를 기준으로 하는 priorityQueue를 생성
2. 중복되지 않도록 edge를 순회하여 priorityQueue에 추가
3. 현재 priorityQueue에서 weight 하나씩 선택하여 같은 tree에 있는지 검사
4. 다름 -> 기존 unionfind에 해당 edge 추가하고, MST에 추가
5. count가 vertex-1이 되면 과정을 종료한다.

package Kruskal;

import java.util.*;

public class KruskalMST {
	int N, M; // 그래프 정점, 간선의 수
	List<Edge>[] graph;
	UnionFind uf; // Union-Find 연산을 사용하기 위해
	Edge[] tree;

	static class Weight_Comparison implements Comparator<Edge> { // weight를 기준으로 우선순위 큐를 사용하기 위해
		public int compare(Edge e, Edge f) {
			if (e.weight > f.weight) return 1;
			else if (e.weight < f.weight) return -1;
			return 0;
		}
	}

	public KruskalMST(List<Edge>[] adjList, int numOfEdges) {
		N = adjList.length;
		M = numOfEdges;
		graph = adjList;
		uf = new UnionFind(N); // Union-Find 연산을 사용하기 위해
		tree = new Edge[N - 1]; // edge = vertex-1
	}

	public Edge[] mst() { // Kruskal 알고리즘
		/* 구현 */
		// weight 순으로 edge 정렬할 기준 생성 (compare()를 통한 자동비교)
		PriorityQueue<Edge> sortByWeight = new PriorityQueue<>(new Weight_Comparison());		
		
		// 실제로 weight 순으로 정렬하기
		for(int i=0; i<N; i++) {
			if(graph[i]!=null) {
				for(Edge e: graph[i]) {
					// 무방향 그래프이므로 (v,a) = (a,v) 동일, 중복 제거하기
					if(e.vertex < e.adjvertex) sortByWeight.add(e);
				}
			}
		}
		
		//추가한 edge count하기 (N-1(edge 최대 개수)이 될때까지 수행 - 종료조건)
		int count=0;
		while(!sortByWeight.isEmpty()) {
			if(count >= N-1) break;
			
			//현재 목록에서 가장 작은 weight를 가진 edge
			Edge e = sortByWeight.poll();
			
			//같은 tree에 있는지 검사 = 이미 연결되어있는지 검사 (사이클 존재 유무)
			if(!uf.isConnected(e.vertex, e.adjvertex)) {
				//새로운 (vertex, adjvertex) edge를 기존 uf에 추가하기
				uf.union(e.vertex, e.adjvertex);
				
				//선택한 edge -> MST tree에 저장
				tree[count] = e;
				count++; //추가했으니 edge 개수 늘려주기
			}
		}
		
		return tree;
	}
}