[Greedy Algorithms] Minimum Spanning Tree

 

 

Greedy Alogrithms

• 답을 찾기 위해 선택을 반복하는 알고리즘
• 비교적 간단한 방법으로 선택
• 선택한 후 바꾸지 않는 알고리즘

ex) selection sort -> greedy 

전체에서 가장 작은걸 찾아서 새 배열의 첫번째 배열로 "선택"하여 옮김 

선택하는 것은 가장 작은것을 고름 (선택을 한 쪽의 배열에서는 없어졌다고 생각)

남은곳에서 또 제일 작은 것을 고르는 과정을 반복

 

Shortest path idea

S에서 B까지 가는 가장 짧은 길을 찾는다고 하자

* S에서 A까지 가는 가장 짧은 길 등등을 찾는것과 같다. 해당 짧은 길을 찾으려면 많은 가장 짧은 길을 찾아야한다. 

S에서 나가는 것 중에 제일 작은 것은 5이고 C에 도착

C까지 가는 5보다 짧은 길이 있는가? -> 없음 : 다른 길을 가는 순간 이미 5보다 큼

이러한 방법으로 반복하는 것이 greedy방법이다

*나중에 자세히 설명하겠다. 

 

Minimum Spanning Tree

Given a Graph, find subset of edges so that a connected graph results with minimum sum of edge cost

엣지들의 일부를 골랐을 때 연결된 그래프가 남아야하고, 그 비용이 가장 작아야한다. 

 

노드 개수가 적으면 모든 경우를 다 따져볼 수 있음

작은 수부터 하나하나 따져가며, 사이클을 만드는 경우 등등을 고려하여 만든다. 

이렇게 5개의 노드가 있다면, 4개의 엣지의 모든 경우를 고려해봐도 됨 -> 하지만, 그래프의 수가 많아진다면 어려워짐

 

Prim Algorithm

idsa

• 하나의 노드를 가진 트리에서 시작 (아무 노드나)
• 트리에 인접한 에지들 중 가장 작은 웨이트를 가진 엣지를 추가
  단, 사이클을 만들지 않아야함
• Spanning Tree가 될 때까지 반복

해당 아이디어를 따라가다 보면, 1, 2, 3, 5의 엣지들을 선택할 수 있다.

 

Correctness

*Greedy 알고리즘의 증명은 답이 여러개 있기 때문에 더 어렵다

statement : prim algorithm 이 가지고 있는 edge set T는 어떤 정답의 부분집합이다.

\(\leftrightarrow\) 항상 T ≤ \(T_{mst}\) for some 정답 \(T_{mst}\)

*알고리즘이 끝났을 때 \(|T| = n-1\), \(|T_{mst}| = n-1\)이고, 해당 조건을 만족한다면 T = \(T_{mst}\)이다.

 

결론 : prim 알고리즘은 답 중에 하나를 만든다.

G = (V,E)이고, E는 노드 쌍의 집합이다.

\(T_{mst}\)는 edge set으로 정답 중 하나이다. 

우리는 T에 우리가 선택한 edge set을 넣는다.

 

Q) 왜 프림알고리즘은 저 "한" 정답을 만드는가? A) 모른다. 정해진건 없지만 정답 중 하나를 만든다.

 

결국 증명을 하려면 \(T_{mst}\)와 비교해야하는데, 뭔가 잡긴 잡아야하는데 이걸 특정할 수 없음. 따라서 잡는 것이 바뀔 수는 있지만 정답인 것은 유지됨

 

< proof >

base) \( T = \emptyset \) and \(T \leq T_{mst}\)

 

해당 그림에서 검은색이 edge가 모두 \(T_{mst}\)이다.

 

step)

Case1 and Case2

어떤 시점에 \(T \leq T_{mst}\) 가정 

알고리즘이 edge \(e_1\)을 추가, 

