[알고리즘/JAVA] 최소 신장 트리(MST) : 크루스칼(Kruskal)

 

최소 신장 트리 (Minimum Spanning Tree, MST)

 

최소 신장 트리는 가중치 무방향 그래프에서 최소 비용으로 모든 정점을 연결하는 트리이다.

사이클이 없음 : 그래프의 모든 정점을 포함하면서 사이클이 없는 그래프 형태로 구성된다.

 

특징

 

• MST는 연결 그래프에서 정의되며 그래프가 연결되지 않은 경우 MST를 구할 수 없다.
• 간선의 개수가 항상 V-1(정점의 개수 - 1)이다.
• MST는 유일하지 않을 수 있으며, 동일한 가중치를 가지는 여러 MST가 존재할 수 있다.

 

---

크루스칼 알고리즘 (Kruskal's Algorithm)

 

• 모든 노드를 연결할 때 필요한 최소 간선 수는 N-1개이며, 이것이 최소 신장 트리의 요구사항이다. 따라서 총 N-1개의 간선을 선택해야 한다.
• 간선을 가중치 순으로 정렬한 뒤, 가중치가 작은 간선부터 차례로 선택하여 그래프를 연결한다.
• 간선 선택 시 사이클 생성 여부를 판단하여, 사이클이 생긴다면 해당 간선은 선택하지 않는다.
• 사이클 판단 알고리즘으로는 주로 Union-Find(분리 집합) 알고리즘을 사용한다.
• 시간 복잡도: O(Nlog⁡(N)) (N은 간선의 수)

 

 

 

알고리즘 과정

(이미지 출처 :  https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)

---

 

1. 최소 가중치(5)를 가지는 A-D 간선을 선택한다.

 

 

 

---

 

2. 선택되지 않은 간선 중 최소 가중치(5)를 가지는 C-E 간선을 선택한다.

 

 

 

 

 

---

 

3. 선택되지 않은 간선 중 최소 가중치(6)를 가지는 D-F 간선을 선택한다.

 

 

 

---

 

4. 선택되지 않은 간선 중 최소 가중치(7)를 가지는 A-B 간선을 선택한다.

 

 

 

 

 

---

 

5. 선택되지 않은 간선 중 최소 가중치(7)를 가지는 B-E 간선을 선택한다.

그 다음 최소 가중치를 가지는 B-C(8), E-F(8), D-B(9)는 사이클을 형성하므로 선택하지 않는다.

 

 

 

 

---

 

6. 선택되지 않은 간선 중 최소 가중치(9)를 가지는 E-G 간선을 선택한다.

총 N-1개의 간선을 선택했으므로 최소 신장 트리가 완성되고, 알고리즘을 종료한다.

 

---

Union-find 알고리즘 

간선을 선택할 때 마다 사이클을 이루는 지 검사해야한다고 언급했다. 이 때 Union-find 알고리즘이 사용된다.

해당 알고리즘은 두 가지 기본 연산으로 구성된다.

• Union 연산: 여러 노드 중 두 노드를 선택하여 이들을 하나의 집합으로 연결한다. 이 연산을 통해 서로 연결된 노드들이 같은 집합에 속하게 된다.
• Find 연산: 특정 노드의 대표 노드를 찾아낸다. 두 노드의 대표 노드를 찾아낸다면 해당 노드들이 같은 집합에 속해 있는지를 확인할 수 있다.

우리는 Find 연산을 통해서 간선이 연결하는 두 노드가 이미 같은 집합에 포함되어 있는지를 검사하고, 같은 집합에 포함되어 있지 않다면, 사이클을 형성하지 않는 것으로 판단한다.

간선을 선택한 이후에는 Union 연산을 통해서 두 노드를 연결시켜주어 같은 집합에 속하도록 갱신한다.

 

https://sjh9708.tistory.com/241

[알고리즘/JAVA] 유니온 파인드 (Union-find, Disjoint-Set)

 

 

---

문제 : 크루스칼 알고리즘 구현 (백준 1197, 최소 스패닝 트리)

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

public class Main {
    static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] edges = new int[m][3];
        
        // Union-find를 위한 집합의 대표 노드
        parents = new int[n+1];
        for(int i = 1; i <= n; i++){
            parents[i] = i;
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            edges[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
        }

        // 간선을 가중치 순으로 정렬
        Arrays.sort(edges, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        int count = 0;
        int sum = 0;
        for(int i = 0; i < m; i++){
            if(count == n - 1) break; //N-1개의 간선이 선택되었다면 종료
            if(union(edges[i][0], edges[i][1])){   // 사이클을 형성하지 않는다면 Union 연산을 통해 두 노드를 동일한 집합으로 갱신한다.
                sum += edges[i][2];
                count++;
            }
        }
        System.out.println(sum);
    }
    
    // Union 연산
    static boolean union(int n1, int n2){
        int p1 = find(n1);
        int p2 = find(n2);
        if(p1 == p2) return false; // 두 대표 노드가 같으면 이미 같은 집합에 속함. 즉 간선을 추가하게 되면 사이클 형성
        else{ // 두 노드를 같은 집합으로 연결
            if(p1 > p2) parents[p1] = p2;
            else parents[p2] = p1;
            return true;
        }
    }
    
    // Find 연산
    static int find(int n){
        if(parents[n] != n){
            parents[n] = find(parents[n]);
        }
        return parents[n];
    }
}

 

• 간선 정렬: 간선들을 가중치 기준으로 오름차순 정렬하여 최소 비용 간선부터 처리할 수 있도록 준비한다.
• 크루스칼 알고리즘: 정렬된 간선을 순회하며 Union 연산으로 두 정점을 같은 집합으로 묶는다. 사이클이 형성되지 않으면 간선을 MST에 추가하고 sum에 추가.
• Union-Find 사용: find로 각 정점의 대표 노드를 확인하고, union으로 두 노드를 연결. 사이클이 발생하면 false를 반환하여 간선 추가를 건너뛰도록 한다.