[Alogrithm] Kruskal(크루스칼)

MST(최소 신장 트리)를 찾는 알고리즘
1. Kruskal(크루스칼)
2. Prim(프림)

MST(최소 신장 트리) 알고리즘
신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘

신장 트리
하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

✔️ 간선을 하나씩 선택해서 MST를 찾는 알고리즘

✔️ 그리디 알고리즘

과정

☁️ 1. 최초, 모든 간선을 가중치에 따라 **오름차순**으로 정렬

2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

① 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택

② 사이클 여부는 union-find를 활용해 찾는다

3. n-1개의 간선이 선택될 때까지 2를 반복

• 설명
  

구현

• 크루스칼 알고리즘

  public static void kruskal(int[][] graph, int[] parent) {
  	int cost = 0;
  	for(int i = 0; i < graph.length;i++) {
  		if (find(parent, graph[i][0]) != find(parent, graph[i][1])) {
  			cost += graph[i][2];
  			union(parent, graph[i][0], graph[i][1]);
  		}
  	}
  	System.out.println(cost);
  }

• 전체코드

  public class Main {
  	// 유니온 
  	public static void union(int[] parent, int x, int y) {
  		x = find(parent, x);
  		y = find(parent, y);
  		
  		if(x < y) parent[y] = x;
  		else parent[x] = y;
  	}
    // 파인드
  	public static int find(int[] parent, int x) {
  		if(parent[x] == x) return x;
  		else return find(parent, parent[x]);
  	}
  	
    // 크루스칼
  	public static void kruskal(int[][] graph, int[] parent) {
  		int cost = 0;
  		for(int i = 0; i < graph.length;i++) {
  			if (find(parent, graph[i][0]) != find(parent, graph[i][1])) {
  				cost += graph[i][2];
  				union(parent, graph[i][0], graph[i][1]);
  			}
  		}
          
      // 최소 신장 트리의 총 가중치 출력
  		System.out.println(cost);
  	}
  	
  	public static void main(String[] args) throws IOException {
      	// 간선 입력 받기, 그래프에 저장
  		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  		int n = Integer.parseInt(bf.readLine());
  		int m = Integer.parseInt(bf.readLine());
  		int[][] graph = new int[m][3];
  		
  		StringTokenizer st;
  		for (int i = 0; i < m; i++) {
  			st = new StringTokenizer(bf.readLine());
  			graph[i][0] = Integer.parseInt(st.nextToken()); // 간선 나가는 정점
  			graph[i][1] = Integer.parseInt(st.nextToken()); // 간선 들어오는 정점
  			graph[i][2] = Integer.parseInt(st.nextToken()); // 가중치
  		}
  		
          // 간선 정렬
  		Arrays.sort(graph, (o1, o2) -> o1[2] - o2[2]);
  		
          // 부모노드 초기화
  		int[] parent = new int[n + 1];
  		for (int i = 0; i < parent.length; i++) {
  			parent[i] = i;
  		}
          
  		//크루스칼 알고리즘 수행
  		kruskal(graph, parent)
  	}
  }

  입력
  5
  6
  1 3 3
  1 4 8
  4 5 9
  1 2 10
  2 3 13
  2 5 14
  
  출력 결과
  30

시간 복잡도

$O(ElogE)$

크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가진다. 왜냐하면 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이며, E개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)이기 때문이다.(퀵 정렬 사용시)

크루스칼 내부에서 사용되는 서로소 집합(Union-Find) 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작으므로 무시한다.