[알고리즘] 최소비용신장트리(Minimum Spanning Tree) - 3

최소비용신장트리(Minimum Spanning Tree) - 3

저번 시간에 이어 크루스칼의 알고리즘을 계속 진행한다.

크루스칼의 알고리즘을 위해서는 원소 u가 속해있는 집합이 무엇인지 찾을수 있어야하고(Find) 

2개의 집합을 하나로 합치는 연산(Union)을 지원해야한다. 이를 Union Find Problem이라고 한다.

결론을 이야기하면 Union Find Problem을 해결하기 위해, 각각의 집합을 하나의 트리로 표현해야한다.

이 때, 이러한 트리에 규칙이 없다. 이진 트리도 아니고 자식이나 부모에 대한 규제도 없다.

대신 해당 집합의 모든 원소들이 트리의 노드로 들어가야한다는 것이다.

또한 일반 트리가 밑으로 내려가는 것과 달리, 여기서는 루트 노드까지 올라가는 연산, 즉 상향식 트리이다.

이것의 의미는 트리의 각 노드가 자기 자식 노드의 주소를 가질 필요가 없고, 

자신의 부모가 누구인지에 대한 정보만 가지면 된다.

이것은 꽤 중요한 정보인데, 유일한 부모 노드의 정보만 가지기 때문에 복잡성을 낮출수 있게된다.

정리하자면 서로소인 집합을 표현하기위해서 상향식 트리로 표현한다는 것이다.

또한 모든 노드는 부모를 가지고 있어야하므로 어떤 노드의 부모가 자기 자신일때 루트 노드이다.

이를 통해서 알고리즘을 좀더 간단하게 만들 수 있다.

예를 들어서 위의 그림은 크루스칼의 알고리즘이 진행되는 시점인데,

현재까지 선택된 엣지들이 파란색 선이라면 4개의 집합이 존재한다.

실제 프로그램 안에서는 4개의 집합을 각각 1개씩의 트리로 표현하므로 총 4개의 트리로 존재하게 된다.

이렇게 상향식 트리로 만들어진 경우 모든 트리를 하나의 배열로 표현할 수있다.

이것이 크루스칼의 알고리즘을 상향식 트리로 만드는 가장 큰 이유이다.

여기서 배열의 인덱스는 노드를 의미하며, 인덱스 내부의 변수값은 부모를 나타낸다.

실제 프로그램안에서는 a,b,c보다 숫자로 표현되게 될것이다.

이렇게 표현 할 수있는 방법은 부모가 유일하기 때문이다.

반대로 생각해서 자식을 표현하게되는 경우 자식은 여러개이므로 복잡하게 표현이 된다.

Find-Set(x){
    if(x!=p[x]){
        then p[x]<-Find-Set(p[x])                                                                         
    }
    return p[x]
}

본격적으로 크루스칼 알고리즘에서 사용되는 코드들을 알아보자.

앞서 설명한 슈도 코드에서 사용되는것은 Find와 Union 이었다.

이중 Find는 어떤 두 노드가 같은 집합에 포함되는지를 알아보는 연산이었다.

이를 위해 두 노드의 루트 노드가 동일하면 같은 집합에 있다고 판단한다.

따라서 find의 결과는 루트 노드의 이름을 리턴해주게 된다.

위의 코드는 Find-Set를 재귀로 구현한 코드이다.

이 find-set의 시간 복잡도를 생각해보면, 트리의 아래에서 부터 루트노드까지 찾아올라가므로

O(h)의 시간복잡도를 가지며 여기서 h는 트리는 높이 이다.

만약 트리를 잘못 만들면 모든 노드들이 1열로 줄서 있으므로 최악의 경우 시간 복잡도는 O(n)이 된다.

두번째는 Union인데 두개의 집합을 합집합으로 만드는 연산이다.

예를 들어 위 그림에서 c가 루트인 트리와 f가 루트인 2개의 트리를 하나로 합치는 것이다.

이를 위해 가장 간단한 방법은, 어느 한쪽 트리가 다른쪽 트리의 자식 트리가 되는 것이다.

따라서 Union을 하는데 걸리는 시간은 루트를 찾아야하므로 find연산과 동일하고,

루트 노드를 찾은 이후에는 둘중의 한명을 다른쪽의 자식으로 넣어주면 되므로 O(1)이다

위의 Union의 알고리즘은 아무생각없이 간단하게 짠 알고리즘이다.

그러나 트리의 높이에 비례해서 복잡도가 증가하므로 가능한한 트리의 높이를 낮춰야한다.

따라서 weighted union으로 합집합을 만드면 복잡도를 낮게 할수 있다.

weighted union의 원리는 간단하다.

트리의 높이를 가능한 낮게 유지한다는 원리에서 작은 트리를 큰 트리의 자식으로 놓는 것이다.

이렇게 되면 전체 트리의 높이가 증가하지 않게 된다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