크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm)

< 핵심 >

내림차순으로 정렬된 엣지를 하나씩 뽑아 노드에 연결되는 엣지로 사용할 것인지를 정하는 것이다.

< 구현 방식 >

즉, 두 노드의 루트가 다를 때 작은 값을 가지는 노드를 기준으로 루트를 union한다.

두 노드의 루트가 같다는 것은 하나로 연결이 되어 있다는 뜻이다.

(여기서 한 노드의 루트를 찾는 find 메서드(또는 함수)가 필요해진다.)

만약 두 노드의 루트가 같다면, 연결하지 않는다. → 싸이클(Cycle)이 생성될 수 있다.

예시 코드 (백준 BOJ 1922 네트워크 연결)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; class edge implements Comparable { int a, b; int cost; edge(int a, int b, int cost){ this.a = a; this.b = b; this.cost = cost; } @Override public int compareTo(edge e){ return this.cost > e.cost ? 1 : -1; } } public class Main { static int[] p; // parent public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int V = Integer.parseInt(br.readLine()); int E = Integer.parseInt(br.readLine()); p = new int[V+1]; for(int i=0; i<=V; ++i){ p[i] = i; } StringTokenizer st; PriorityQueue pq = new PriorityQueue<>(); for(int i=0; i 싸이클 생성 방지 } System.out.print(ans); } // 루트 찾아서 반환 public static int find(int a){ if(a != p[a]){ p[a] = find(p[a]); return p[a]; } return a; } // 루트 일치화 public static void union(int aRoot, int bRoot){ // + 이미 루트를 구했으므로 구할 필요가 없다. // + 이미 main 반복문에서 비교했으므로 할 필요가 없다. // a가 더 작은 수니까 a를 넣는 게 맞다. p[bRoot] = aRoot; } }

< 활용 >

모든 노드를 최소의 비용으로 연결시키는 설계에 유용하다. ( 각 노드는 한 번씩만 연결되며 싸이클은 존재하지 않는다. )

from http://verycrazy.tistory.com/26 by ccl(A) rewrite - 2021-11-16 17:26:39