[자료구조] 크루스칼 vs 프림 알고리즘

3. 크루스칼 알고리즘 ( Kruskal's algorithm )

 

 크루스칼 알고리즘은 아래와 같은 '그리디'스러운 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다.

 

step 0) 모든 간선을 끊어 놓는다.

step 1) 가중치 순으로 간선들을 정렬한다. (오름차순)

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

step 3) 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.

              ( 1-2-3 처럼 간접적인 연결이어도 1,3 은 연결되어 있는 걸로 친다.)

 

 예시 그래프를 통해 알고리즘을 따라가 보겠습니다. 편의 상, 연결되지 않은 간선은 점선, 연결된 간선은 실선으로 표현하겠습니다.

 

 

 

step 0) 모든 간선을 끊어 놓는다.

step 1) 가중치 순으로 간선들을 정렬한다. (오름차순)

 

 위는 연결된 정점들, 아래는 가중치로 표현하면 아래와 같이 정렬됩니다.

 

step 2) 정렬된 간선을 순서대로 선택한다. ->  정점 = 2, 3, 가중치 = 2

 

step 3) 2, 3은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 2, 3, 가중치 = 2

 

 

step 2) 정렬된 간선을 순서대로 선택한다. ->  정점 = 4, 5, 가중치 = 3

 

step 3) 4, 5은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 4, 5, 가중치 = 3

 

 

step 2) 정렬된 간선을 순서대로 선택한다. ->  정점 = 1, 3, 가중치 = 4

 

step 3) 1, 3은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다.->  정점 = 1, 3, 가중치 = 4

 

 

step 2) 정렬된 간선을 순서대로 선택한다.  ->  정점 = 1, 2, 가중치 = 5

 

step 3) 1, 2은 연결되어 있다. (1-3-2)

 

step 2) 정렬된 간선을 순서대로 선택한다.  ->  정점 = 3, 4, 가중치 = 6

 

step 3) 3, 4은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 3, 4, 가중치 = 6

 

 

step 2) 정렬된 간선을 순서대로 선택한다.  ->  정점 = 2, 4, 가중치 = 7

 

step 3) 2, 4은 연결되어 있다.. (2-3-4)

 

step 2) 정렬된 간선을 순서대로 선택한다.->  정점 = 4, 6, 가중치 = 8

 

step 3) 4, 6은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 4, 6, 가중치 = 8

 

 

-> 모든 정점이 연결되었으므로 최소 스패닝 트리가 완성되었습니다.

 

 

 

4. 크루스칼 알고리즘의 구현

 

 이제 다음 알고리즘을 구현해보겠습니다.

 

step 0) 모든 간선을 끊어 놓는다.

step 1) 가중치 순으로 간선들을 정렬한다. (오름차순)

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

step 3) 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.

              ( 1-2-3 처럼 간접적인 연결이어도 1,3 은 연결되어 있는 걸로 친다.)

 

step 0) 모든 간선을 끊어 놓는다.

-> 미리 연결시켜 놓지 않기 때문에, step 0을 구현할 부분은 없습니다.

step 1) 가중치 순으로 간선들을 정렬한다. (오름차순)

-> 간선 정렬은 STL sort함수를 통해 할 수 있습니다. 시간복잡도는 O(E log E)가 됩니다.

 

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
const int N = 100005;
 
struct edge{
    int v1, v2, cost;
    bool operator < (const edge& e1) const{ return cost < e1.cost; }
};
vector<edge> e;
 
int main(){
    /*
    간선 입력 부분
    */
    sort(e.begin(),e.end());
    return 0;
}

 

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

 

//code by RiKang, weeklyps.com
int kruskal(int kn){
    sort(e.begin(),e.end());
    for(auto now: e){
        // now = e[0] ~ e[e.size()-1] 까지 순회합니다.
    }
    return ret;
}Colored by Color Scripter

step 3) 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.

 

 step 3에서 필요한 연결을 확인하는 작업과 연결하는 작업은 유니온 파인드로 관리하면 쉽게 할 수 있습니다. 크루스칼 알고리즘에선 정점의 연결만 있고, 끊는 건 없기 때문이지요.

 

