[알고리즘] 최소 신장 트리 - Java

최소 신장 트리
그래프에서 모든 노드를 연결할 때 사용된 Edge들의 가중치의 합을 최소로 하는 트리이다.

 

특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있을 때 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다.

 

핵심 이론

모든 Edge들을 '가중치'를 기준으로 오름차순 정렬 후, 가중치가 낮은 Edge부터 연결한다. 이때 사이클이 형성되지 않을 때만 연결한다.

 

1. Edge 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기

그래프를 Edge 중심 형태로 Edge 리스트로 저장한다. edge class는 시작 노드, 끝 노드, 가중치로 구성된다. 사이클 여부를 확인하기 위해 유니온 파인드 배열(parent)를 인덱스의 값으로 초기화한다.

 

2. 그래프 데이터를 가중치 기준으로 정렬하기

Edge 리스트를 가중치 기준으로 오름차순 정렬한다.

 

3. 가중치가 낮은 Edge부터 연결 시도한다.

가중치가 낮은 Edge부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 Edge를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union연산을 시행한다.

 

4. 과정 3 반복

연결한 Edge의 개수가 N-1이 될 때까지 과정 3을 반복한다.

 

 

풀어본 문제

백준의 최소 스페닝 트리문제이다. 최소 신장 트리(MST) 알고리즘을 사용하여 풀 수 있다.

1197번: 최소 스패닝 트리

 

 

구현 코드

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


public class Main {
    static BufferedWriter bw;
    static BufferedReader br;
    static ArrayList<Edge> edges;
    static int [] parent ;

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 정점의 개수
        int V = Integer.parseInt(st.nextToken());
        // 간선의 개수
        int E = Integer.parseInt(st.nextToken());

		// 우선순위 큐로 구현
        PriorityQueue<Edge> edges = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });

		// Edge 리스트 생성
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            edges.add(new Edge(start, end, weight));
        }

        // 유니온 파인트 배열
        parent = new int[V+1];
        for(int i=0; i<parent.length; i++){
            parent[i] = i;
        }
        bw.write(MST(edges, V)+"");

        bw.flush();
        br.close();
        bw.close();

    }
    
	  public static int MST(PriorityQueue<Edge> edges, int N){
        int count = 0;
        int result = 0;

        while(count < N-1){
            Edge cur = edges.poll();
            int a = find(cur.start);
            int b = find(cur.end);
           
            if(a != b){  // 같은 부모가 아니라면 연결해도 사이클이 안생김
                // union 연산
                parent[b] = a;
                result += cur.weight;
       			// 간선을 추가할 때만 count를 1 증가시킴
                count++;
            }

        }
        return result;
    }

    public static int find(int a){
        if(parent[a] == a)
            return a;

        a = find(parent[a]);
        return a;
    }

  
}
class Edge{
    int start;
    int end;
    int weight;

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