최소신장트리(MST)

최소 신장 트리 (Minimum Spanning Tree)

그래프 이론에서 최소 신장 트리란 모든 노드들을 연결하면서 사이클이 존재하지 않고 각 간선의 가중치의 합이 최소인 트리

주어진 연결 그래프가 있을 때, 최소 신장 트리를 찾는 것은 네트워크 설계, 클러스터링 등의 다양한 분야에서 매우 중요한 문제이다.

 

 

특징

모든 노드가 연결: 그래프의 모든 노드가 서로 연결되어 있어야 하며, 이 과정에서 어떤 노드도 고립되지 않습니다.

사이클이 존재하지 않음: 최소 신장 트리는 트리 구조이므로, 간선이 하나 더 추가되면 사이클이 생기게 됩니다. 따라서 트리에서는 절대 사이클이 존재할 수 없습니다.

최소 가중치: 주어진 그래프의 모든 간선 중, 가중치의 합이 최소가 되도록 간선을 선택합니다.

연결된 그래프: MST는 그래프가 연결되어 있어야만 존재할 수 있습니다. 만약 그래프가 연결되어 있지 않다면 각 연결 성분마다 별도의 MST를 찾을 수 있습니다.

 

 

최소신장트리 종류

최소신장트리는 크게 크루스칼 알고리즘과 프림 알고리즘으로 나뉘는데,  현재 단계에서는 크루스칼 알고리즘만 알아도 괜찮으니

크루스칼 알고리즘을 기준으로 설명하겠습니다.

 

핵심 설명

1) 엣지리스트로 그래프 구현 & 유니온-파인드 배열 초기화

  - 노드가 아닌 엣지중심이므로 인접리스트가 아닌 엣지리스트로 구현합니다.(Edge 클래스도 구현 - 노드변수2개, 가중치 변수 1개)

class Edge {
    int src;     // 출발 노드
    int dest;    // 도착 노드
    int weight;  // 간선의 가중치

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

 

int[] parent = new int[노드의 수];
for (int i = 0; i < 노드의 수; i++) {
    parent[i] = i;  // 각 노드는 자기 자신이 부모 (자기 집합)
}

 

2) 그래프 데이터를 가중치 기준으로 오름차순 정렬

  - 그래프를 정렬하기 위해 엣지리스트를 Priority Queue자료구조로 생성해주면 됩니다.

 

3) 가중치가 낮은 엣지부터 연결시도

  - find 연산을 이용해 사이클 형성 유무를 확인하고, 사이클이 되지 안흥 때만 union연산을 이용해 두 노드 연결을 진행합니다.

 

4) 과정 3 반복

 

5) 총 엣지비용 출력

  - 엣지갯수가 N-1이 되면 알고리즘을 종료, 완성된 MST 총 엣지비용을 출력합니다.

 

 

예제코드 - 백준 1197

package algorithms.src.graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class b1197_최소스패닝트리 {
    private static int[] parent;
    static int cnt, weight = 0;

    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());
        PriorityQueue<Edge> q = new PriorityQueue<Edge>();

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            q.add(new Edge(s, e, v));
        }

        parent = new int[V + 1];  // 유니온 파인드
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }

        while (cnt < V - 1) {
            Edge edge = q.poll();
            if(union(edge.s, edge.e)) {
                weight += edge.v;
            };
        }
        System.out.println(weight);
    }

    private static boolean union(int a, int b) {
        if(find(a) != find(b)) {
            parent[find(b)] = find(a);
            cnt ++;
            return true;
        }
        return false;
    }

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

    private static class Edge implements Comparable<Edge> {
        int s;
        int e;
        int v;

        public Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }

        @Override
        public int compareTo(Edge o) {
            return this.v - o.v;
        }
    }
}