Minimum Spanning Tree

MTS

MTS, 최소신장트리, 최소스패닝트리

 최소신장트리는 이름에서 알 수 있듯이 트리와 관련되어있다. 정확히 따지자면 그래프에서 특정 트리를 찾아내는 것이다. 주어진 그래프에서 모든 노드를 포함하는 가중치가 최소(또는 최대)가 되는 트리를 찾는 것이다. 왜 신장이라는 단어가 들어가는 지는 잘 모르겠지만, 모든 노드를 포함하는 중복되는 간선이 없음을 뜻하는 것일 듯 하다. 즉 간선의 수는 무조건 노드의 수보다 하나 작아야 한다는 것이다. 또 다른 조건은 앞에서 설명했던 내용에서 유추할 수 있듯이 사이클이 발생해서는 안된다는 것이다.

트리, 그래프에서 대해서 모른다면 다른 곳에서 찾아보고 오자.

Kruskal & Prim

 최소신장트리를 구하는 알고리즘은 Prim과 Kruskal알고리즘이 있다. 포인트는 Kruskal은 간선을 선택하는 것이고 Prim은 노드를 선택하는 것이다.

Kruskal

 Kruskal의 경우 모든 간선을 우선순위(최대 혹은 최소)로 정렬한 다음에, 하나씩 꺼내어 조건에 맞는지 확인한다. 만약 선택한 간선의 양쪽 노드들이 이미 연결되어 있던 노드들이라면 사이클이 발생하게 된다. 이럴경우 그 간선은 무시하면 된다. 아래와 같은 그래프가 있다.

먼저 간선의 가중치를 우선순위로 정렬을 한다면 2 3 4 5 6 7 8 8 이 된다. 가중치가 2인 노드 2,3을 연결한 간선을 선택한다. 다음으로 3의 가중치를 가지고 있는 간선을 선택한다. 다음으로 4의 간선을 선택하게 되고 아직까진 사이클이 발생하지 않는다. 다음 가중치의 5의 간선을 보게 되면 이를 선택할 경우 사이클이 발생하기 때문에 이를 선택해서는 안된다.

같은 방법으로 모든 노드들을 포함할 수 있는 트리를 만들게 되면 된다. 결과적으로 아래와 같은 트리가 완성된다.

Union & Find

 크루스칼 알고리즘을 코드로 작성하기위해서는 매턴 간선을 선택했을 때, 선택된 간선이 사이클을 만드는지를 확인해 주어야한다. 이때 사이클을 확인하는 방법중 Union find이라는 기법이 있다. 두 서로소 집함을 찾을 때 사용된는 기법이다.

 연결된 노드를 트리 형식으로 표현하는 방법이다.

 각 노드별로 부모를 가리키는 변수가 필요하다. 일반적으로 parent 배열이다 root 배열로 표현한다.

public class Unionfind {/

    static int[] parent;

    public Unionfind(int a) {
        parent = new int[a];
    }

    public static int find(int x){
        if(parent[x]==x){
            return x;
        }

        return find(parent[x]);// 이렇게 하면 리턴하면서 parent를 한번에 update 할 수 있다.
    }

    public static void union(int x, int y){
        int a = find(x);
        int b = find(y);

        if( a==b ) return;

        parent[b] = a;
    }
}

먼저 모든 노드들은 자기 자신을 루트로 하는 그래프라고 생각한다.

두 그래프가 같은 그룹에 속하는 지를 확인하기 위해 각 노드의 루트를 찾는 것이다.

만약 두 노드의 루트가 같다면 이미 같은 그룹에 속한 것이고 다르다면 다른 그룹에 속한것이다.

크루스칼 알고리즘에서는 엣지에 있는 양 노드들의 루트를 비교하여 루트가 같다면 이미 연결되어 있는 것이다.

먼저 각 노드의 루트 혹은 혹은 부모 노드를 나타내는 배열을 자기 자신으로 초기화 한다.

find 함수를 보면 각 노드의 부모를 찾아 자기 자신과 같으면 루트이다.

배열의 값이 자신과 다르다면 재귀로 부모노드를 확인해가며 루트노드를 찾아낸다.

union 함수에서 두개의 노드의 루트노드를 찾아 같다면 이미 연결된 노드들이며 다르다면, 한쪽 루트에 다른쪽 루트를 자식으로 삼아 하나의 루트로 만든다.

크루스칼 알고리즘에서는 유니온 파인드 기법을 통해서 엣지가 추가될따 사이클이 형성되는 지를 알 수 있다.

find와 union을 하면서 간단한 방법으로 성능을 향상 시킬수 있다.

먼저 find 함수에서 루트를 구할때

return parent[x] = find(parent[x])라 변경하면, 각 노드의 부모노드가 아닌 루트가 재귀를 부를때 업데이트 된다.

union 함수에서 두 트르의 깊이 값을 가지고 있다면, 더 높은 트리에 더 낮은 트리를 붙인다면, 높이가 증가 하지 않을 수 있다.

(높이가 증가하지 않는다는 것은 탐색을 할때 속도가 더 빠르다는 것이다)

http://isukorea.com/blog/home/waylight3/215

Prim

 Prim 알고리즘은 kruskal과는 달리 하나의 노드에서 시작하여 다른 노드를 선택하는 방식입니다. 출발 노드를 선택하여 그노드에서 가장 가중치가 적은 엣지를 선택하여 다음 노드를 선택합니다. 이제드 두 노드에서 갈수 있는 모든 엣지를 살펴보면서 그중 가장 가중치가 낮은 엣지를 선택하여 다음 노드로 넘어가는 방식 입니다.