크루스칼과 프림 (최소신장 트리)

신장트리(Spanning Tree)

---

신장트리의 조건

1. N개의 정점을 가지는 그래프에서 최소 N-1 개의 간선으로 연결되어 있다.
2. 그래프의 모든 정점을 포함한다.

신장트리는 최소한의 간선으로 모든 정점을 연결한 트리이다.
따라서 사이클이 존재하지 않는 특징이 있다.

 

최소 신장 트리(Minimum Spanning Tree)

---

최소한의 간선으로 모든 정점을 연결하며, 이때 간선의 가중치의 합이 최소로 이루어진 트리

 

크루스칼 알고리즘

---

크루스칼 알고리즘은 최소 신장 트리를 만들기 위한 알고리즘으로 그리디 알고리즘의 한 종류이다.

매 순간 가중치가 가장 낮은 간선을 선택한다.

이러한 그리디 알고리즘 방식은 로컬 최적해를 구하지만 전체 최적해를 보장하지 않는다.

하지만, 크루스칼 알고리즘은 사이클이 존재하지 않는 조건을 통해 로컬 최적해가 전체 최적해가 됨을 보장한다.

크루스칼 알고리즘이 핵심인 사이클의 존재여부를 판단하기 위해 union-find를 이용한다.

 

[알고리즘 구조]

1. 가중치 기준 오름차순 정렬
2. 가중치가 가장 낮으며, union-find 알고리즘을 통해 사이클을 형성하지 않는 간선 선택
3. 전체 해 결과 집합에 포함

[시간복잡도]

• 가중치 정렬 시간복잡도 O(ElogE)
• union-find 시간복잡도 O(1)
• 전체 O(ElogE)

 

Union-Find

---

union-find란 ‘합집합 찾기’라는 알고리즘이다.

여러개의 노드가 존재할 때 두 노드를 선택하여 서로 같은 집합인지 여부를 확인할 수 있다.

간단하게 조상 노드가 같으면 같은 집합이라고 할 수 있다.

반대로 조상 노드가 같은게 없다면 서로 다른 집합이라고 할 수 있고, 그래프에서 사이클이 존재하지 않는다고 판단할 수 있다.

조상노드를 정하기 위해 항상 '부모노드는 자식노드 보다 값이 작다'라는 규칙을 정할 수 있다.(반대도 가능)

 

아래와 같이 다섯개의 노드가 존재한다고 하자.

 

배열을 통해 두 노드가 서로 같은 집합에 존재하는지 여부를 체크할 것이다.

같은 집합에 존재한다면 같은 부모 노드의 번호를 갖게 할 것이고, 번호가 작은 노드를 부모 노드로 할 것이다.

즉, 번호가 작은쪽으로 집합을 합칠 것이다.

 

아래와 같이 우선 자기 자신을 부모 노드로 선언하자.

노드 번호	1	2	3	4	5
부모 노드 번호	1	2	3	4	5

 

이 상태에서 아래와 같이 서로 같은 집합의 조건이 주어졌을 때, 배열이 어떻게 변하는지 확인해 보자.

R1 : (1, 4)

R2 : (1, 5)

R3 : (2, 3)

 

첫번째 라운드 이후

노드 번호	1	2	3	4	5
부모 노드 번호	1	2	3	1	5

두번째 라운드 이후

노드 번호	1	2	3	4	5
부모 노드 번호	1	2	3	1	1

세번째 라운드 이후

노드 번호	1	2	3	4	5
부모 노드 번호	1	2	2	1	1

최종 결과를 보면 노드 1, 노드 4, 노드 5는 모두 부모노드롤 1을 갖고,

노드2, 노드 3는 부모노드로 2를 갖는다.

 

노드 번호가 작은 쪽으로 집합이 합쳐짐을 확인 할 수 있다.

 

 

[Union-Find 알고리즘 구현]

이제 union-find 알고리즘이 어떻게 이루어져있는지 보자.

static int getParent(int x){
   if(parent[x]==x) return x;
   else return parent[x] = getParent(parent[x]);
}

