[알고리즘] 최소 신장 트리, MST(Minimum Spanning Tree), Prim, Kruskal

최소 신장 트리, MST (Minimum Spanning Tree)

개념

신장 트리(spanning tree): 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 최소 연결 부분 그래프.

최소 신장 트리(minimum spanning tree): 신장 트리 중 간선의 가중치 합이 가장 작은 트리

특징

• (n-1)개의 간선만을 사용하며 간선의 가중치 합이 최소여야 한다.
• 사이클이 없어야 한다. (사이클이 존재 == 한 곳으로 도달하는 경우가 두 개 이상 존재 != 최소한의 연결)
• 그리디 기법으로 최적의 해를 구할 수 있다.

 

관련 알고리즘

Kruskal's Algorithm

작동

1. 그래프의 모든 간선의 집합 E을 만든다.
2. E가 비어있지 않을 때까지 아래를 반복한다.
   1. E의 간선들 중 가중치가 최소인 간선을 지운다.
   2. 삭제된 간선이 가리키는 정점 x, y를 연결하여도 사이클이 발생하지 않는다면 연결한다.

그림 출처: https://www.javatpoint.com/kruskal-algorithm

위의 예제 그림으로 설명을 해보자면 다음과 같다.

일단 그래프를 구성하고 있는 모든 간선을 가중치의 오름차순으로 정렬한다.

Edge	AB	DE	BC	CD	AE	AC	AD
Weight	1	2	3	4	5	7	10

• 먼저 가장 가중치가 작은 AB 간선을 추가한다.
• 그 다음으로 가중치가 작은 DE 간선을 추가한다. (이때, DE 간선을 추가해서 사이클이 생긴다면 추가하지 않고 넘어간다.)

• STEP 2와 동일하게 BC, CD 간선을 각각 연결한다.

구현

private static void kruskal() {
	int[] parent;
    
    // parent 초기화
    for(int i=0; i<N; i++) {
        parent[i] = i;
    }
    
	// Edge의 weight 오름차 순으로 정렬
	PriorityQueue<Edge> edges;
    
    int N = edges.length;
    int cnt = 0;
	
    for(int i=0; i<N && cnt<N-1; i++) {
        ed = edges.poll();
        
        // 추가해서 사이클이 만들어지는가
        if(find(ed.v1) == find(ed.v2)) continue;
        
        // 안만들어지면 추가 (union find)
        union(ed);
        cnt++;
    }
}

private static void union(Edge ed) {
    int p1 = find(ed.v1);
    int p2 = find(ed.v2);
    parent[p1] = p2;
}

private static int find(int v) {
    if(parent[v] == v) return v;
    return parent[v] = find(parent[v]);
}

 

Prim's Algorithm

작동

1. 임의의 정점을 선택하여 하나의 정점을 갖는 최초의 트리(T)를 구성한다.
2. 트리(T)에 포함된 정점(t)과 트리에 포함되지 않은 정점(v) 간의 간선 중 가장 작은 가중치를 가지는 간선을 선택하여 v를 트리에 추가한다.
3. 모든 정점이 트리에 포함될 때 까지 2를 반복한다.

 

그림 출처: https://www.javatpoint.com/prims-algorithm-java

위의 예제 그림으로 설명을 해보자면 다음과 같다. (맨 처음 1번 노드를 트리 T에 포함시킨다.)

1. 1번에서 가장 가까운 6번 노드가 T에 속한 어떤 노드와 가장 적은 비용으로 연결할 수 있는지 확인한다. 여기서는 T에 속한 노드가 1 하나밖에 없기 때문에 1-6 간선으로 연결한다.
2. 다음 6번에서 가장 가까운 5번 노드를 추가하고자 할 때, T에 속한 1로는 연결할 수 없고 6번 노드와는 25로 연결할 수 있으므로 5-6 간선으로 연결한다.
3. 다음 5번에서 가장 가까운 4번 노드는 T에 속한 다른 1, 6번 노드와 연결하는 것보다 5번 노드와의 연결이 최소 이므로 4-5 간선으로 연결한다.
4. 다음 4번에서 가장 가까운 3번 노드는 T에 속한 다른 노드와 연결하는 것보다 4번 노드와의 연결이 최소 이므로 3-4 간선으로 연결한다.
5. 다음 3번에서 가장 가까운 2번 노드는 T에 속한 1번 노드와 연결하는 것보다 3번 노드와의 연결이 최소 이므로 2-3 간선으로 연결한다.
6. 다음 2번에서 가장 가까운 7번 노드는T에 속한 다른 4, 5번 노드와 연결하는 것보다 2번 노드와의 연결이 최소 이므로 2-7 간선으로 연결한다.

 

구현

private static void Prim(){
    // weight 저장된 인접 배열
    int[][] weight;
    
    // 노드가 트리에 연결되기까지의 최단 거리
    // 갈 수 없거나 이미 트리에 속한 경우: -1
    int[] distance = new int[N];

	// root(0번) 노드를 기준으로 distance 초기화
    for(i=1; i<N; i++) {
        distance[i] = weight[0][i];
    }
    
    // 트리에 다음으로 추가할, 가장 가까운 노드의 번호
    int near;
    
    for(int j=0; j<N-1; j++) {
        min = Integer.MAX_VALUE;
        
        // 트리에서 가장 가까운 노드(near)를 찾음
        for(int i=1; i<N; i++) {
        	// 트리에 속하지 않고 && 제일 가까움 -> near 갱신
            if(0<=distance[i] && distance[i]<min) {
                min = distance[i];
                near = i;
            }
        }

		// near를 트리에 추가
        distance[near] = -1;
        
        // near를 추가함으로써 트리와 더 가까워진 노드가 있으면 갱신
        // near와 연결된 노드만 보면 된다
        for(int i=1; i<N; i++) {
            if(weight[i][near] < distance[i]) {
                distance[i] = weight[i][near];
                nearest[i] = near;
            }
        }
    }
}