[GDG - 스터디] 최소 스패닝 트리(MST)

최소 스패닝 트리

최소 스패닝 트리(MST) ?

• 최소 스패닝 트리는(MST)는 가중치 그래프에서 모든 정점들을 연결하는 최소 비용의 연결 부분 그래프이다.

MST 조건

1. 모든 정점이 연결되어 있어야 한다 !
2. 사이클이 없어야 한다 !
3. 가중치의 합이 최소여야 한다 !

---

💡 핵심 개념 - 스패닝 트리

• 스패닝 트리는 주어진 그래프의 모든 정점을 포함하는 연결 그래프이며, 간선의 수는 V(정점의 수)-1이다. → 여러 스패닝 트리 중 가중치의 합이 최소인 트리가 MST이다.

---

💡 핵심 개념 - MST를 구하기 위한 알고리즘

• 크루스칼 알고리즘: 간선을 정렬한 뒤, 최소 가중치 간선을 하나씩 선택하면서 사이클이 생기지 않도록 트리를 구성한다.
• 프림(Prim) 알고리즘: 하나의 정점에서 시작하여 인접한 간선 중 최소 가중치를 선택하며 트리를 확장한다.

---

💡 핵심 개념 - 유니온-파인드(Union-Find)

• 크루스칼 알고리즘에서 사이클을 판별하기 위해 사용된다 !
• 간선을 추가하기 전에 두 정점이 이미 **같은 집합(루트가 같은지?)**에 속해 있는지 확인한다 !

GDG 스터디 - 유니온 파인드를 이용해 집합 관계 확인하기

---

💡 MST - 구현

• 시간 복잡도
  • 크루스칼 알고리즘: $O(ElogE)$ → 간선 정렬 비용
  • 프림 알고리즘: $O(ElogV)$ → 우선순위 큐 사용
• 구현 과정
  1. 간선 정보를 리스트에 저장한다.
  2. 크루스칼 알고리즘을 기준으로, 간선을 가중치 순으로 정렬한다.
  3. 유니온-파인드로 사이클을 판별하여, 같은 집합에 속해 있으면 추가하지 않는다.
  4. 간선 수가 V-1이 되면 MST가 완성된다 !

import java.util.*;

public class MSTKruskal {

    static class Edge implements Comparable<Edge> {
        int src, dest, weight;

        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight; // 가중치를 기준으로 정렬
        }
    }

    static int[] parent;

    public static void main(String[] args) {
        // 정점과 간선 개수
        int V = 4; // 정점 개수
        int E = 5; // 간선 개수

        List<Edge> edgeList = new ArrayList<>();

        // 간선 입력 (src, dest, weight)
        edgeList.add(new Edge(0, 1, 10));
        edgeList.add(new Edge(0, 2, 6));
        edgeList.add(new Edge(0, 3, 5));
        edgeList.add(new Edge(1, 3, 15));
        edgeList.add(new Edge(2, 3, 4));

        // 크루스칼 알고리즘 실행
        int mstWeight = kruskalMST(V, edgeList);
        System.out.println("최소 스패닝 트리의 가중치 합: " + mstWeight);
    }

    static int kruskalMST(int V, List<Edge> edgeList) {
        // 간선 정렬
        Collections.sort(edgeList);

        // 유니온-파인드 초기화
        parent = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i; // 각 정점은 초기에는 자기 자신이 부모
        }

        int mstWeight = 0; // MST 가중치 합
        int edgesUsed = 0; // MST에 추가된 간선 수

        for (Edge edge : edgeList) {
            // 간선의 두 정점이 다른 집합에 속해 있으면 추가
            if (find(edge.src) != find(edge.dest)) {
                union(edge.src, edge.dest);
                mstWeight += edge.weight;
                edgesUsed++;

                // MST가 완성되면 종료
                if (edgesUsed == V - 1) break;
            }
        }

        return mstWeight;
    }

    // 유니온-파인드: find 연산 (경로 압축 기법 사용)
    static int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    // 유니온-파인드: union 연산
    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }
}

---

문제: 최소 스패닝 트리 (백준 1197)

문제 링크

 

---

알고리즘 [접근 방법]

1. 먼저 크루스칼 알고리즘을 수행하기 위해서 간선 정보(출발지, 도착지, 가중치)를 저장한 배열을 가중치를 기준으로 오름차순 정렬을 시켜준다.
2. 정렬시킨 엣지 리스트에 대해 크루스칼 알고리즘을 수행하는 과정에서, 유니온-파인드 알고리즘을 사용하여 두 정점(graph[i][0], graph[i][1])이 같은 집합에 있는지 체크하고, 서로 다른 집합에 있다면 스패닝 트리에 해당 간선을 추가한다.
3. 이 과정을 MST가 완성될 때까지 반복하면 된다.

---

해결 코드

• 위에서 다른 구현 코드와 달리 Edge 클래스를 따로 만들지 않고 2차원 배열과 람다식을 사용했다. → 간단한 문제에선 이 방식이 더 효과적이고 빠른 것 같다.

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

public class Main {
	
    static int[][] graph; // 엣지리스트
    static int[] parent;  // 부모 노드
    static int total;     // 최종값
    static int V, E;

    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());

        graph = new int[E][3];
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            graph[i][0] = Integer.parseInt(st.nextToken());
            graph[i][1] = Integer.parseInt(st.nextToken());
            graph[i][2] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(graph, Comparator.comparingInt(o -> o[2]));

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

        kruskal();
        
        br.close();
    }

    static void kruskal(){
        total = 0;
        int edgeCount = 0;
        for(int i=0; i<graph.length; i++){
            if(find(graph[i][0]) != find(graph[i][1])){
                total += graph[i][2];
                union(graph[i][0], graph[i][1]);
                edgeCount++;
                
                // MST가 완성되면 종료
                if (edgeCount == V - 1) break;
            }
        }
        System.out.println(total);
    }

    static void union(int i, int j){
        i = find(i);
        j = find(j);
        if(i<j){
            parent[j] = i;
        } else{
            parent[i] = j;
        }
    }

    static int find(int i){
        if(parent[i] != i){
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }
}

---

정리

• MST를 구하기 위해선 크루스칼 알고리즘과 유니온-파인드 알고리즘을 사용하면 된다.

https://thin-azimuth-2a9.notion.site/GDG-147f4ee21c00803a8149d5ed4cbb35fd?pvs=4

GDG 스터디 - 벨만포드를 이용한 최단 경로 찾기 | Notion