신장 트리(Minimum Spanning Tree)란, 주어진 그래프에서, 서브 그래프지만 그래프의 모든 정점을 포함하고, 각 정점들은 모두 경로를 가지고 있어야 하지만 모든 경로를 포함하고 있지는 않은 그래프를 말한다.따라서, 신장 트리는 유일하지 않을 수도 있다. 최소 신장 트리란, 이들 경로에 가중치가 주어졌을 때, 경로의 가중치의 합이 가장 작은 트리를 말한다. (트리와 그래프의 차이는, 트리는 사이클이 존재할 수 없으며 그래프는 사이클이 존재할 수 있다는 점이다)
예를 들어, 전자 회로를 설계할 때, 요소 몇 개의 핀을 전선으로 연결해 전기적으로 동등하게 만들어야 하는 경우가 있다. n개의 핀을 서로 연결하기 위해, n - 1개의 전선을 사용할 수 있는데, 여기서 하나의 전선이 2개의 핀을 연결한다. 일반적으로, 전선을 배치하는 모든 방법 중에서, 전선을 가장 적게 사용하는 방법을 원한다.
이 전선을 연결하는 문제는, 무방향 그래프 G = (V, E)로 모델링할 수 있다. 이때 V는 핀의 집합, E는 연결 가능한 핀 쌍의 조합이고, 각 간선(u, v) ∈ E마다 u와 v를 연결하는 비용(필요한 전선의 양)을 나타내는 가중이 w(u, v)가 있다. 그리고 나서, 모든 정점을 연결하는, 전체 가중치의 합
w(T) = Σw(u, v)
를 최소화시키는 비순한 부분 집합 T ⊆ E를 찾는다. T는 비순환이고 모든 정점이 모두 연결되어 있기 때문에, 트리가 형성될 것이며, 이 트리는 그래프 G에서 늘어나기 때문에 신장 트리라고 부른다. 트리 T를 결정하는 이 문제를 최소 신장 트리 문제라고 부른다.
최소 신장 트리 문제를 해결하는 대표적인 두 개의 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 있다. 두 알고리즘은 그리디(Greedy) 알고리즘이다. 알고리즘의 각 단계에서 가능한 몇 가지 선택 중 한 가지를 선택해야 한다. 그리디 방법에서는, 그 순간에서 가장 좋은 것을 선택한다. 이러한 방법은 일반적으로 최적해를 찾는 것을 보장해주지 못한다. 하지만, 최소 신장 트리 문제에 대해서 특정한 그리디 방법을 사용하면 최소 가중치의 신장 트리를 얻을 수 있다는 것을 증명할 수 있다. 크루스칼이 제시한 알고리즘은 연결 요소(connected component) 알고리즘과 유사하며, 프림이 제시한 알고리즘은 Dijkstra의 최소 경로 알고리즘과 유사하다.
크루스칼 알고리즘은 다음과 같다,
1. 집합 A를 공집합으로 초기화한다.
2. 주어진 그래프의 각각의 정점들에 대해서 n(V)만큼의, 단일 정점을 가지는 트리는 생성한다.
3. 주어진 그래프의 간선 E를 가중치에 따라 정렬한다. 오름차순이어야 한다.
4. 각각의 간선(u, v)에 대해서, FindSet(u)의 결과와 FindSet(v)의 결과가 다르면, (u, v)를 A에 추가하고, u, v 정점을 가지는 트리를 서로 합치는 Union(u, v) 프로시저를 호출한다.
여기서, FindSet(u)이 어떤 것을 리턴하는가가 모호한데, 이것은 정점 u를 포함하는 그래프의 대표 원소라면 상관없다. 즉, 정점 u를 포함하는 그래프의 가장 처음 시작 원소를 대표 원소라고 해도 상관없다.
프림 알고리즘을 간략히 설명하면 다음과 같다.
1. 완료된 그래프의 집합과 fringe라 불리는, 후보군의 집합을 만든다.
2. 루트에서부터 시작하여, 이 정점이 가질 수 있는 모든 경로를 보고, 최소의 가중치를 가지는 경로를 선택하여 완료된 그래프 집합에 추가한다.
3. 추가하는 과정에서, 이미 그래프 집합에 있는 정점과, 후보군에 있는 정점과 중복된 경로가 존재할 수 있는데, 이 경우 더 적은 가중치를 가지는 경로를 남긴다.
4. 후보군의 집합이 공집합이 될 때까지 2, 3 과정을 반복적으로 수행한다.
프림 알고리즘은, 각각의 단계마다 최소의 가중치를 가지는 경로를 선택한다는 점에서, Dijkstra 최소 경로 찾기 알고리즘과 비슷하다.
예를 들어, 전자 회로를 설계할 때, 요소 몇 개의 핀을 전선으로 연결해 전기적으로 동등하게 만들어야 하는 경우가 있다. n개의 핀을 서로 연결하기 위해, n - 1개의 전선을 사용할 수 있는데, 여기서 하나의 전선이 2개의 핀을 연결한다. 일반적으로, 전선을 배치하는 모든 방법 중에서, 전선을 가장 적게 사용하는 방법을 원한다.
이 전선을 연결하는 문제는, 무방향 그래프 G = (V, E)로 모델링할 수 있다. 이때 V는 핀의 집합, E는 연결 가능한 핀 쌍의 조합이고, 각 간선(u, v) ∈ E마다 u와 v를 연결하는 비용(필요한 전선의 양)을 나타내는 가중이 w(u, v)가 있다. 그리고 나서, 모든 정점을 연결하는, 전체 가중치의 합
w(T) = Σw(u, v)
를 최소화시키는 비순한 부분 집합 T ⊆ E를 찾는다. T는 비순환이고 모든 정점이 모두 연결되어 있기 때문에, 트리가 형성될 것이며, 이 트리는 그래프 G에서 늘어나기 때문에 신장 트리라고 부른다. 트리 T를 결정하는 이 문제를 최소 신장 트리 문제라고 부른다.
최소 신장 트리 문제를 해결하는 대표적인 두 개의 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 있다. 두 알고리즘은 그리디(Greedy) 알고리즘이다. 알고리즘의 각 단계에서 가능한 몇 가지 선택 중 한 가지를 선택해야 한다. 그리디 방법에서는, 그 순간에서 가장 좋은 것을 선택한다. 이러한 방법은 일반적으로 최적해를 찾는 것을 보장해주지 못한다. 하지만, 최소 신장 트리 문제에 대해서 특정한 그리디 방법을 사용하면 최소 가중치의 신장 트리를 얻을 수 있다는 것을 증명할 수 있다. 크루스칼이 제시한 알고리즘은 연결 요소(connected component) 알고리즘과 유사하며, 프림이 제시한 알고리즘은 Dijkstra의 최소 경로 알고리즘과 유사하다.
크루스칼 알고리즘은 다음과 같다,
1. 집합 A를 공집합으로 초기화한다.
2. 주어진 그래프의 각각의 정점들에 대해서 n(V)만큼의, 단일 정점을 가지는 트리는 생성한다.
3. 주어진 그래프의 간선 E를 가중치에 따라 정렬한다. 오름차순이어야 한다.
4. 각각의 간선(u, v)에 대해서, FindSet(u)의 결과와 FindSet(v)의 결과가 다르면, (u, v)를 A에 추가하고, u, v 정점을 가지는 트리를 서로 합치는 Union(u, v) 프로시저를 호출한다.
여기서, FindSet(u)이 어떤 것을 리턴하는가가 모호한데, 이것은 정점 u를 포함하는 그래프의 대표 원소라면 상관없다. 즉, 정점 u를 포함하는 그래프의 가장 처음 시작 원소를 대표 원소라고 해도 상관없다.
프림 알고리즘을 간략히 설명하면 다음과 같다.
1. 완료된 그래프의 집합과 fringe라 불리는, 후보군의 집합을 만든다.
2. 루트에서부터 시작하여, 이 정점이 가질 수 있는 모든 경로를 보고, 최소의 가중치를 가지는 경로를 선택하여 완료된 그래프 집합에 추가한다.
3. 추가하는 과정에서, 이미 그래프 집합에 있는 정점과, 후보군에 있는 정점과 중복된 경로가 존재할 수 있는데, 이 경우 더 적은 가중치를 가지는 경로를 남긴다.
4. 후보군의 집합이 공집합이 될 때까지 2, 3 과정을 반복적으로 수행한다.
프림 알고리즘은, 각각의 단계마다 최소의 가중치를 가지는 경로를 선택한다는 점에서, Dijkstra 최소 경로 찾기 알고리즘과 비슷하다.