\(T' = T \cup \{e_1\}\)

 

case1 : \(T' \leq T_{mst}\) => OK

case2 : \(T' \nleqslant T_{mst}\) 

\(T_{mst} \cup \{e_1\}\) -> cycle 존재

cycle 안에 \(e \neq e_1\), \(e \notin T\), \(T \cup \{e\}\)가 no cycle이고, e가 T에 인접하는 e가 존재한다.

현재 만들어진 사이클 안에는, 빨간 선이 있고, 지금 추가하고자 하는 파란 선이 있고, 검은 선이 무조건 존재한다 .

사이클을 만들게 되면 엣지에 추가하지 않으므로, 파란색을 추가하고자 알고리즘이 선택했다면 무조건 검은 선이 존재할 것이다. 

또한, 이 검은 선은 무조건 빨간 선과 인접 (연결) 되어있다. 

e

해당 조건을 만족하는 e가 이것이다. Y S

즉, 원래 내가 생각하던 정답 (검은색)과 다른 엣지를 추가하였다. 

파란색과 현재 e중 현재 파란색을 선택하게 된 상황인 것이다. 

case 2-1 : \(w(e_1) > w(e)\)이면 알고리즘과 모순 (가장 작은 엣지를 추가한다)

case 2-2 : \(w(e_1) < w(e)\)이면 \((T_{mst} - \{e\})\cup\{e_1\}\)이면 이게 더 좋은 정답이된다. \(T_{mst}\)는 정답이였으므로 모순

case 2-3 : \(w(e_1) = w(e)\)이면 \((T_{mst} - \{e\}) \cup \{e_1\}\)이므로 이것도 정답이다. 이는 \(T'_{mst}\)로 또 다른 정답을 찾은것이다.

 

구현 및 성능

Algorithm Prim (G, T)

G : 입력 G = (V,E)

T : 출력, edge set

|V| = v, |E| = m

• T = Empty set
• U = node set으로 트리에 붙은 노드를 저장하는 set을 설정 (성능을 위해)
• While U != V do (정확히는 n-1번)
  U의 한 노드와 V-U의 한 노드를 잇는 엣지들 중 웨이트가 제일 작은 것 uv (한쪽 노드는 트리에, 한쪽은 아니기에 사이클을 만들지 않고 인접한 엣지를 추가한다)
  uv를 T에 추가
  v를 U에 추가

이대로 구현하면 여전히 느리다. 

uv를 T에 추가하는것,v를 U에 추가하는 것 모두 시간이 걸리지 않는다. 

T는 출력이기 때문에 set이지만, 배열로 그냥 만들면 됨

U도 배열로 만든 뒤에, 그냥 마킹하도록 설정하면 됨 (U에 있는 노드와 없는 노드를 구분하기 쉬움)

 

즉, 여기서 중요한 것은 엣지들 중 웨이트가 제일 작은 것 uv를 고르는 것이다. 

만약, 여기서 모든 것을 확인한다면 O(nm)이 걸리게 될 것이다. 

 

 

< Graph 의 표현 > 

 

입력은 단순히

노드 엣지

노드 노드 weight

로 입력한다.

 

ex) 5 7

1 3 5

1 2 1 ...

 

이러한 입력을 바탕으로 왼쪽처럼 그래프를 표현한다. 

 

 

 

 

 

노드마다 마킹한 배열을 만든다. 

노드가 Tree에 들어갔다. 들어가지 않았다.를 체크하는 것이다. 

만약, 4번이 마킹되었다고 생각하면, 4번과 인접한 노드를 모두 "고려"해야한다 (고려하는것은 priority queue를 이용)

 

고려해야하는 노드는 모두 priority queue에 그래프의 입력처럼 노드 노드 weight의 형태로 들어간다. 

제일 작은 것을 꺼내면 트리에 인접하지만, 사이클을 만들 수도 있는데

만약 사이클을 만든다는것은 이미 트리에 들어가있다는 것이기 때문에, 노드를 체크하는 배열에서 이미 버려진다.

새로운 노드가 추가되면 고려되어야할 것들을 계속 queue를 추가하고, 안되는 것을 버리는 작업을 반복한다.

이 때 n-1이 되면 종료한다. 

 

*하지만 이렇게 도는 과정에서 때에 따라 얼마나 돌지 모름

graph에서 쓰는 시간, node 마킹에서 쓰는 시간 priority queue에서 쓰는 시간을 전부 더하면 됨

 

Graph : 전부 한번씩만 읽음, 한번 추가된 엣지는 추가하지 않기 때문에 - O(m)

priority queue : 동일한 엣지는 여기에 두번 들어감. 노드가 추가될 때 들어가므로 두 번 들어감

priority queue에서 넣고 뺄 때 logm이 걸리므로 O(2mlogm) = O(mlogm)

node 마킹 : 엣지가 하나 꺼내질 때마다 두 칸을 본다(노드 두개) 최대 엣지가 2m번 꺼내지므로 O(4m)

따라서 전체 시간이 O(mlogn) = O(mlogm) = O(n + mlogm) = O(n + m + mlogm)이다. 

 

 

 

Kruskal Algorithm

프림 알고리즘은 하나를 선택하면 거기에 인접한 애들을 찾아나가며 구함

크루스칼 알고리즘은 전체에서 작은 것부터 넣음

idea

• Keep adding edge
• From smaller weights
• As long as no cycle results 
• Until N-1 Edges are added

Q) 어떻게 사이클을 만들지 않는다는 것을 알까?

A) 프림은 인접한 것을 추가하기 때문에, 사이클인지 아닌지를 알 수 있었다. Connected component를 사용한다. 서로 다른 connected component에 있는 것만 추가한다. 

 

 

해당 아이디어를 따라가면, 1, 2, 3,5를 연결하게 된다. (4는 사이클이 생겨서 안됨)

Correctness

 

T : edge set

invariant : \(T \subseteq T_{mst} \) 가 유지된다. 

이때, \(T_{mst}\)는 정답 중 하나

 

< proof > 

base ) \( T = \emptyset \) OK
step )

