[알고리즘] 최소 스패닝 트리(MST)

 목  차

• 최소 스패닝 트리(Minimum Spanning Tree)
• 기본 개념 및 조건
• 위상정렬을 구현하며 배운 것들
• 구현 방법

 
선행 개념: Union-Find-Algorithm
 

---

 

  최소 스패닝 트리(Minimum Spanning Tree)

 
사이클(cycle)이 없으면서 연결된 노드간의 간선 가중치가 최소인 것을 구하는 알고리즘
 
요약하자면 그래프 내에서 가장 효율적인 연결 구조를 찾는 것이다. 

 
 

---

 

  알고리즘 종류

 

• 프림 알고리즘: 하나의 노드에서 시작하여, 가장 낮은 가중치를 가진 간선을 선택하면서 점진적으로 트리를 확장한다.
• 크루스칼 알고리즘: 모든 간선을 가중치를 기준으로 정렬하고, 가장 낮은 가중치의 간선부터 추가하면서 트리를 구성한다. 

 
중요한 포인트는 사이클이 생기지 않는 것이다.
 
 

---

  구현 방법과 알고리즘 문제

 
크루스칼 알고리즘으로 구현을 해보려고 하는데, 크루스칼 알고리즘은 우선순위 큐를 사용한다.
 
1. 우선순위 큐에 모든 간선의 정보를 입력
2. 가장 낮은 가중치를 가진 간선을 pop
3 - 1. 목적지에 갔을 때 사이클이 생기면 continue;
3 - 2. 목적지에 갔을 때 사이클이 생기지 않으면 해당 노드를 흡수.
* 중요한 점은 해당 노드를 흡수할 때, 그 노드에 연결된 다른 노드들도 흡수를 해주어야 한다.
 
 
최소 스패닝 트리 알고리즘 문제는 백준 1922 번 문제 네트워크 연결을 예시로 보면 좋을 것 같다.
이 문제에서는 '모든 컴퓨터를 연결하는 데에 필요한 최소비용을 출력해라' 라는 문구를 보면 최소 스패닝 트리 문제라고 알 수 있다.
 

package src.Graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 네트워크연결_1922 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[] relationship = new int[N + 1];

        // 우선순위 큐: { 출발지, 목적지, 가중치(비교대상) }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[2], o2[2]);
            }
        });

        for(int i = 1; i <= M; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            priorityQueue.add(new int[] {from, to, weight});
        }

        // 모든 노드의 초기 부모를 자신으로 설정
        for(int i = 1; i <= N; i++){
            relationship[i] = i;
        }

        int result = 0;

        // Main
        while(!priorityQueue.isEmpty()){

            int[] node = priorityQueue.remove();

            int from = node[0];
            int to = node[1];
            int weight = node[2];

            // 부모가 같으면 넘기기
            if(relationship[from] == relationship[to]){
                continue;
            }

            int origin = relationship[to];
            int toChange = relationship[from];
            // 부모가 같지 않다면
            for(int i = 1; i <= N; i++){
                if(relationship[i] == origin) relationship[i] = toChange;
            }

            result += weight;
        }

        System.out.println(result);

    }
}