MST알고리즘 - 크루스칼(Kruskal)

구현 과정 이해하기

---

크루스칼 알고리즘은 탐욕적인 방법을 이용한 간선 선택 기반 알고리즘 입니다.

MST(최소 신장 트리)를 찾는 과정은 아래와 같습니다.

1. 간선들을 가중치의 오름차순으로 정렬합니다.

2. 정렬된 간선 리스트 순서대로 사이클이 형성하지 않는 간선을 선택합니다.

(사이클 형성 여부는 Union Find 알고리즘을 사용하게 됩니다.

3. 선택된 간선을 MST 집합에 추가합니다.

4. 모든 정점을 연결될 때 까지 2~3번 과정을 반복합니다.

 

아래와 같은 연결리스트에서 최소 신장 트리를 찾아내는 구현 과정을 그림으로 확인하면서 이해해보겠습니다.

(!!만약 간선의 가중치 값이 동일할 때, 어느 간선을 먼저 선택할지에 대해선 상관이 없습니다. 사이클이 형성되지 않게만 해주면 됩니다.)

구현과정 그림 설명

 

구현 과정을 위와 같이 이해해보았다면 다음으로 

구현 과정 2번. 사이클 형성 여부를 확인하기 위해서 Disjoint Set의 Union find개념을 알아야 합니다. 이전 글에서 Union find에 대해서 알아보았습니다.

[알고리즘] - Union find(유니온 파인드)

Union find(유니온 파인드)

 

---

 

Kruskal Algorithm with Java

---

구현과정 그림설명

 

5 //노드수
7 //간선수
1 2 10 //정점1 정점2 정점1과2사이의가중치 -> 간선수만큼 입력이 반복되어 들어갑니다.

입력이 위와 같이 들어올 때, Kruskal을 자바로 구현한 코드는 아래와 같습니다.

public class MSTByKruskal {
    public static class Edge implements Comparable<MSTByKruskal.Edge>{
        int start, end, cost;

        public Edge(int start, int end, int cost){
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;//min Heap용
        }
    }

    private static int node, edge;
    private static int[] parent;//union find(cycle 생성여부)에서 필요한 부모노드를 저장하는 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        node = Integer.parseInt(br.readLine());
        edge = Integer.parseInt(br.readLine());

        parent = new int[node+1];

        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
        String[] inputStr;
        for(int i=0;i<edge;i++){
            inputStr = br.readLine().split(" ");
            priorityQueue.add(new Edge(Integer.parseInt(inputStr[0]), Integer.parseInt(inputStr[1]), Integer.parseInt(inputStr[2]))); //STEP 1. 간선의 가중치를 오름차순으로 정렬한다.
        }

        for(int i=1;i<=node;i++) parent[i] = i;//union find(init연산)

        int result = 0;
        for(int i=0;i<edge;i++){
            Edge edge = priorityQueue.poll();//현재 우선순위큐에 있는 edge중 간선 가중치가 가장 작은 것이 poll된다.
            //양쪽 노드의 루트노드가 같은지 확인하고
            int a = find(edge.start);
            int b = find(edge.end);
            if(a==b) continue;//같다면, cycle이 생성되기에 선택하지 않고 넘어간다.
            result += edge.cost;//다르다면, STEP2. cycle이 생성되지 않기에 간선을 선택한다.
            union(a,b);//STEP3. 선택한 간선을 MST 그룹에 추가해준다
        }
        System.out.println(result);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a==b) return;
        else parent[b] = a;
    }

    private static int find(int x) {
        if(x==parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
}

 

 

---

 

프로그래머스 [섬 연결하기]를 크루스칼 알고리즘을 이용해 풀어보았습니다.

전체 코드

import java.util.PriorityQueue;

public class Solution {
    public static class Edge implements Comparable<Solution.Edge>{
        int start,end,cost;
        public Edge(int start, int end, int cost){
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;//가중치 기준 min heap 용
        }
    }
    
    private static int[] parent;
    public int solution(int n, int[][] costs) {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
        for(int i=0;i<costs.length;i++) {
            priorityQueue.add(new Edge(costs[i][0],costs[i][1],costs[i][2]));//우선순위큐 생성
        }
        
        parent = new int[n];
        for(int i=0;i<n;i++){//union find(init)
            parent[i] = i;
        }
        
        int cost = 0;
        for(int i=0;i<costs.length;i++){
            Edge edge = priorityQueue.poll();//가중치 가장 작은 간선 poll
            //두 노드의 루트노드 find
            int a = find(edge.start);
            int b = find(edge.end);
            if(a==b) continue;//cycle 생성시 간선선택 No
            else{//간선 선택 후, MST집합에 추가
                cost += edge.cost;
                parent[b] = a;//union
            }
        }
        return cost;
    }

    private int find(int x) {
        if(parent[x]==x) return x;
        return parent[x] = find(parent[x]);
    }
}

 

 

reference

---

https://blog.naver.com/ssarang8649/221038259400

최소 신장 트리 크루스칼 알고리즘 JAVA로 구현해보기 - Minimum Spanning Tree(MST) Kruskal