-
Connected Graph에서 MST를 생성하는 Prim's Algorithm(Greedy, Priority Queue)Algorithm 2021. 3. 19. 02:30
MST를 생성하는 방법에는 Kruskal, Prim 두 가지 알고리즘이 존재한다.
Kruskal 알고리즘을 빠른 시간 내에 동작하게 하려면 Union-Find 자료구조(라이브러리가 없기에 직접 구현해야함)를 사용해야 한다는 번거로움이 있지만, 여기에서 다룰 Prim's Algorithm은 priority queue를 가지고 구현할 수 있다.
Prim's Algorithm을 관통하는 가장 중요한 property를 정의하고 가자.
Cut Property:
Edge e = (u,v)는 MST의 edge set T에 속해 있다 ↔ e는 vertex u를 포함한 어떤 vertex set S와 v를 포함한 V(G) - S를 이어주는 edge들 중 제일 cost가 작다
- (오른쪽 그림, ←)MST가 위에서 설명한 e 대신 S와 V(G) - S를 이어주는 다른 edge e'을 가지고 있다고 했을 때, e의 성질에 의해 T에서 e를 제외한 뒤 e'를 추가해주면 기존 cost보다 작아지므로 T가 MST의 edge set이라는 가정에 모순된다.
- (→)T가 어떤 MST를 이루는 edge set이라 하고 S와 V(G) - S를 각각 T에서 e를 제외한 connected component에 속하는 vertex set이라 할 때, 위와 같은 상황에서 모순이 발생한다.
이와 같은 cur property를 통해, V(G)에 속하는 어떤 임의의 vertex set S에 대해 MST는S와 V(G) - S를 이어주는 edge들 중 cost가 가장 작은 edge를 언제나 포함한다는걸 알 수 있다.
👉 Prim Algorithm은 S에 속한 vertex를 하나씩 늘려가면서 cut property를 만족시키도록 edge를 골라 나가 MST를 생성한다.
+ 왜 해당 알고리즘으로 edge들을 추가한 결과물은 tree가 될까??(connected & acyclic할까) 🤔
👉 base case: S의 원소가 한 개 일 때 vertex 하나를 추가해주면 결과물은 tree이다
👉 inductive step: S가 tree라면 V(G)-S에 속한 vertex v와 S를 이어주는 결과물도 트리가 나올 수 밖에 없다(cycle이 생길 수 없기 때문. cycle이 생긴다는 것은 이미 S에 v와 연결된 vertex가 있다는 것인데... 그럼 V(G)-S에 속한 vertex가 아님)
Prim's Algorithm with greedy
1️⃣ S = {v}, v는 graph G상의 아무 vertex
2️⃣ S와 V(G) - S를 이어주는 edge들 중 가장 작은 cost를 가진 e = (v,w)를 MST의 edge set T에 추가
3️⃣ w를 S에 추가
4️⃣ 2️⃣~3️⃣을 S=V(G)가 될 때 까지 반복
Pseudocode는 다음과 같다
S = {v} T = ε (T will store edges of a MST) while S is not V(G) pick e = (v,w) in E(G) such that, V∈S and w∈V(G)-S, and e has minimum cost T = T ∪ {e} S = S ∪ {w} return set T
Time Complexity: 총 N번(vertex 개수)반복 & 해당 조건을 만족하는 edge(minimum cost)를 찾는데 최대 O(m)시간 소모
= O(NM)이다.
하지만 minimum weighted edge를 빠르게 찾을 수 있는 방법은 priority queue(min heap)를 통해 구현할 수 있다.
priority queue를 통해 로직을 재 설계하면 다음과 같다.
1️⃣ V(G)에 속한 vertex v에 대해 cost(v) = (u∈S)min w(u,v)라 한다.
- cost(v)의 초기값은 Prim's algorithm을 처음 시작할 vertex(해당 vertex는 cost 0)를 제외하고는 INF(무한대)로 초기화한다.
- 각 vertex v에 대해 pre(v)라 하는 pointer를 두고 초기값을 nil(아무것도 가리키지 않는다는 뜻)로 둔다.
2️⃣ 모든 vertex들을 cost(v)를 priority로 둔 priority queue H에 insert한다.
→ cost(v)가 작을수록 priority가 높다(min heap).
3️⃣ H에서 deletemin을 통해 얻는 vertex v를 S에 추가한 다음, pre(v) = nil이 아니라면 edge(v, pre(v))를 MST의 edge set T에 추가해 준다.
→ nil이 아닌 pre(v)값은 S상에 있는 vertex를 의미한다. 따라서 3번을 수행하면 V(G)-S의 vertex와 S를 연결하는 것
4️⃣ H에서 v와 adjacent한 모든 vertex의 cost를 다시 계산하여, 변경해야 할 경우 decreasekey(delete&insert)를 사용해 cost를 변경해준다. 이 때, edge e(v,z)로 인해 z의 cost가 변경되었다면 pre(z) = v로 변경해준다.
5️⃣ 3️⃣~4️⃣를 H가 완전히 빌 때 까지 반복
Prim's Algorithm을 시뮬레이션하면 위와 같다.
각 step을 수행할 때 마다, S에 인접한 vertex 중 cost가 가장 작은 edge를 포함하는 vertex를 S에 추가한다.
Pseudo Code
procedure Prim(G, w) Input: A Connected undirected graph G = (V,E) with edge weights w Output: A minimum spanning tree defined by the array prev for all u ∈ V: cost(u) = INF prev(u) = nil pick any initial node u0 cost(u0) = 0 H = makequeue(V) (priority queue, using cost-values as keys) while H is not empty: v = deletemin(H) for each {v,z} ∈ E: if w(v,z) < cost(z): cost(z) = w(v,z) prev(z) = v decreasekey(H,z)
Time Complexity:
- (makequeue = insert n번) + deletemin n번 -> O(n logn)
- 각 edge를 최대 2번 scan하며 decrease key는 최대 m번 수행 (edge e(u,v)에 incident한 vertex u, v는 각각 한 번씩만 visit하기 때문) -> O(m logn)
- sum = O((m+n)log n)
'Algorithm' 카테고리의 다른 글
Weighted Graph에서 최단거리를 찾는 Bellman-Ford Algorithm (0) 2021.04.04 Edge-Weighted Graph에서의 최단경로를 찾는 Dijkstra Algorithm (427) 2021.03.23 Connected Graph에서 MST를 생성하는 Kruskal's Algorithm(Greedy, Union Find) (413) 2021.03.16 무방향그래프에서의 Cut Vertex와 Biconnected Components (388) 2021.03.08 Sort Algorithm(Bubble/Insert/Selection/Merge/Quick)과 시간복잡도 (0) 2021.02.25