MST

트리

1. N개의 노드
2. N-1개의 간선
3. 모든 노드는 연결되어 있다.
4. 두 노드에 대해 경로가 하나만 존재한다.
5. 순환이 없다.
6. 방향성이 없다.

Spanning Tree (신장 트리)

모든 노드가 연결되어있는 트리

Minium Spanning Tree (최소 신장 트리)

모든 노드가 연결되어 있고, 간선의 가중치의 합이 최소인 트리

최단 경로는 아님! (다익스트라..등등)
MST를 사용하면 전체 비용이 최소가 되는 경우를 구할 수 있다.

크루스칼 알고리즘 (Kruskal's Algorithm)

Union Find를 활용
1. 간선을 기준으로 오름차순으로 정렬
2. 정렬된 간선에 대해 연결된 두 노드를 연결 (모든 간선에 대해 반복)
3. 두 노드가 다른 집합이면 Union 후 cost에 간선의 가중치를 더한다.

간선을 아래 클래스에 저장해보자

int E; // 간선
int V; // 노드
class Cable implements Comparable<Cable> {
    int start;
    int end;
    int cost;
    
    @Override
    public int compareTo(Cable o) {
    	return this.cost - this.o;
    }
}
Cable[] cableList = new Cable[E];

Kruskal

static int kruskal(int V, int E) {
    int cost = 0;
    int selected = 0;
    
    Arrays.sort(cableList);
    
    for(int i=0; i<E; i++){
    	if(find(cableList[i].start) != find(cableList[i].end)) {
            cost += cableList[i].cost;
            union(cableList[i].start, cableList[i].end);
            selected++;
        }
    }
    
    if(selected != V-1) {
    	return cost;
    }
    else
    	return -1; //연결불가한 노드가 있음
}

프림 알고리즘 (Prim's Algorithm)

크루스칼 보다 살짝 빠름