static void union(int a, int b){
   int parentA = getParent(a);
   int parentB = getParent(b);

   if(parentA<parentB) {
       parent[a]=parent[b]=parentA;
   } else {
       parent[a]=parent[b]=parentB;
   }
}

 

위의 union 함수가 집합을 합치는 역할을 하고, getParent함수가 부모노드를 find하는 역할을 한다.

parent 배열이 위 부모노드 번호를 체크한 배열이다.

 

getParent함수는 재귀 함수 형태이다.

재귀함수 형태이므로, 모든 계산이 가능하다. 

그러나 완전 재귀함수는 아니다.

parent[x] = getParent(parent[x]);와 같이 재귀 호출 과정에서 부모 노드를 갱신 하는 코드가 존재한다.

다음번 함수 호출시에는 부모 노드를 찾기 위해 재귀를 계속 호출 하는 것이 아닌 바로 부모 노드의 값에 접근할 수 있다.(경로 압축)

 

시간 복잡도

union-find의 시간 복잡도는 어떻게 될까?

union함수의 경우 getParent를 호출하기에 (getParent의 시간복잡도)*2 +2로 보면 될 것이다.

 

union-find의 시간복잡도는 find함수의 시간복잡도가 핵심이다.

이론적으로 union-find의 find 함수의 시간 복잡도는 O(a(N))을 갖는다고 한다. 

a(N)은 아커만 함수를 의미하는데 거의 상수에 가까운 수로가 보면 무방하다고 한다.

 

union-find 주의점 : 정렬

예제를 보며 union-find 사용시 주의할 점에 대해 알아보자.

 

예제1)

R1 : (1, 2)

R2 : (3, 4)

R3 : (1, 4)

 

첫번째 라운드 이후

노드 번호	1	2	3	4
부모 노드 번호	1	1	3	4

 

두번째 라운드 이후

노드 번호	1	2	3	4
부모 노드 번호	1	1	3	3

 

세번째 라운드 이후

노드 번호	1	2	3	4
부모 노드 번호	1	1	3	1

 

예제2)

R1 : (1, 2)

R2 : (1, 4)

R3 : (3, 4)

 

첫번째 라운드 이후

노드 번호	1	2	3	4
부모 노드 번호	1	1	3	4

 

두번째 라운드 이후

노드 번호	1	2	3	4
부모 노드 번호	1	1	3	1

 

세번째 라운드 이후

노드 번호	1	2	3	4
부모 노드 번호	1	1	1	1

 

예제1)과 예제2)의 주어진 합집합의 조건은 갖고 실행 순서만 다르다.

최종결과를 보면 예제1)은 3번 노드의 부모노드는 3으로 되어있고 예제2)의 부모 노드는 1로 되어있다.

조건에 따르면 모두 같은 집합에 속해야한다.

 

그렇다. union-find 사용시 집합 조건의 정렬여부를 고려해야 한다.

작은 노드 번호로 부모 노드를 셋팅하기에 작은 노드 순으로 실행을 해야 원하는 결과를 얻을 수 있다.

여기서 잠깐. union-find 사용시 반드시 작은 노드 번호로 부모 노드 번호를 설정해야하나?? 그렇지 않다. 큰 번호로 설정해도 상관 없다. 단순히 노드 번호 값이 작은 것을 부모 노드로 할지, 큰 것을 부모노드로 할지에 대해서는 상관 없다. union 함수의 부등호 방향만 바꿔주면 된다.

 

정렬을 고려하지 않아도 되는 union-find

static void union(int a, int b){
   int parentA = getParent(a);
   int parentB = getParent(b);

   if(parentA<parentB) {
       parent[a]=parent[b]=parentA;
   } else {
       parent[a]=parent[b]=parentB;
   }
}

 

이 union 함수는 가장 최적화가 되어있는 형태이다.

하지만 의도적으로 알고리즘의 효율을 떨어트려야하는 상황이 있을 수 도 있다.

 

아래 union 함수를 보자.

