DataStructure - 신장 트리, Kruskal 의 MST 알고리즘, 위상 정렬

신장 트리

신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리다. 신장 트리도 트리의 일종이므로 모든 정점들이 연결되어 있고 사이클이 없어야 한다. 신장트리는 그래프에 있는 n개의 정점을 정확히(n-1)개의 간선으로 연결하게 된다.

신장 트리를 찾기위해 기피 우선 탐색이나 너비 우선 탐색을 이용할 수 있는데, 하나의 그래프에는 많은 신장 트리가 가능한 것에 유의하라.

신장트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선들만 모으면 만들 수 있다.

---

최소 비용 신장 트리

최소 비용 신장 트리(MST : minimum spanning tree) 란 어떤 그래프의 신장 트리들 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다.

최소 비용 신장 트리를 구하는 방법에는 Kruskal 과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있다.

• Kruskal 의 MST 알고리즘

Kruskal의 알고리즘은 탐욕적인 방법(greedy method)이라는 알고리즘 설계에서 중요한 기법 중의 하나를 사용한다. 이것은 어떤 결정을 해야 할 때마다 "그 순간에 최적"이라고 생각되는 것을 선택하는 방법이다. 물론 순간에 최적이라고 판단했던 선택을 모아 최종적인 답을 만들었을 때 이것이 "궁극적으로 최적"이라는 보장은 없다. 따라서 탐욕적인 방법으 항상 최적의 해답을 주는지를 반드시 검증해야 한다. 다행히 Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.

Kruskal의 알고리즘은 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 이러한 과정을 반복하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구한다. Kruskal 의 알고리즘을 자연어로 나타내면 아래의 알고리즘과 같다. 

| Kruskal 의 최소 비용 신장 트리 알고리즘

kruskal()

1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

2. 가장 가중치가 작은 간선 e를 뽑는다.

3. e를 신장트리에 넣을 경우 사이클이 생기면 삽입하지 않고 2번으로 이동한다.

4. 사이클이 생기지 않으면 최소 신장 트리에 삽입한다.

5. n-1개의 간선이 삽입될 때 까지 2번으로 이동한다. 

Kruskal 의 알고리즘은 간단해 보이지만 아직 해결하지 못한 부분이 있다. 사이클이 생기는지를 검사하는 것이다. 이미 선택된 간선들의 집합에 새로운 간선을 추가할 때 사이클을 생성하는 지를 체크하여야 한다. 새로운 간선이 이미 다른 경로에 의하여 연결되어 있는 정점들을 연결하면 사이클이 만들어 진다.

사이클을 검사하는 과정을 포함하여 Kruskal의 알고리즘을 다시 기술하면 다음과 같다.

• 초기에는 모든 정점이 각각 고유한 집합이다.
• 최소 가중치 간선(u, v) 가 선택되면 u 와 v 가 각각 속한 집합을 찾는다. 이때 find(u) 와 find(v) 연산을 수행한다.
• 두 집합이 같으면 사이클이 발생하는 상황이므로 이 간선을 벌니다.
• 두 집합이 다르면 간선을 삽입하고 집합을 하나로 합친다. 이때 union(u, v) 연산을 사용한다.

Kruskal의 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다. 따라서 퀵 정렬이나 최소 힙과 같은 효율적인 알고리즘을 사용한다면 Kruskal의 알고리즘의 시간 복잡도는 이다.

---

위상 정렬

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상 정렬(topological sort)이라고 한다.                                                                                                                                                            

방향 그래프의 위상 정렬 알고리즘을 생각해 보자. 먼저, 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 연결된 모든 간선을 삭제한다. 이때, 삭제되는 간선과 연결된 남아있는 정점들의 진입 차수를 변경한다. 이 과정을 반복하여 모든 정점이 삭제되면 알고리즘이 종료된다. 전체 과정에서 정점이 삭제되는 순서가 위상 순서(topological order)가 된다.

진입 차수 0인 정점이 여러 개 존재할 경우 어느 정점을 선택하여도 무방하다. 따라서 하나의 그래프에는 여러개의 위상 순서가 존재한다. 만약 그래프에 남아 있는 정점 중에 진입 차수 0인 정점이  없다면 위상 정렬은 불가능하다. 이것은 그래프에 사이클이 존재하는 것이고, 모든 과목이 선수과목을 갖는 것을 말한다.