[알고리즘] 최소 신장 트리 || 최소 스피닝 트리 (MST)

최소 스패닝 트리 ( Mininum Spanning Tree, MST )

• 가중치가 할당된 연결 그래프에서 모든 정점을 최소한의 비용으로 연결하는 부분 그래프임

  

  요런 식으로 구성된 그래프구조이다.

  특징

  1. 스패닝 트리
     1. 그래프의 모든 정점을 포함하는 트리
        1. 그래프의 모든 정점이 연결되어 있으며, 사이클이 없음
  2. 최소 비용
     1. 간선들의 가중치 합이 최소인 트리
  3. 연결 그래프
     1. 그래프의 모든 정점이 서로 연결되어 있어야 한다.
        1. 어떤 정점에서 다른 모든 정점으로 가는 경로가 존재한다.

  대표 알고리즘

  1. 크루스칼 알고리즘
  2. 프림 알고리즘

  사용처

  • 여러 도시를 도로로 연결시 가능한 가장 적은 비용으로 모든 도시를 연결하고자 하는 경우 최소 스패닝 트리가 이용됨
  • 물류 네트워크의 최적화에 사용한다고 보면됨.

크루스칼과 유니온 파인드를 사용한 문제 풀이

흐름

1. 간선 리스트 준비
   1. 모든 간선 리스트 추가
   2. 가중치 기준으로 오름차순

2. 유니온 파인드 초기화
   1. 각 정점 부모를 자기 자신으로 초기화

3. 간선의 선택
   1. 정렬된 간선에서 순서대로 간선 선택

4. 사이클 검사
   1. 유니온-파인드를 사용해 선택한 간선이 사이클 형성 여부 파악

5. 트리의 구성
   1. 사이클 형성하지 않는 간선만을 선택해 트리를 구성함

6. 최소 가중치 계산
   1. 선택된 간선들의 가중치 합을 계산한다.

전체 코드

package org.example.알고리즘.최소스패닝트리;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] parent;
    
    public static void main(String[] args) {
        try (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());
            
            List<Edge> edges = new ArrayList<>();
            
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int src = Integer.parseInt(st.nextToken());//출발 정점
                int dest = Integer.parseInt(st.nextToken()); //도착 정점
                int weight = Integer.parseInt(st.nextToken());//가중치
                Edge edge = new Edge(src, dest, weight);
                edges.add(edge);
            }
            
            Collections.sort(edges); // 가중치 오름차순으로 정렬한다.
            
            // 유니온 파인드 초기화 단계 - 정점 개수만큼 초기화 수행
            // 각 정점의 부모를 자기 자신으로 초기화해야한다.
            /*
						1   2   3   4   5
	          |   |   |   |   |
            1   2   3   4   5 */
            parent = new int[V + 1];
            
            for (int i = 1; i <= V; i++) {
                parent[i] = i;
            }
            
            System.out.println("parent = " + Arrays.toString(parent));
            
            int mstWeight = 0;
            
            for (Edge edge : edges) {
                if (find(edge.src) != find(edge.dest)) {
                    union(edge.src, edge.dest);
                    mstWeight += edge.weight;
                }
            }
            
            System.out.println(mstWeight);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    /**
     * 유니온 파인드 알고리즘
     * 주어진 정점의 루트 정점을 찾는다.
     *
     * @param x
     * @return
     */
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    
    /**
     * 두 정점을 연결한다. - 두 원소가 속한 집합을 합친다.
     * 한 집합의 대표 원소를 다른 집합의 대표 원소에 연결해 두 집합을 합친다.
     */
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        
        if (x != y) {
            parent[y] = x;
        }
    }
    
    public static class Edge implements Comparable<Edge> {
        int src;
        int dest;
        int weight;
        
        public 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;
        }
    }
}

간선 리스트 준비

List<Edge> edges = new ArrayList<>();
  
for (int i = 0; i < E; i++) {
	  st = new StringTokenizer(br.readLine());
	  int src = Integer.parseInt(st.nextToken());//출발 정점
	  int dest = Integer.parseInt(st.nextToken()); //도착 정점
	  int weight = Integer.parseInt(st.nextToken());//가중치
	  Edge edge = new Edge(src, dest, weight);
	  edges.add(edge);
}

Collections.sort(edges); // 가중치 오름차순으로 정렬한다.

• Edge 객체에 시작점, 종작점, 가중치 필드를 담아서 List 형태로 가지고 있는다.
  • 스피닝의 최소 가중치를 구해야하기에, 오름차순으로 리스트를 정렬한다.

    자세하게 설명하면..

    • 여러 도시들의 도로를 연결하는 경우에 비싼 도로부터 설치하게되면, 싼 도로를 건설할 기회를 잃어버릴 수 있다.
    • 그렇기에 크루스칼 알고리즘에서 같은 원리가 적용되는 것이다.
    • 간선 리스트를 오름차순으로 정리하면, 가장 가중치가 낮은 간선부터 순서대로 처리가 가능해진다.

유니온 파인드 초기화

parent = new int[V + 1];

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

• 각 정점의 부모를 자기 자신으로 초기화를 수행한다.

• 왜냐
  • 일단 이미 간선 리스트가 가중치순으로 오름차순으로 설정되어 있기 때문이다.
  • 가중치가 얼마고하는건 사실 단순 비교상에선 불필요하긴하다.

간선의 선택

for (Edge edge : edges) {
  //사이클 검사 및 대표 원소 검사 + 두 원소가 속한 집합을 하나로 합치는 연산
}

• 순차적으로 작은 가중치 ~ 높은 가중치 순으로 순회

사이클의 검사 및 집합화

/**
 * 유니온 파인드 알고리즘
 * 주어진 정점의 루트 정점을 찾는다.
 *
 * @param x
 */
public static int find(int x) {
    if (x == parent[x]) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

/**
 * 두 정점을 연결한다. - 두 원소가 속한 집합을 합친다.
 * 한 집합의 대표 원소를 다른 집합의 대표 원소에 연결해 두 집합을 합친다.
 */
public static void union(int x, int y) {
    x = find(x);
    y = find(y);
    
    if (x != y) {
        parent[y] = x;
    }
}

--
실행부

for (Edge edge : edges) {
    if (find(edge.src) != find(edge.dest)) {
        union(edge.src, edge.dest);
        mstWeight += edge.weight; // 현재 edge 의 집합설정 후 가중치를 더해준다.
    }
}

1. 각 간선 루트의 가중치가 출발과 도착지가 다르면
   1. 사이클이 검사를 통과하지 못한 것입니다.
   2. 사이클이 형성되는 순간, 이미 최소 신장 트리 ( 최소 스피닝 트리 ) MST 의 조건에 부합하지 않게 됨.
   3. 이후 Union 을 수행하여
      1. 서로 다른 집합에 속해 있는지 체크한 후, 서로 다른 집합에 속해 있는 경우 두 집합을 합치는 역할을 수행합니다.

Uploaded by N2T