연결을 확인하는 작업 : 두 정점이 같은 집합에 속하는 지로 판별합니다. (find)

연결하는 작업 : 유니온 파인드의 병합 연산으로 해결합니다. (union)

 

//code by RiKang, weeklyps.com
int kruskal(int kn){
    uf.init(kn+1);
    sort(e.begin(),e.end());
    int ret = 0;     // 간선 가중치의 합의 최솟값
    for(auto now: e){
        if(!uf.same_set(now.v1,now.v2)){ // 두 정점이 끊어져 있는가?
            ret+=now.cost;       // 가중치를 ret에 더함
            uf.merge(now.v1,now.v2); // 두 정점 연결
        }
    }
    return ret;
}

 

 유니온 파인드는 O(E log E) 보다 빠르므로 크루스칼의 최종 시간 복잡도는 O(E log E)가 됩니다. E <= V^2 임이 보장되는 평범한 그래프라면 O(E log V)라고 할 수 있습니다.

출처: https://www.weeklyps.com/entry/크루스칼-알고리즘-Kruskals-algorithm [weekly ps:티스토리]

 

 

2. 프림 알고리즘

 

 프림 알고리즘은 MST를 찾기 위한 그리디 패러다임의 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다.

 

step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. 

                (step 1에서 찾은 간선도 같이 T에 포함됩니다.)

step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

 

 이 알고리즘을 통해 만들어진 최후의 T는 MST가 됩니다. 아래의 그래프에 프림 알고리즘을 순서대로 적용 시켜 보겠습니다. 편의 상, T에 포함된 노드는 빨간색, T에 아직 포함되지 않은 노드는 파란색으로 표시하겠습니다.

 

 

step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

-> 초기 상태는 T에 아무것도 포함되어 있지 않습니다. 임의의 정점으로는 아무거나 선택해도 상관없지만, 예시에서는 1을 선택하겠습니다.

 

 

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 빨간색과 파란색을 연결하는 간선 중 가중치가 최소인 걸 찾으면 됩니다. 노드 1과 노드 3을 연결한 가중치 4의 간선이 최선입니다.

 

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 3을 T 에 포함시킵니다.

 

 

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 2과 노드 3을 연결한 가중치 2의 간선이 최선입니다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 2을 T 에 포함시킵니다.

 

 

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 3과 노드 4을 연결한 가중치 6의 간선이 최선입니다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 4을 T 에 포함시킵니다.

 

 

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 4과 노드 5을 연결한 가중치 3의 간선이 최선입니다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 5을 T 에 포함시킵니다.

 

 

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 4과 노드 6을 연결한 가중치 8의 간선이 최선입니다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 6을 T 에 포함시킵니다.

 

 

 이렇게 간선이 가중치의 합이 23인 트리가 완성되었으며, 이 트리가 그래프의 MST 입니다. 이러한 프림 알고리즘을 구현하는 데에는 2가지 방법이 있습니다.

 

 방법 1은 배열을 사용하여, T 와 각 노드를 연결하는 최소 간선 가중치를 찾는 방법이며 시간 복잡도는 O(V^2) 입니다.

 

 방법 2는 힙 ( min heap ) 을 사용해 최소의 간선 가중치를 찾는 방법이며, 시간 복잡도는 O(E log E), 즉, O(E log V) 입니다.

 

V = 정점의 개수, E = 간선의 개수

 

 

 

3. O(V^2) 알고리즘

 

 아래와 같은 두 배열을 잡으면 다익스트라와 비슷한 방식으로 프림 알고리즘을 구현할 수 있습니다.

 

dist [ i ] = T 에 들어간 노드와 i 노드 사이의 간선 가중치 중 최소값

( 결국, T와 i 노드를 연결할 때 사용할 간선의 가중치입니다.)

 

selected[ i ] = i 노드가 T에 들어가 있으면 true, 아니면 false

 

 이 두 배열을 통해 프림 알고리즘을 구현해보겠습니다.

 

step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

 

출처: https://www.weeklyps.com/entry/프림-알고리즘-Prims-algorithm [weekly ps:티스토리]