KRUSKAL 알고리즘

1. 기본 개념 🧪

1. 신장 트리 (Spanning Tree)

  n개의 정점을 가지는 그래프에서 n개의 정점을 모두 연결할 수 있는 n-1개의 간선으로 이루어진 트리

(간선은 n-1개 이상일 수 있다.)

물론 n-1개 이상의 간선을 가져도 신장 트리가 될 수 있다.

2. 최소 신장 트리(Minimum Spanning Tree)

무향 가중치 그래프에서 가중치의 합이 가장 작은 신장 트리를 최소 신장 트리라고 한다.

 

2. KRUSKAL 알고리즘 🧫

1. 기본개념

  그리디 방식을 이용하여 최소 신장 트리를 찾는 방식
  그리디한 방식 자체가 항상 최적의 해답을 제공한다는 보장은 없지만, KRUSKAL 알고리즘에서는 최적의 해답을 제공하는 것으로 증명되어있다.

2. 동작 방식

1. 모든 간선들을 가중치에 따라 오름차순으로 정렬한다.
2. 가중치가 낮은 간선들을 선택하여 트리를 만든다.
   이때, 사이클을 만드는 간선은 제외한다.
   사이클의 생성 여부는 'union-find 알고리즘'의 개념을 활용한다.
3. 모든 정점을 포함('정점 - 1'개의 간선을 선택한 경우) 할 때까지 2번을 진행한다.

 

3. 구현 (JAVA) 🧬

  위의 예시를 테스트 케이스로 생각하자.

  먼저 정점의 개수(vertexNum)와 간선의 개수(edgeNum)를 받아온다. 그리고 간선의 개수만큼 간선의 정보(출발지, 도착지, 간선의 가중치)를 가져온다. 'a, b, c, d, e, f, g'는 '0, 1, 2, 3, 4, 5, 6'이라고 하자.

  아래는 입력 정보와 구현 코드이다.

7 9
0 1 29
1 2 16
2 3 12
3 4 22
4 5 27
5 0 10
6 1 15
6 3 18
6 4 25

public class Main {

	static int vertexNum, edgeNum;
	static Edge[] edges;
	static int[] parents;
	
	static class Edge implements Comparable<Edge> {
		
		public int from;
		public int to;
		public int weight;
		
		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	static void makeSet() {
		
		parents = new int[vertexNum];
		
		for(int i = 0; i < vertexNum; i++) {
			parents[i] = i;
		}
	}
	
	static int findSet(int a) {
		
		if(parents[a] == a) {
			return a;
		}
		else {
			return parents[a] = findSet(parents[a]);   
		}
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		
		if(aRoot == bRoot) {
			return false;
		}
		
		parents[aRoot] = bRoot;
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		vertexNum = Integer.parseInt(st.nextToken());
		edgeNum = Integer.parseInt(st.nextToken());
		
		edges = new Edge[edgeNum];
		for(int i = 0; i < edgeNum; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			edges[i] = new Edge(Integer.parseInt(st.nextToken()) // 출발 edge
						, Integer.parseInt(st.nextToken()) // 도착 edge
						, Integer.parseInt(st.nextToken())); // 가중치
		}
		
		// 1. 간선들을 가중치에 따라 오름차순으로 정렬한다.
		Arrays.sort(edges);
		
		makeSet();
		
		int mstWeight = 0;
		int edgeCount = 0;
		
		// 2. 가중치가 낮은 간선을 먼저 선택하여 트리를 만들어 나간다.
		for(Edge edge : edges) {
			if(union(edge.from, edge.to)) { // 사이클을 만들지 않는 경우
				mstWeight += edge.weight;
				
				// 3. 모든 정점을 포함하는 경우 ('정점 - 1'의 간선을 선택한 경우)에 빠져나온다.
				if(++edgeCount == vertexNum - 1) { 
					break;
				}
			}
		}
		
		System.out.println(mstWeight);
	}
}

 

4. 시간복잡도 🔬

  KRUSKAL 알고리즘의 시간복잡도는 간선들을 가중치에 따라 정렬하는 것에 의해 결정된다. 일반적으로 정렬 알고리즘을 고려하였을 때, KRUSKAL알고리즘의 시간 복잡도는 O(N logN)이다.
  그러므로 간선이 많은 경우 다른 방식(PRIM 알고리즘)을 고려해야 한다.