어떤 시점에 \(T \subseteq T_{mst} \)라고 가정하자

algorithm 이 edge e를 추가한다. 

\(T' = T \cup \{e\}\)

 

case 1 : T' ≤ \(T_{mst}\) OK

case 2 : \(T' \nleqslant T_{mst}\)

case 2

\(T_{mst} \cup {e}\) -> cycle 존재

cycle 에 T에 안들어있고,e도 아닌 edge가 하나 이상 존재함 => 즉 검은 선이 존재해야함

-> 그 중에 최소 weight인 것을 \(e_1\)을 찾아야한다 (프림에서는 인접한 것) 

*아무거나 잡아도 아래 case 3개가 전부 증명됨

 

case 2-1 : \(w(e) < w(e_1)\) -> \((T_{mst} - \{e_1\} \cup \{e\}\)가 더 좋으므로 모순

case 2-2 : \(w(e) = w(e_1)\) -> \((T_{mst}-\{e_1\} \cup \{e\}\) 얘도 정답

case 2-3 : \(w(e) > w(e_1)\) -> algorithm 에서 \(e_1\)이 먼저 추가되었어야함. 추가하지 않는 경우는 사이클을 만드는 경우 밖에 없는데, e가 없으면 사이클을 만들지 않으므로 말이 안되는 경우이다. 

 

따라서 세가지 경우 모두 괜찮거나 모순이 생긴다.

 

구현 및 코드

Algorithm Kruskal(G,T)

• T : empty set
• While |T| < n-1 do
  E에서 가장 작은 weight인 엣지 e 선택
  E = E - {e}
  if (V, T\(\cup\) {e} )에 사이클이 없으면,  T <- T\(\cup\) {e} (프림에서 얘기한 것과 같이)

그래프를 링크드 리스트로 표현하거나, 마크를 표시할 필요 없음

 

< Union Find > 

한 덩어리만 구분할 수 있으면 됨

 

sort edges by weight -> 즉, 노드 노드 weight로 저장된 것을 순서대로 쭉 나열한 후 맨 앞에 있는 것을 보고 만약 노드와 노드가 같은 덩어리인지 확인한다 . 

 

ex) (3,4,1)이면 현재 3-4가 한 덩어리임을 표시

(2,3,3)이면 현재 2-3-4가 한 덩어리이다.

(4,2,6)이면, 현재 2-3-4가 한 덩어리임으로 union find로 덩어리를 확인하여 추가하지 않는다. 

 

edge를 sorting 한 것이 m개

union find가 n개이다. 

 

edge sorting : O(mlogm)

union find : O(m \(\alpha\) (n))

따라서 전체 시간은 O(mlogm)이다. 

 

 

Prim and Kruskal can find ANY solution

프림과 크루스칼 알고리즘은 어떤 솔루션도 찾을 수 있다.

똑같은 입력에 대해서 다르게 돌아갈 수 있다. 작은걸 고를 때 같은게 있으면, 어떤걸 먼저 고르느냐에 대한 차이이다. 

 

stable sort

some algorithms cannot find some of the possiblee solutions

원래 순서가 유지가 되는 sorting 이다. 

이러한 sorting을 한다면 모든 가능한 답을 만들 수는 없다 (같은 것은 바뀌어도 되니까)

 

proof

Fix any solution \(T_{mst}\)

Show Prim can find THAT solution 

 

아까 증명에서 \(w(e) = w(e_1)\)일 때, prim alg이 \(e_1\)을 추가할 수도 있었다. 

 

is that property important?

can be used to show that if all weights are differenct there is exactly one solution to the MST problem

만약, 모든 edge weight가 다르면 답이 "유일"하다. 

 

prim과 kruskal은 가능한 어떤 답이든지 만들 수 있다. 

만약, 정답과 같으면 바꿔서 넣을 수 있었다. -> 여러가지 결과를 낼 수 있음

따라서 저러한 경우가 없다면 다른 결과를 낼 수 없다 .

그러면 알고리즘이 다른 답을 만들 선택권이 없기 때문에 유일한 답만 만들 수 있다.