static void union(int a, int b) {
   int parentA = getParent(a);
   int parentB = getParent(b);

   if (parentA<parentB){
       parent[parentB] = parent[parentA] = parentA;
   }
   else{
       parent[parentA] =parent[parentB]= parentB;
   }
}

 

첫번째 union 함수 구조와 달리 자기자신의 부모 노드를 바꾸는게 아니라 부모 노드의 부모 노드를 바꾸고 있다.

왜 이렇게 알고리즘을 구현하는 것일까?

위의 코드로 예제1)을 다시 풀어보라

 

세번째 라운드 이후 

노드 번호	1	2	3	4
부모 노드 번호	1	1	1	3

 위와 같은 결과를 얻게 될 것이다.

그렇다. 정렬을 하지 않더라도 정렬한 결과를 얻을 수 있다.

union-find를 사용할 때, 노드 번호 순으로 정렬을 하고 첫번째 코드로 사용하는게 훨씬 효율적이겠지만

만약 정렬을 할 수 없는 상황이라면 위와 같이 정렬한 것과 같이 결과를 얻을 수 있다.

 

부모노드의 번호는 항상 자신보다 작은 값이므로 부모의 부모를 바꿔주면 오름차순 정렬이 되는 것이다.

 

이 방식을 사용하는 것이 효과적인 상황이 있다. 

예를 들어 노드들 간의 간선에 가중치가 존재하고 우리는 이 가중치가 최소가 되도록 노드를 연결해야한다면
노드 번호 순이 아닌 간선의 가중치 기준으로 정렬을 할 것이다.

가중치 기준으로 정렬된 자료구조를 통해 union-find를 수행하면 이전의 예제1)과 같은 상황이 나타날 수 있다.

이를 해결하기 위해 노드 번호 기준으로 정렬된 자료를 하나 더 만들어 수행할 것인가??

그렇게 되면 더욱 비효율적인 상황이 아닌가??

 

이렇게 union-find의 최적화는 포기하지만 다른 연산 횟수를 줄여 결과적으로 비용 절감을 이뤄낼 수 있다.

그 예시의 가장 대표적인 경우가 크루스칼 알고리즘을 사용하는 경우이다.

 

프림 알고리즘

---

최소신장트리를 구하는 알고리즘으로 

새로운 정점을 연결할 때마다 간선을 추가하며 트리를 확장해 나가는 방식을 취하게 된다.

다익스트라 알고리즘과 같이 방문한 정점을 체크하며 한번 방문했던 지점은 다시 방문하지 않는 방식으로 구현하게된다.

가중치가 가장 낮은 것을 선택하기 위해서 PriorityQueue를 이용할 수 있다.

 

[알고리즘 구조]

1. 처음 방문할 정점 선택
2. 현재 방문한 정점들에 연결된 모든 간선을 우선순위큐에 넣음(가중치 기준 오름차순 정렬)
3. 우선순위 큐에서 가장 작은 가중치 간선 꺼내며 방문하지 않았다면 방문하고 큐에 추가
4. 2-3 과정 반복

[시간복잡도]

• 현재 정점에 연결된 정점을 우선순위 큐에 삽입하므로 logV
• 이때, 연결된 정점은 간선 정보에서 가져오므로 E
• 전체 시간 복잡도 O(ElogV)

프림 알고리즘의 시간복잡도는 2번 과정이 핵심이다.

나머지는 시간복잡도가 상수항이니 무시한다.

 

크루스칼과 프림의 차이

---

크루스칼 알고리즘과 프림 알고리즘은 모두 최소 스패닝 트리를 구하는 알고리즘이기에,

주어진 문제의 해를 구할 수 있는지 없는지에 차이는 존재하지 않다.

크루스칼로 가능하면 프림으로도 가능하고, 프림으로 가능하면 크루스칼로도 가능하다.

단, 구분해야할 것은 union-find 알고리즘은 크루스칼에서 사용하는 알고리즘이지

union-find 알고리즘과 크루스칼 알고리즘을 같게 보면 안된다.

