알고리즘 공부<11> - Spanning Tree( kruskal, prim)

오늘은 Spanning Tree가 무엇인지 알아보고 또 여기에서 파생된 2개의 알고리즘에 대해 공부해보자

1. Minimum Spanning Tree

MST는 모든 노드들을 연결(connected)하는데 있어 최소비용(minimum cost)으로 연결하는 트리구조를 말한다.

식으로 표현하면 이렇게 된다.

즉 간선들의 합이 곹 트리의 cost가 되는것이다.  따라서 MST는 몇가지 속성들을 가질 수 있다.

1. V -1 개의 Edge를 가지며

2. no cycle

3. 고유하지 않을 수있다. ( 최소비용인 다른 경로가 존재할 수 있다는점)

그럼이제 MST가 어떻게 구성되어지는지를 보기전에 사전 지식을 먼저 알고 가자

먼저   S는 V(노드)에 부분집합 A는 E(간선)의 부분 집합이라고 하자

여기서  cut( S, V-S)은 S 와 V-S로 나누며 교집합이 존재하지 않는 노드의 파티션이다.

또 이 두 구역을 가로질러 이으는 간선의 집합을 crosses라고 한다.

그리고 cut respects A 는 간선의 부분집합 A에 있어 crosses하는 간선이 없다면 respects A라고 한다.

그리고 crosses할 때 가장 싼 간선을 light edge라고 한다.

그리고 각 집합의 개념을 보면

이렇게 된다. 그럼 이제 본격적으로 크루스칼 알고리즘에 대해서 공부해보자

---

2. kruskal's Algorithm

크루스칼 알고리즘은 정렬된 간선들의 집합을 이용해 MST를 구성하는 알고리즘이다.

먼저 집합 T를 공집합으로 초기화 시켜준다음 각 노드(v)에 대하여 집합을 구성해준다. 

이후 가중치(비용)순으로 간선들을 정렬 해준다.(이러한 과정 때문에 탐욕적이라고함) 이후 정렬해준 간선의 집합에서 각각 각선을 하나씩 뽑아 간선을 이루는 노드에 대해 findSet을 하게 된다.

이 때 findset결과가 같지 않다면 즉 같은 집합에 속하지 않아 사이클을 이루지 않는다면 두 간선을 집합 T에 포합해주고 u와v에 속하는 집합에 대해 합집합을 해준다.

이와 같은 과정을 살펴 보면 MakeSet을 노드 수 만큼 수행하므로 O(v)가 되고, 간선들에 대해서 비용에 대한 정렬을 수행하므로 1sort가 수행된다 ,

FindSet을 모든 간선의 수만큼 수행하므로 O(E)가 된다 그리고 모든 노드의 개수 수만큼 Union 합집합을 수행하게 되므로 O(v)가 된다. 또 

이를  종합하면 O(v) + sort+ O(v) + O(E) 이므로 만약 퀵정렬을 사용하여 정렬하게 된다면 

빅오는 O(ElgE) 이 될것이다 즉 자료구조에 따라 달라지게 된다.

3. Prim's Algorithm

프림 알고리즘 역시 MST를 구하기 위한 알고리즘이다. 의사코드를 보자

프림 알고리즘은 노드에 대한 집합 개념으로 접근한다. 따라서 하나의 노드에서 시작되어진다.

먼저 모든 노드들을 집합 Q에 넣어주고 모든 노드의 key값을 무한대 값으로 넣어준다.

이후 무작위로 하나의 노드를 선택하여(r) 키값을 0 그리고 이전값을 null로 채워준다.

이후 Q가 전부 비워질때까지 최소값을 가진 노드들을 하나씩 추출하게 된다.

Q의 추출한 노드(u)에 대해 인접한 노드(v)에 대해서 그 노드v가 Q에 포함되고 그 노드(v)의 키값이 두 노드를 이으는 간선보다 큰지 확인하여 

맞다면 노드 v의 이전값을 u를 넣어주고 이후 키값을 두노드의 간선의 가중치를 넣어준다. 이와 같은 과정을 Q가 전부 비워질때까지 수행하게 된다.

이 과정에서 중요한 것은 한 노드와 간선을 이루기 위한 인접노드에서 인접노드의 key값 과 두 노드의 간선의 가중치값을 비교하여 간선의 가중치값이 더작다면 인접노드의 키값 으로 넣어주고 이어주며  인접 노드의 key값이 더 작다면 이어주지 않고 다음 노드로 넘어가는것이 포인트다.

자 그럼 빅오를 구해보자

처음에 노드들의 집합을 Q에 넣어주고 이후 이를  무한대로 초기화해준다음 이중 무작위 노드 하나를 뽑아 0으로 초기화 해주는 모든 과정은 총노드수에 해당되므로 O(V) 이다 

이후 while문이 문제인데 

노드의개수만큼 Extract-min이 수행되어지고 이후 차수 즉 총 간선의 개수만큼 key값의 변경이 이루어진다.  

여기서 extract-min 과 key값변경에 있어 큐를 어떻게 구성하느냐에 따라 빅오가 나눠지는데.

배열의 경우 최대 V개의 개수만큼 수행 되어지므로 O(v) 이고 이후 키값 변경은 그냥 단순하게 변경해주므로 O(1)이 된다 

즉 O(v) *v + O(1)*E  이 이므로 O(v*v) 가 된다.

binary heap의 경우 최소값 노드를 하나 뽑아준 이후에 구조를 다시 재조정 해야 하므로 O(lgv) 가 되어지고 키값 변경을 위해 탐색 하므로 O(lgV)에 해당 된다.

즉 O(lgV) * V + O(lgv) * E  가 되며  여기서 스패닝 트리구조는 전부 connectted 되어 있으므로 E>=V이다 즉 빅오는 O(Elgv) 가 된다.

이러한 과정을 거치게되며 최종적으로

이렇게 된다.