최소 스패닝 트리

최소 스패닝 트리의 정의

Kruskal의 알고리즘

Kruskal의 알고리즘 분석

Prim의 알고리즘

Prim의 알고리즘 분석

최소 스패닝 트리의 정의

연결된 그래프 [eqn: G(V,E)]의 스패닝 트리란 [eqn: G]의 부그래프로써 [eqn: G]의 모든 정점을 포함하는 트리를 말한다. 여기서 트리란 물론 사이클이 없고 연결된 그래프를 말한다.

에지에 가중치가 주어진 그래프 [eqn: G]에서 [eqn: G]의 스패닝 트리중에 트리에 속한 에지의 가중치 합이 최소가 되는 스패닝 트리를 최소 스패닝 트리라고 한다. 이 문제의 응용으로는 비용이 최소인 통신 네트워크의 설계 등에처 찾을 수 있다.

여기서는 Kruskal의 알고리즘과 Prim의 알고리즘을 소개한다. 두 알고리즘 모두 소위 욕심장이 방식(Greedy Method)으로 설계되었다. 욕심작이 방식이란 각 단계에서 나름의 기준으로 최상의 결정을 하며, 그 후에도 한번 내린 결정을 번복하지 않는 방식을 발한다.

Kruskal의 알고리즘

Kruskal의 알고리즘은 에지를 하나씩 추가하는 방식으로 최소 스패닝 트리를 만들어 간다. 에지의 가중치가 증가하지 않는 순서로 에지의 추가 여부를 결정하는데, 에지를 추가하였을 때 사이클을 형성하지 않으면 추가한다.

Kruskal의 알고리즘 분석

Kruskal 알고리즘이 옳음을 증명하여 보시오. 연결된 그래프에 대해서 항상 스패닝 트리를 찾을 수 있으며, 찾은 스패닝 트리는 항상 최소 스패닝 트리임을 보이면 된다.

Kruskal 알고리즘을 어떻게 구현할지를 생각하여 보자. 우선 가중치가 작은 에지부터 차례로 선택할 수 있어야 한다. 이를 위하여 에지를 가중치로 미리 정렬할 수도 있으나, 앞에서 최소 힙을 이용할 수 있다. 미리 에지의 가중치로 최소 힙을 만들고, 다음 에지가 필요할 때마다 최소 힙의 루트에 있는 에지를 제거하여 사용하면 된다. 최소 힙을 구성하는데 [eqn: O(m)] 시간, 에지를 제거할 때 마다 [eqn: O(log m)] 시간이 소요된다.

선택된 에지 [eqn: e =(v,w)]에 대해서 [eqn: e]가 추가되었을 때 사이클을 이루는지 아닌지는 [eqn: v]가 속한 연결 요소와 [eqn: w]가 속한 연결 요소가 같으냐 다르냐를 묻는 것과 같으므로 UNION-FIND 연산을 이용한다. 이 때 각 연결 요소의 정점을 서로소인 집합으로 표현한다. 그러면 [eqn: v]와 [eqn: w]가 같은 집합에 속해있는지 아닌지를 알면 된다. UNION은 최대 [eqn: n-1]회, FIND는 최대 [eqn: 2m]회가 수행된다.

대부분의 경우는 에지의 수 [eqn: m]이 정점의 수 [eqn: n]보다 크거나 같겠지만, [eqn: m < n-1]인 경우에는 최소 스패닝 트리가 존재하지 않는다고 결과를 출력해야 한다. 따라서 전체 시간 복잡도는 [eqn: O((n+m) log m)]이 된다.

Prim의 알고리즘

Prim의 알고리즘은 그래프 [eqn: G]의 한 정점을 선택하여 시작한다. 각 반복 과정마다 그 때까지 구성된 최소 스패닝 트리의 부분에 새로운 정점과 에지를 선택하여 추가한다. Prim의 알고리즘은 항상 트리에 속한 정점과 인접한 정점 사이의 에지 중 최소의 가중치를 갖는 에지를 선택한다.

Prim의 알고리즘 분석

Prim의 알고리즘이 옳게 동작함을 증명하시오.

Prim의 알고리즘에서 다음 단계의 에지를 선택하기 위해서 트리에 속하지 않은 모든 정점[eqn: v][eqn: v]에 대해서 트리 정점에 인접한 정점 중에 에지의 가중치가 최소인 값과 해당 정점을 보관하고 있으면 된다.

어떤 정점 [eqn: v]가 선택되었다면, [eqn: v]에 인접하면서 트리에 속한 정점이 아닌 것에 대해서 해당 정보를 수정한다.

따라서 전체 시간 복잡도는 [eqn: O(n)] 시간에 다음 정점을 선택할 수 있고, 선택된 정점에 대해서 역시 같은 시간에 정보를 update할 수 있다. 따라서 전제 시간 복잡도는 [eqn: O(n^2 )]이다.

Kruskal의 알고리즘과 Prim의 알고리즘을 비교하면, 에지의 수가 작으면 Kruskal의 알고리즘이 빠르고 에지의 수가 많으면 Prim의 알고리즘이 더 효율적이라고 말할 수 있다.

그래프의 에지에 가중치가 음수로 주어지더라도 앞의 두 알고리즘이 잘 동작하는가? 그리고 최대 스패닝 트리는 어떻게 구할 수 있을까?