[Study] 알고리즘 문제풀이

최소스패닝트리 #프림 #크루스칼 #그래프 #트리 #네트워크

미런던 2017. 5. 5. 22:51

스터디를 위한 준비!


그래프, 트리, 네트워크 대략적 차이

트리 : Circuit이 없는 그래프

그래프 : 노드와 엣지로 구성. directed/undirected, weighted edge/unweighted edge 등등 여러 종류가 있다.

네트워크 : 그래프와 비슷.


최소스패닝트리, Minimum Spanning Tree

'최소신장트리', '최소비용신장트리' 등으로도 불린다.

1. 방향성이 없는 Edge를 갖는 그래프에 한해서,

2. 모든 노드들이 연결되는 Edge Set을 만드는 것이다.


프림 알고리즘, Prim

매우 단순한 그리디 알고리즘.


1. 임의의 V를 골라서 Set을 만든다.

Loop (n-1회) {     2. Set에 연결된 엣지들 중 가장 작은 것을 고른다.(pq)

3. 해당 노드를 Set에 포함하고, pq를 업데이트해준다. }


크루스칼 알고리즘, Kruskal's

매우 단순한 그리디 알고리즘.


1. 모든 Edge들을 weight기준 정렬한다. (sorting)

Loop (n-1회){      2. weight가 가장 작은 edge를 뽑아 연결하고 있는 두 노드 V1,V2에 대해

3. V1, V2가 속해져있는 Set이 다르면 연결한다. (Union)    }


두 알고리즘 모두 Greedy라, 맞는지 확인하기 위해 귀류법을 사용해본다.



크루스칼 알고리즘 증명


우리가 찾는 답이 유일하다고 가정, 이 답을 Tmst 라고 부른다.

핵심 : "알고리즘의 모든 단계에서 T 가 Tmst의 subset이다." 를 증명

base : T는 공집합. (true)

induction : T가 Tmst의 subset이고, T + {e} = T'가 Tmst의 subset이 아닐 경우,

{e}는 Tmst의 원소가 아니므로, Tmst + {e} 는. 노드 v개, edge v -1 + 1개로 루프가 생긴다.    

(Tmst관점에서는 그렇고, T'에는 아직 루프가 있지는 않다.)

즉, 루프 위에 있되, 아직 T'에 포함되지 않고, e와 같은 노드에 연결된 엣지 f가 있다. (*)

f가 e보다 weight가 무겁다. 즉, Tmst = (Tmst - {f} ) + {f} > (Tmst - {f} ) + {e} (*)

(* 위 부분들 사실 더 디테일한 증명이 필요한것같으나 그림과 직관으로 대체)