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

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

이번 포스팅에서는 전에 언급했던 2가지 알고리즘 중에서 

크루스칼의 알고리즘을 살펴 보도록 하자

크루스칼 알고리즘의 순서는 다음과 같다.

1. 엣지들을 가중치의 순서대로 정렬한다.

2. 엣지들을 그 순서대로 하나씩 선택해간다. 

단, 이미 선택한 엣지들과 사이클(Cycle)을 형성하면 선택하지 않는다.

3. n-1개의 엣지가 선택되면 종료한다.

앞서 말한 순서대로 MST를 구성한다고 했을 때,

위의 그림을 예로 들면, a에서 가중치가 가장 작은 것을 선택하고, 

b에서는 그 다음 작은 것을 선택한다. 같은값이 있는 경우 아무거나 선택한다.

c, d, e도 마찬가지로 가중치가 작은 순서대로 선택하게 된다.

f 에서 다음 순서는 6이 되지만 이 엣지를 선택하면 사이클이 형성되므로

이 엣지를 포기하고 다음으로 넘어간다.

따라서 g에서 가중치가 7인 엣지를 선택한다.

위와 같은 연산이 계속 반복되며,

n-1개의 엣지가 선택되면 MST가 되며 알고리즘을 종료하게 된다.

그림으로 볼때 논리적으로 간단한 알고리즘이지만, 코드로 구현 하기는 쉽지 않다.

왜 이렇게 선택한 엣지들이 MST가 되는 것일까?

A를 현재까지 알고리즘이 선택한 엣지들이라고 하고, A를 포함하는 MST가 존재한다고 가정하자.

A가 공집합에서 시작했으므로 임의의 스텝에서 A를 포함하는 MST가 존재할 때, 

크루스칼 알고리즘이 선택한 엣지가 이 A에 대해서 안전하다라는 것을 보이게 되면 증명이 되는 것이다.

 그렇게 만들어지는 엣지를 추가한 A도 MST의 일부이고 일관성이 유지되기 때문이다.

위의 그림은 (u, v)가 사이클을 만들지 않는 가장 가중치가 작은 엣지라고 할 때,

u와 v는 빨간 엣지들에 의해서 연결되지 않은 상태 이다.

그렇기 때문에 v에 인접한 노드들을 한쪽집합 S라고 하고 나머지 정점들을 V-S라고 할 때

이 두 컷을 Cross하는 어떤 엣지도 사이클을 만들지 않는다.

왜냐하면 한쪽은 S에 속해있고 한쪽은 V-S에 속해있으므로 연결 되어 있지않은 엣지이며,

따라서 엣지를 추가 하더라도 사이클을 만들지 않는다.

이러한 엣지들 중에서 가중치가 최소인 엣지 이므로 앞선 포스팅에서 정리된 증명과 일치한다.

그렇다면 사이클 검사는 어떤식으로 검증 되는 것일까

일반적으로 크루스칼 알고리즘에서 사이클이 만들어지는지 검사하기위해서

모든 노드들을 집합으로 표현한다.

다시 말하자면, 이미 연결되어있는 노드들을 하나의 집합으로 표현한다.

위의 그림은 어떠한 노드도 연결되어 있지 않으므로 각각의 노드가 개별적인 집합으로써 존재한다.

첫번째로 선택하는것은 h와 g인데, 서로 다른 집합에 존재하므로 사이클을 만들지 않는다고 판단한다.

이 후에 엣지를 선택하고 합집합을 만든다.

엣지를 선택할 때마다 같은 집합에 있는지 확인하고 합집합을 만드는 연산을 수행한다.

이와같이 알고리즘을 진행하다가 동일한 집합에 속해 있는 요소들을 찾는 경우

해당 엣지를 버리게 된다.

마지막은로 n-1개의 엣지가 선택되면 크루스칼 알고리즘을 존재한다.

알고리즘을 종료 했을때 모든 노드들이 한 집합 안에 들어가 있는 것을 확인할 수 있다.

슈도 코드로 다음과 같이 표현이 가능하다.

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