📌 MST란

• Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

  • Spanning Tree
    • 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
    • 그래프의 최소 연결 부분 그래프
    • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결
      

• Minimum Spanning Tree = 최소 신장 트리

• 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것

✅ MST의 특징

• 간선의 가중치의 합이 최소여야 한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.

✅ MST의 구현방법

✔ 크루스칼 알고리즘

위의 그래프를 살펴 보았을 때 노드는 6개이고, 간선의 갯수는 9개 입니다.

1. STEP(1) : 모든 간선들을 거리(비용,가중치)를 기준으로 오름차순으로 정렬한다.

2. STEP(2) : 정렬된 간선을 순서대로 선택한다.

3. STEP(3) : 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 두 정점을 연결시킨다.

▷즉 사이클 테이블을 통해 두 점이 연결되어 있는지 여부를 파악합니다. (Union-Find 알고리즘 이용한다)

▷최소비용 신장 트리에서는 사이클이 발생되면 안되기 때문입니다.

1. '거리(비용, 가중치)를 기준으로 먼저 오름차순 정렬'을 수행한후 가중치가 가장 낮은 3이였던 간선을 선택합니다. 두 노드를 연결해 줍니다.
   

2. 아래 그림처럼 가장 가중치가 낮은 두 번째 간선을 선택합니다.
   

3. 가장 가중치가 낮은 세 번째 간선을 선택합니다.
   

4. 가장 가중치가 낮은 네 번째 간선을 선택하면 안됩니다!!!! 사이클이 생기기 때문에입니다.
   그 이유로 가장 가중치가 낮은 다섯 번째 간선을 선택합니다. 사이클 테이블도 갱신해줍니다.
   (1과 2 모두 이미 사이클테이블에 포함되어있기 때문에 사이클이 생김)
   

5. 가장 가중치가 낮은 여섯 번째 간선을 선택합니다. 6개의 모든 노드가 연결되었기 때문에 이 후에 있는 간선들은 확인하지 않아도 됩니다. 모든 사이클 테이블의 모든 값이 1이 되면서 최소 비용 신장 트리가 만들어진 것을 볼 수 있습니다.
   

코드

import java.util.ArrayList;
import java.util.Collections;

class Edge implements Comparable<Edge> {
    int v1;
    int v2;
    int cost;
    Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge o) {
        if(this.cost < o.cost)
            return -1;
        else if(this.cost == o.cost)
            return 0;
        else
            return 1;
    }
}
public class Main {
    public static int[] parent;
    public static ArrayList<Edge> edgeList;
	
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y)
            parent[y] = x;
    }
	
    public static int find(int x) {
        if(parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    public static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return true;
        else return false;
    }
    public static void main(String[] args) {
        edgeList = new ArrayList<Edge>();
        edgeList.add(new Edge(1,4,4));
        edgeList.add(new Edge(1,2,6));
        edgeList.add(new Edge(2,3,5));
        edgeList.add(new Edge(2,4,3));
        edgeList.add(new Edge(2,5,7));
        edgeList.add(new Edge(2,6,8));
        edgeList.add(new Edge(3,6,8));
        edgeList.add(new Edge(4,5,9));
        edgeList.add(new Edge(5,6,11));
		
        parent = new int[7];
        for(int i = 1; i <= 6; i++) {
            parent[i] = i;
        }
		
        Collections.sort(edgeList);
		
        int sum = 0;
        for(int i = 0; i < edgeList.size(); i++) {
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.v1, edge.v2)) {
                sum += edge.cost;
                union(edge.v1, edge.v2);
            }
        }
		
        System.out.println(sum);
    }	
}

MST를 나타내는 알고리즘
크루스칼, 프림
노드가 많으면 크루스칼이 효율적
간선이 많으면 프림이 효율적

🧩 Reference

• https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
• https://brenden.tistory.com/36