Connected Graph에서 MST를 생성하는 Prim's Algorithm(Greedy, Priority Queue)

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)