크루스칼

1. 크루스칼 (Kruskal) 알고리즘이란?

그리디 알고리즘과 Union&Find를 활용해 주어진 그래프 내에서 최소 스패닝 트리를 찾는 알고리즘이다.

2. 동작 원리

그 때 당시 최소 비용으로 갈 수 있는 정점을 방문 정점들과 같은 그룹으로 묶어 가면서 최소 스패닝 트리를 구한다.

그리디한 방식으로 당시에 선택되지 않는 간선 중 최소 비용 간선을 뽑는다.

해당 간선이 트리의 정의를 깨는 순환을 만드는지 확인한다. (union&find 이용)

만약 순환을 만들지 않으면 해당 간선을 방문 처리하고 모든 간선을 확인할 때까지 1번부터 다시 반복한다.
(MST 전체 간선 비용 계산해야 하면 이때 답 누적)

3. 동작 과정

(0) 준비물

간선 리스트
: (정점1, 정점2, 가중치) 형식으로 이루어진 간선 리스트를 만든다.
모든 간선을 저장한 후에 가중치가 작은 순으로 정렬한다.

유니온파인드 용 배열
: 간선 리스트를 순회하며 (A,B,가중치) 형태의 객체를 마주할 때, 정점 A와 정점 B가 이미 같은 트리의 구성원인지 확인하는 용도이다.

(1) 동작

간선리스트에 (정점A, 정점B, 가중치) 형태로 데이터를 저장한다.

간선리스트를 가중치가 작은 순으로 정렬한다.

간선리스트를 순회하며 다음을 반복한다.

간선 객체의 정점 A와 정점 B가 유니온 파인드 상 같은 집합에 속하는지 확인한다.

만약 같은 집합에 속하면 이미 최소 스패닝 트리의 일원이므로 현 간선을 이으면 안된다. 따라서 넘어간다. ( 현재 간선을 이으면 순환이 생기므로 트리의 정의에서 벗어남)

만약 같은 집합에 속하지 않으면 둘을 잇는다. (Union(A,B) 실행 및 가중치 더하기)

(2) 예시

기본 형태는 위와 같을 것이다.첫번째 간선에 대한 작업 수행

두 번째 간선에 대한 작업 수행

세 번째 간선에 대한 작업 수행
(1,4,3)을 이으면, 순회가 생겨서 더 이상 트리가 아니게 되므로 해당 간선은 넘어간다.

네번째 작업을 수행

5번째 작업 수행

6번째 작업 수행.
(2,5,5) 또한 연결하면 순환이 생기므로, 넘어간다.
순환은 아직 두 정점을 UNION으로 연결하지도 않았는데, 둘의 조상이 겹치는 경우에 존재하는 것으로 간주 가능하다.

7번째 작업 수행
이번 작업을 끝으로 트리의 간선 N-1 개를 모두 찾았음으로 더 이상 그 뒤의 계산을 진행할 필요가 없다.

3. 시간복잡도

O(E \log{E})

간선 정렬: $O(E \log{E})$

UNION & FIND
:최적화 기법을 적용하면 하나의 UNION 혹은 FIND 계산 당 시간복잡도가 상수 시간에 가깝다. 최대 E번의 찾기 및 합치기 과정을 진행할 것이므로 $O(E)$

즉 간선 정렬이 최대 시간 복잡도 이다.

4. 예시 코드

최소 스패닝 트리의 총 가중치를 구하는 크루스칼 알고리즘 코드


import java.util.*;
import java.io.*;

public class Main {
  static class Edge implements Comparable<Edge> {
  	int v1;
    int v2;
    int cost;

    public Edge (int v1, int v2, int cost) {
    	this.v1 = v1;
      	this.v2 = v2;
      	this.cost = cost;
    }

	@Override
    public int compareTo (Edge ob) {
    	return this.cost - ob.cost;
    }

  }
  static int V, E;
  static int [] unf;
  static ArrayList<Edge> list;

  public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    V = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());
    unf = new int [V+1];
    list = new ArrayList<>();

    for(int i = 1; i <=V; i++){
    	unf[i] = i;
    }

    for(int i = 0; i<E; i++) {
    	st = new StringTokenizer(br.readLine());
      	int v1 = Integer.parseInt(st.nextToken());
      	int v2 = Integer.parseInt(st.nextToken());
      	int cost = Integer.parseInt(st.nextToken());
      	list.add(new Edge(v1,v2,cost));
    }
    Collections.sort(list);
    int sum = 0;
    for(int i = 0; i < E; i++) {
    	Edge now = list.get(i);
      	if(find(now.v1) == find(now.v2)) continue;
      	union(now.v1, now.v2);
      	sum += now.cost;
    }
    System.out.println(sum);
  }

  public static void union (int a, int b) {
  	int rootA = find(a);
    int rootB = find(b);
    if(rootA > rootB) unf[rootA] = rootB;
    else unf[rootB] = rootA;
  }

  public static int find(int a) {
  	if(unf[a] == a) return a;
    return unf[a] = find(unf[a]);
  }
}

B. 참고 문서

최소 스패닝 트리 (MST): 크루스칼 알고리즘

⬅️ 이전 글

➡️ 다음 글

숨숨 베이스