[c++] 알고리즘 개념공부 :: MST (Prim/Dijkstra, Kruskal, 시간복잡도)

MST

Spanning Tree

: 그래프 내의 모든 정점을 포함하는 트리

 

 우선 트리의 정의는 connected undirected acyclic graph (연결 비방향 비순환 그래프)이다. 모든 노드는 연결되어있으며, 방향성은 없고 순환이 존재하지 않는 그래프이다.

 하나의 그래프가 주어졌을 때, 그래프 내에서 여러 트리를 찾을 수 있다. 그 중 특별하게 모든 정점을 포함하는 트리를 Spanning Tree라고 한다.

 다르게 말하면 Spanning tree(신장 트리)는 그래프의 부분 그래프면서 간선의 수가 가장 적은(최소 연결) 그래프이다.

 

 감이 안온다면 그림으로 살펴보자.

 

 위의 그림과 같이 그래프가 주어졌을 때, 최소한의 간선을 사용하여 모든 정점을 포함하는 부분 그래프가 여러 개 존재한다. 이 부분 그래프는 최소한의 간선을 사용하기 때문에, 트리의 형태가 된다. 이를 Spanning tree라고 한다.

 

특징

Spanning tree는 그래프 내의 n개의 정점을 n-1개의 간선으로 연결한다. 하나의 그래프에도 많은 Spanning tree가 존재할 수 있으며 DFS, BFS 등의 탐색 방법을 사용하여 찾을 수 있다.

 

응용

Spanning tree는 간선의 수를 최소화 하므로 간선에 드는 비용을 줄이는 데에 도움을 준다. 따라서 네트워크망 등의 분야에서 비용을 최소화하고자 할 때 사용한다.

 

MST

: Minimum Spanning Tree

Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 말한다. 가중치 그래프일 때는 단순히 적은 간선을 사용하는 것이 비용을 적게 한다고 할 수 없다. 따라서 적은 간선을 사용하면서 가중치의 합도 적은 MST를 찾아야한다.

 

특징

MST는 간선의 가중치 합이 최소이며, Spanning tree의 특징을 모두 가지고 있다.

 

응용

통신망, 도로망, 유통망 에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하기 위해 사용한다.

---

Kruskal 알고리즘

kruskal은 greedy 알고리즘을 이용하여 MST를 구하는 알고리즘이다. MST의 특징 중 (최소비용), (비순환) 을 지키며 각 단계에서의 최선의 답을 택한다. 각 단계의 최선의 답이 전체의 최선이라는 것을 반드시 증명해야한다.

 

과정

1. 그래프의 간선들을 가중치 기반으로 정렬한다.
2. 정렬된 순서대로 간선을 택하되, 사이클을 만들지 않는 간선을 택한다.
3. 간선이 n-1개가 될 때까지 반복한다.

예시로 살펴보자.

위와 같은 그래프에서 kruskal 알고리즘으로 MST를 찾아보자.

처음에는 graph 오른쪽의 표와 같이 간선을 정렬한다. 정렬된 간선 중 가장 앞에 있는 간선을 택한다.

 

마찬가지로 가장 가중치가 낮은 간선을 택한다.

 

(A,D) 간선이 들어가면 (A,C)=>(C,D)=>(D,A)의 cycle이 생기므로 건너뛰고 다음 간선을 택한다.

cycle이 생성되는지 확인하는 방법은 아래의 '예시(union-find)'를 참조하자.

 

n-1개의 간선이 택해졌으므로 MST를 찾았다.

 

구현

 위의 그림처럼 생각하면 간단하지만, 실제 코드로 구현할 때는 해당 간선이 cycle을 만드는 지를 판단하는 과정이 간단하지 않다.

 이는 dfs를 이용하여 확인하기도 하고, 추가하는 간선에 연결된 정점 2개가 이미 tree에 있는지를 검사해서 확인하기도 한다. 가장 유명한 방법은 union-find 알고리즘을 사용하는 방법이다.

 union-find 알고리즘은 disjoint set(공통된 요소가 없는 집합들)을 이용하는 알고리즘이다. union은 집합을 합치는 과정이고, find는 집합의 대푯값을 반환하는 과정이다. union-find는 배열로 구현하기도 하지만 배열에서는 union과정이 O(N), find가 O(1)이고 트리에서는 union과정과 find과정이 모두 O(lgN)이므로 대부분 트리를 사용한다.

(union-find : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html)

 

 MST의 cycle을 찾는 과정과 연관지어 설명해보자. 주어진 2개의 tree A, B가 있을 때, 정점 x,y가 같은 집합에 속해있는지 확인하려고 한다. 같은 집합에 속해있다는 의미는 이미 연결되어있다는 의미이고, 그렇다면 (x,y)의 간선을 추가하였을 때 해당 집합에 cycle이 생기기 때문이다. 같은 집합에 속해있는지 확인하기 위해서는 x, y 각각이 속한 tree의 루트노드가 같은지 확인하면 된다. 이 과정은 트리를 거슬러 올라가면 되기 때문에 O(lgN)의 시간복잡도로 확인이 가능하다.

 

예시(union-find)

위의 과정에서 보았던 예시를 union-find 과정만 자세히 한 번 살펴보자.

 

 

해당 그래프에서 처음에는 root 정점 값이 자기 자신이다. 가장 가중치가 작은 첫 간선 (A,C)를 추가할 때, A 정점과 C 정점의 root가 다르므로 cycle을 형성하지 않는다는 것을 알 수 있다.

 

 

그 후, (C,D) 간선을 추가할 때도 C 정점과 D 정점의 root가 다르므로 cycle을 형성하지 않는다는 것을 알 수 있다.

