Kruskal vs Prim

신장 트리란? 

그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다.

사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다.

 

최소 비용 신장 트리란?

신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다.

 

최소 비용 신장 트리의 특징

1. 무방향 가중치 그래프입니다.
2. 가중치의 합이 최소입니다.
3. 정점 n개에서 n - 1개의 간선을 가지는 트리입니다.
4. 사이클이 포함되서는 안됩니다.

 

최소 비용 신장 트리의 사용

도로망, 통신망, 유통망 등 여러 분야에서 비용을 최소로 해야하는 경우에 유용하게 사용됩니다.

 

최소 비용 신장 트리를 구성하는 방법

• Kruskal(크루스칼 알고리즘)
• Prim(프림 알고리즘)

 

Kruskal 알고리즘

: 간선 선택 기반의 알고리즘이며, Greedy 방법을 이용합니다. 간선을 하나씩 선택해서 MST를 찾는 알고리즘

 

동작

1) 그래프의 간선들을 가중치의 오름차순으로 정렬

2) 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택 (Union Find 이용하는 것이 유리)

3) 선택한 간선을 MST 집합에 추가하고 n-1 개의 간선이 선택될 때까지 반복 수행

 

(프로그래머스 섬 연결하기 Lv3)

import java.util.*;
 
class pro_connectIsland {
    static int[] parent;
    public int solution(int n, int[][] costs) {
        int answer = 0;
       Arrays.sort(costs, (o1,o2) ->; Integer.compare(o1[2], o2[2]));
        parent = new int[n];
 
        for(int i=0; i<n; i++){
            parent[i] = i;
        }
 
        for(int i=0; i<costs.length; i++){
            if(find(costs[i][0]) != find(costs[i][1])){
                union(costs[i][0],costs[i][1]);
                answer += costs[i][2];
            }
        }
        return answer;
    }
    private static int find(int val){
        if(parent[val] == val)  return val;
        return find(parent[val]);
    }
    private static void union(int a, int b){
        int c = find(a);
        int d = find(b);
 
        if(c < d){
            parent[d] = c;
        }
        else{
            parent[c] = d;
        }
    }
}

 

 

 

Prim 알고리즘 : 정점 선택 기반의 알고리즘으로, 하나의 정점에서 연결된 간선들 중에 최소 간선 비용을 가진 정점을 하나씩 선택하면서 MST를 찾는 알고리즘

 

 

프림 알고리즘 동작 과정

1. 임의의 정점 하나를 선택해서 시작합니다.
2. 선택한 정점과 인접하는 정점들 중에 최소 비용의 간선을 가지는 정점을 선택합니다.
3. 모든 정점이 선택될 때까지 반복합니다.

프림의 경우 선택된 정점들과 연결된, 선택되지 않은 정점들의 간선에서 최소 간선 비용을 가진 정점을 선택하는 방식으로 진행됩니다.

 

(프림 알고리즘 예시) 우선순위를 사용했고, 인접행렬을 사용하는 방법도 있음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
 
public class Prim_pq {
 
    public static class Vertex implements Comparable<Vertex>{
        int v, dist;
 
        Vertex(int v, int dist){
            this.v = v;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(Vertex o) {
            return Integer.compare(this.dist, o.dist);
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input1[] = br.readLine().split(" ");
        int V = Integer.parseInt(input1[0]);
        int E = Integer.parseInt(input1[1]);
 
        int result = 0;
 
        List<Vertex> list[] = new ArrayList[V];
 
        for(int i = 0; i < V; i++) list[i] = new ArrayList<Vertex>();
 
        // 간선의 정보와 가중치 입력 받기
        for(int i = 0; i < E; i++) {
            String input2[] = br.readLine().split(" ");
            int a = Integer.parseInt(input2[0]) - 1;
            int b = Integer.parseInt(input2[1]) - 1;
            int c = Integer.parseInt(input2[2]);
            // 인접 리스트 구성
            list[a].add(new Vertex(b, c));  
            list[b].add(new Vertex(a, c));  
        }
 
        // 선택되었는지 아닌지 판단하기 위한 boolean 배열
        boolean visited[] = new boolean[V];
        // 현재 선택된 정점들로부터 도달할 수 있는 최소 거리 저장 배열
        int distance[] = new int[V];
 
        // 모두 최대 값으로 key를 갱신
        Arrays.fill(distance, Integer.MAX_VALUE);
 
        distance[0] = 0; // 처음 선택한 정점은 거리 0
        int cnt = 0;
 
        PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();
        q.offer(new Vertex(0, distance[0]));
 
        while(true) {
            Vertex cur = q.poll();
 
            if(visited[cur.v]) continue; 
            visited[cur.v] = true;
            result += cur.dist;
            cnt++;
 
            if(cnt == V) break;
 
            for(Vertex v : list[cur.v]) {
                if(!visited[v.v] && distance[v.v] > v.dist) {
                    distance[v.v] = v.dist;
                    q.offer(new Vertex(v.v, distance[v.v]));
                }
            }
        }
        System.out.println(result);
    }
}