주어진 문제가 union-find를 통해 해를 구할 수 있다고해서 프림으로도 풀수 있을 것이라고 생각하면 안된다.

union-find는 최소신장트리를 구하기 위함이 아니라 합집합을 찾는(반대로 서로소를 찾는) 알고리즘이다.

 

크루스칼과 프림의 차이는 성능의 차이로 보면 될것 같다.

크루스칼은 O(ElogE), 프림은 O(VlogE)이므로 간선정보가 많다면 프림, 간선이 적다면 크루스칼을 도입하는 것이 빠른 문제 해결에 더욱 도움이 된다.

 

크루스칼과 프림을 통한 문제해결(백준 1197)

---

[문제]

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

전형적인 최스 스패닝 트리를 구하는 문제이다.

아래 크루스칼과 프림을 통한 해결 코드를 첨부하였으니 참고 바란다.

 

[크루스칼 알고리즘]

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


public class Main {
    
    static int[] parent;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        parent = new int[V+1];
        for(int i=1; i<V+1; i++) parent[i] =i;
        
        Edge[] edges = new Edge[E];
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(u, v, c);
        }
        // 가중치 오름차순 정렬
        Arrays.sort(edges, (o1, o2) -> (o1.c-o2.c));
        
        int sum =0;
        for(int i=0; i<E; i++) {
            if(getParent(edges[i].u) == getParent(edges[i].v)) continue;
            union(edges[i].u, edges[i].v);
            sum += edges[i].c;
        }
        
        System.out.println(sum);
    }
    
    public static int getParent(int x) {
        if(parent[x]==x) return x;
        else return parent[x] = getParent(parent[x]);
    }
    
    public static void union(int a, int b) {
        int parentA = getParent(a);
        int parentB = getParent(b);
        
        if(parentA<parentB) {
            parent[parentA] = parent[parentB] = parentA;
        }else {
            parent[parentA] = parent[parentB] = parentB;
        }
    }
    
    static class Edge{
        int u;
        int v;
        int c;
        
        public Edge(int u, int v, int c) {
            this.u = u;
            this.v = v;
            this.c = c;
        }
    }
    
}

 

[프림 알고리즘]

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		HashMap<Integer, ArrayList<Edge>> edgeMap = new HashMap<>();
		for (int i = 1; i <= V; i++) {
			edgeMap.put(i, new ArrayList<Edge>());
		}
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken()); //가중치
			
			ArrayList<Edge> list = edgeMap.get(a);
			list.add(new Edge(b, cost));
			edgeMap.put(a, list);
			
			list = edgeMap.get(b);
			list.add(new Edge(a, cost));
			edgeMap.put(b, list);
		}
		
		// 가중치 오름차순 정렬
		PriorityQueue<Edge> qu = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge p1, Edge p2) {
				return p1.cost - p2.cost;
			}
		});
		
		boolean[] vis = new boolean[V+1]; //방문한 정점들
		vis[1] = true; //임의로 1부터 정점 방문 시작
		ArrayList<Edge> list = edgeMap.get(1);
		for (Edge edge : list) {
			qu.add(edge);
		}
		
		int cost = 0; //최종 비용의 합
		int cost_v = 1; //방문한 정점의 수. V개와 같아지면 반복문을 멈춘다
		while (cost_v != V) {
			
			Edge edge = qu.poll();
            // 방문한 정점은 스킵(사이클 방지)
			while (vis[edge.to]) edge = qu.poll();
			cost += edge.cost;
			vis[edge.to]= true;
			cost_v++;
			
            // 새롭게 방문한 정점에 연결된 간선 큐에 넣기
			list = edgeMap.get(edge.to);
			for (Edge tmp : list) {
				if (!vis[tmp.to]) qu.add(tmp);
			}
			
		}
		System.out.println(cost);
	}
    
    static class Edge {
    	int to; //정점
	    int cost; //가중치
        
	    Edge(int to, int cost) {
	    	this.to = to;
		    this.cost = cost;
	    }
    }
}