(코드 구현 추가)

 

DFS vs Union Find

 만약 cycle을 찾을 때 DFS를 사용했다고 해보자. 주어진 그래프가 완전 그래프일 때 한 정점에서의 간선은 n-1개가 존재하고, 이 간선들을 가중치 순으로 하나씩 체크해야한다. 최악의 경우 마지막 간선을 제외한 모든 간선이 cycle을 만들 수도 있는데, 이 경우 모든 간선에 대해 dfs를 수행해야하므로 n-1에 dfs의 시간복잡도 n을 곱해서 O(n^2)의 시간복잡도가 나온다. 이 과정을 n-1개의 간선을 찾을 때까지 반복해야하므로, dfs 이용시 총 O(n^3)의 시간복잡도를 가진다. E를 간선의 갯수로, V를 정점의 갯수로 표현하면 O(EV)라고 표현할 수도 있다.

 하지만 Union-Find 알고리즘을 이용한다면, cycle을 찾는데에 최대 lgn 밖에 걸리지 않는다. 따라서 모든 간선에 대해 체크를 했을 때, O(nlgn)의 시간복잡도가 나오며 총 시간복잡도는 O(n^2lgn)이 된다. O(ElgV)라고 표현할 수도 있다.

 

시간 복잡도

Union-Find 알고리즘을 이용했을 때 시간복잡도는 cycle을 찾는 데에서 O(n^2lgn)이 소요되고, 간선을 정렬하는 데에 O(ElgE)가 소요되므로 간선 정렬 시간복잡도에 따라 총 시간복잡도는 O(ElgE)가 된다.

즉, O(n^2lgn)이다.

 

정리

• 간선 선택이 기반이다.
• greedy 알고리즘을 사용하여, 이미 최적의 해를 구할 수 있음이 증명되어있다.
• cycle을 찾을 때는 Union-find 알고리즘을 사용한다.
• 시간복잡도는 간선 정렬에 기반하여 O(n^2lgn)이다.

---

Prim(Dijkstra) 알고리즘

과정

1. 시작 정점을 포함한다.
2. 인접 정점 중 최소 간선으로 연결된 정점을 선택한다.
3. n-1개의 간선이 모이면 종료한다.

예시로 살펴보자.

 

위와 같은 그래프에서 Prim 알고리즘으로 MST를 찾아보자.

처음에는 시작 정점을 포함시킨다.

 

시작정점과 인접한 정점인 (B, C, D) 중 가장 간선의 가중치가 낮은 (A,C)의 C 정점을 포함시킨다.

 

그 후, 이미 포함된 정점들과 인접한 정점인 (B,D,E) 중 가장 간선의 가중치가 낮은 (C,D) 의 D 정점을 포함시킨다.

 

정점이 모두 포함될 때까지 반복한다.

 

구현

vertice(정점)는 3가지 분류로 나뉜다.

• tree vertice(T) : tree에 속해 있는 정점
• fringe vertice (F) : tree에 포함되지 않으면서 연결되어있는 정점
• unseen vertice (U) : 나머지

1. 모든 정점을 U 집합으로 초기화한다.
2. 시작 정점은 T에 넣고, 해당 정점과 인접한 정점을 F에 넣는다.
3. F가 존재하는 동안, T-F의 minimum weight edge를 찾는다.
   • 해당 간선에 연결된 정점(V)을 T에 포함시킨다.
   • tree에 해당 간선을 포함시킨다.
   • V의 인접 정점들을 F에 포함시킨다.

 

시간 복잡도

Prim 알고리즘의 시간 복잡도는 최소 가중치 간선을 찾는 것에 의존한다.

 

T 집합에 k개의 노드가 있고, 총 노드의 갯수가 n이라고 하면 완전 그래프일 때 T-F 간선의 갯수는 (n-k)*k이다. 따라서 최소 가중치 간선을 찾으려면 (n-k)*k -1번의 비교가 필요하다. 최소 가중치 간선을 찾는 과정을 n개의 정점을 찾을 때까지 반복해야하므로, 이렇게 구성되었다면 Prim 알고리즘의 시간복잡도는 O(n^3)일 것이다.

하지만 T에 속한 노드들을 각각의 노드로 보지 않고, 하나의 T라는 노드 보기 때문에 더 적은 시간복잡도로 줄일 수 있다.

 

즉, 위에 표시된 두개의 간선을 비교해서 가중치가 작은 간선만을 유지하는 방식으로 나타냈다.

 

 이렇게 나타내면 n-k개의 간선만이 존재한다고 볼 수 있다.

 이렇게 구현하기 위해서는 가중치를 나타내는 배열을 만들고, 해당 배열이 Fringe에 속하는 정점에 대해서 T와의 최소 가중치만을 유지하도록 만들어주면 된다. 정점이 T에 추가될 때마다 기존에 존재하는 최소 가중치보다 해당 정점과 이어지는 간선의 가중치가 더 작다면 갱신해주면 되는 것이다.

 정점이 추가될 때마다 최소 가중치가 갱신되므로 이를 정렬하기 위해서는 O(nlgn)의 시간복잡도가 필요하다. 따라서 총 O(n^2lgn)의 시간복잡도를 가질 수 있다.

 

정리

• 정점 선택이 기반이다.
• 최소 가중치 간선을 찾기 위해 배열로 이를 갱신한다.
• 시간복잡도는 간선 정렬에 기반하여 O(n^2lgn)이다.

---

Prim vs Kruskal

prim과 kruskal 알고리즘 결과로 나온 MST는 서로 다를 수 있다.