[sw정글 3주차] 문지동 MST알고리즘 마스터의 쉽게이해하는 최소 스패닝 트리(Minimum Spanning Tree) 설명

📚SW정글 3.3주차

(4명의 저자들의 last-name의 앞글자만 따서 C.L.R.S)

CLRS라고 불리우는 알고리즘 책이다. 극찬받는 좋은 책이라고 하지만, 공감할 수 없었다. (서울대 문병로 교수님의) 번역이 정말 💩이기 때문이다. 책에서 나오는 example들과 solution을 왜 없애두었는지 모르겠다. 번역어투도 마음에 들지 않는다.

그리고 이건 시대의 문제 같은데, 용어가 너무 공감가지 않는 방식으로 번역되었다. MST(Minimum Spanning Tree)알고리즘의 경우에는, 최소신장트리로 번역되었다. 트리가 신장(Spanning) 하기 때문이라고 한다👎. 솔직히 20년 전, 한자어를 많이 사용할 떄야 적절한 단어였을 것 같지만, 요즘은 다른 방식으로 번역되어야 할 것 같다.

minimum, spanning => 신장 스패닝, 확장, 한붓그리기🤔?, 최소포괄범위🤔? edge도 간선이라고 표현되어있다. 그냥 엣지라고 해도 될 것 같다. 개인적인 의견으로 간선이라고 하는건 좀 구리다. 그래프에서 트리가 여러개 있으니, Forrest? => 이걸 깊이우선 포리스트 라고 해두었는데 이것도 조금…

노드 = 정점 = vertex

간선 = edge

🔎MST에 관하여

MST는, 그래프G에서 span(신장)하여 모든 노드들을 포괄할 수 있는 edge들의 집합을 알아낼 수 있는 경우이다.

쉽게말하면, 최소비용으로 모든 집을 연결하는 경우이다. 서울의 모든 집에 전기를 공급하려면 어떻게 해야할까? 일단 모든집이 연결되어야 한다. 모든 집들을 연결하는데 드는 최소비용을 알아내는 알고리즘이다. 그렇다면 여기서 서울의 각각의 집들은 노드(a.k.a [node, vertex, 정점])가 될 것이고, 이를 연결하는 전선들은 간선(a.k.a edge)가 될 것이다.

알고리즘의 근-본 서적인 CLRS 에서는 그래프 G에 대한 Vertex와 Edge들 이라고 표현한다. 그리고 이를 수학적으로 G(V,E)로 표현할 수 있다.

편의상 비유를 통해서 MST알고리즘을 설명하고, 이를 수학적으로(멋있는척) 표현할 수 있는 방법들을 설명 해 보도록 하겠다. 처음에는 이해가 안갔지만 휴게실에서 예리한 개발자(링크)의 도움을 받아서 쉽게 이해할 수 있었다.

이에 대해 CLRS에서 얻어낸 부가적인 지식들을 같이 설명해 보고자 한다. 하이에나마냥 끈질기게 글을 읽고나서 근-본을 깨우쳐서 매우 기뻤다.

(새벽 03:01분) MST를 뿌수고 강의실을 떠나는 Sunny(본인)

🚀Generic MST

일단 MST알고리즘에는 두가지가 있다. Kruskal-알고리즘과 Prim-알고리즘 이다. 둘다 그리디 알고리즘이다. BST(이진트리)를 통해서는 모두 O(ElogV)시간에 실행될 수 있으며, 피보나치 힙을 통해서는 조금 더 빠르게 실행될 수 있다. 뒤에서 설명하도록 하겠다.

오늘은 MST를 설명해 보고, 다음 시간에는 최단경로를 설명 할 예정인데, 크루스칼 알고리즘은 Connected Component-알고리즘과 비슷하고, 프림은 다익스트라 알고리즘과 비슷하다.

책을 공부하며 얻어낸 핵심은 딱 1개이다. 그 핵심을 지금 바로 알아보고, 이 내용이 크루스칼과 프림에 어떻게 적용되는지 알아보도록 하겠다. 가장 핵심 내용을 다음줄에서 바로 설명을 하고, 부가적인 설명을 이어나가도록 하겠다.

❗️❗️MST의 핵심❗️❗️

카이스트와 충남대의 교수님들은 비밀조직을 만들고자 한다. 충남대의 6개의 연구실과, 카이스트의 7개의 연구실들은 모두 연결되어 비밀메시지를 주고받고자 한다. 현재 카이스트와 충남대의 각각의 학교에서는, 연구실들을 미완성이지만 최소비용으로 연결하였거나, 완전히 연결했다.

그렇다면 최소비용으로 비밀조직 연결망을 열결하는 방법 중, 카이스트와 충남대를 연결하는 연결선은, 위의 보라색 점선 중 어떤 선들일까?????

정답은… 보라색 점선중 가장 비용이 낮은 경로이다. 그 연결이 비밀조직 연결망을 만드는 최소비용 선분임을 보장할 수 있는 것이다.

다른 방법으로 한번 더 설명 해 보겠다.

MST를 만족하는 그룹 A를 respect하는 G의 cut에 대해, light-edge(u,v)는 A에 대해 Safe edge를 보장할 수 있다.

무슨 말인지 모르겠지 않는가? 이렇게 어렵게 써있는 말을 이해하는데 꽤나 오랜 시간이 걸렸다. 카이스트-충남대 비밀조직 연결망에 빗대어서 설명을 이어나가도록 하겠다.

⭐️Generic MST알고리즘

비밀조직 연결망을 연결할 때, 다양한 경로가 나올 수 있다. 하지만 최소비용은 명확하다. 최소비용을 만족할 수 있는 여러가지 연결망을 만들 수”도” 있는 것이다.

어쨌던, 최소비용을 만족하는 연결망의 일부를 A라고 하겠다. 그리고 최소비용을 만족하는 연결선들을 safe edge라고 하겠다. 해당 edge들은 MST를 만족하는 선분임을 확실히 보장할 수 있기 때문에 safe-edge라는 용어가 나왔다.

MST-Generic-Algorithm

A = 0
while A가 MST를 형성하지 못하는 동안...
	A에 대한 safe edge를 추가한다
	A = A U {(u,v)}
return A

그렇다. MST를 형성할 때 까지, safe edge를 계속 추가해 나가면 MST를 완성할 수 있다. 그리고 이 safe edge를 추가하는 방법이 두가지가 있고, 이 두가지가 익히 아는 크루스칼과 프림의 알고리즘이다.

그리고 이를 관통하는 한가지 원리가 바로 앞서 설명한 내용이다. 조금 더 덧붙여서 설명을 이어나가겠다.

위와 같이 연결되지 않은 두 그룹이 있다. 모든 vertex V에 대하여, S그룹과 V-S그룹으로 나눌 수 있는 것이다. 이렇게 서로 연결되어있지 않을 때 이 두 그룹을 나누는 선분을 cut이라고 한다.

이렇게 보면 확실히 cut 되어있는 것임을 알 수 있다. S 와 V-S가 나뉘어있다. 그리고 이 cut의 위를 지나는 edge가 없을 때, 우리는 cut이 그룹A를 respect한다고 하는 것이다.

쉽게말해, 충남대랑 카이스트가 나뉘어져있다는 것이다. 그리고 카이스트는 충남대를 존중해 주고, 충남대도 카이스트를 존중해 주는것이다. Respect!!

이 때, cut위를 지나가는 경로중 가장 작은 값을 light edge라고 한다. 그리고 이 light edge는 safe edge이다.

🤔이에대한 증명(클릭)

MST T가 A를 포함한다고 가정한다.

🚀Case 1) MST T가 (u, v)를 포함하고 있다. 자명하다.

🚀Case 2) MST T가 (u, v)를 포함하고 있지 않다. 이러한 경우에는, A U {(u, v)}를 포함하는 새로운 MST T’를 만들어서 증명한다.

그렇다. case2에 대해서만 확인하면 된다.

Tree에서는 각 Vertex와 Vertex 사이의 Path가 모두 Unique하다. 즉, T는 MST이므로, u에서 v까지의 모든 Unique Path를 가지고 있다. 예를 들어, u에서 v까지 가는 Path p에서는 Cut (S, V - S)를 건너가는 Edge가 최소한 하나 있어야 한다. Path p에 위치한 Cut을 지나는 Edge를 (x, y)라 가정한다. 알고리즘이 Edge (u, v)를 골라줬다는 것은 w(u, v) <= w(x, y)라는 것을 뜻한다.

그러니까, 당연히도 알고리즘이 골라준 light edge는 w(x,y)보다 무조건 작다는 것이다.

(u, v) Edge 사이의 점선을 제외하고는 나머지 Edge들은 모두 T에 포함되는 Edge들이다.Set A는 현재 T의 Edge의 Subset이며, 아직까지는 Cut (S, V - S)를 건너가는 Edge를 포함하지 않은 상태이다.

이는 Set A가 아직 Cut을 Respect하기 때문이다. Set A는 Cut을 Respect한다는 것은 Edge (x, y)는 현재 Set A에 존재하지 않는다는 것을 의미한다.

따라서, MST T’을 만들기 위해서는

MST T에서

i) Edge (x, y)를 제거한다 => T를 2개의 Component로 나눈다. ii) Add (u, v) => 2개의 Component가 다시 연결된다.

결론적으로, T’ = T - {(x, y)} U {(u, v)}이고 T’은 Spanning Tree이다.

w(T’) = w(T) - w(x, y) + w(u, v) <= w(T) 즉, 위에서 알고리즘은 Light Edge를 골라야 한다는 전제조건에 의해서 (x, y)보다 (u, v)를 먼저 선택했다는 것은 (u, v)가 더 작은 Weight를 가진 Edge임을 의미하여 w(u, v) <= w(x, y)을 도출하였다.

결론적으로, T’는 Spanning Tree이며 w(T’) <= w(T)를 만족한다. 따라서, T가 MST라면 T’도 MST일 것이다. 해당 (u, v)가 추가되는 것이 Safe한지 조건을 다시 체크해보자면, A는 T의 부분집합의 Edge만 가지고 있었다. 현재는 MST T’의 (u, v)가 추가되었으므로 Safe하다.

따라서, 보라색 선분중 weight가 가장 작은 값이 safe edge가 아니라면, 이미 연결된 각 학교간의 연결망이 safe edge들이 아니라는 것이다. 따라서 충남대, 카이스트가 각각 최소비용으로 잘 연결되어 있다면, 보라색 선분중 가장 작은 값이 safe edge임을 보장할 수 있는 것이다.

⭐️Generic MST알고리즘의 결론

그렇다. 우리는 두 그룹을 연결시킬 때, greedy하게 선택해도 무조건 safe edge이다. (증명 다 읽었다고 가정..ㅎㅎㅎ)

그렇다. 정부 예산을 쓸어오기 위해, 문지캠퍼스, 정부청사의 몇몇 부서와 카르텔을 만드려고 한다. 이때도, 가장 최소비용이 드는 경로(= light edge)를 선택하면 MST를 만족하는 경로를 만들어 나갈 수 있는 것이다.

이렇게 greedy하게 선택해도❗️ 전혀❗️ 문제가 없기 때문에❗️ 크루스칼과 프림 두가지 알고리즘이 성립 될 수 있는 것이다. 이 하나의 사실을 알았다면, 다 끝났다. 크루스칼과 프림 알고리즘에 대해 빠르게 정리하고 넘어가겠다

🚀크루스칼 알고리즘

알고리즘 내용, sudo-code, 시간복잡도, 장단점 순으로 설명해 보겠다.

1️⃣..알고리즘 내용

1. 각 vertex는 자기 자신만 포함한 Component로 시작
2. Light-Edge를 사용하여, 2개의 Component를 1개의 Component로 Merge
3. Edge의 Set중 가장 작은 Weight부터 순차적으로 순회
4. Component간의 Edge연결유무판단 → Disjoint-set 자료구조
   1. Disjoint-SET자료구조는 Union-find 라고 불리기도 함
   2. Union(c1,c2): Component c1과 c2를 하나의 Componenet로 합쳐주는 함수
   3. Find(c1, c2): Component c1과 c2가 연결되어있는지를 확인하는 함수

2️⃣..sudo-code

Kruskal Algorithm (sudo-code)

def 크루스칼알고리즘(노드,엣지,가중치) -> sequence :
	A <- 0
	for 모든 vertex에 대하여,
		do set(v)
	
	sort 오름차순(엣지, key = weigh)
	for 정렬된 모든 (u,v)에 대해:
		if Find-Set(u) != Find-Set(v):
			A <- (u,v) #(u, v)를 safe edge에 추가
			Union(u,v) #묶어벌이기
	
	return A

3️⃣..시간복잡도

따라서 시간복잡도는 도합 O(Elog^E) 이다

🚀프림 알고리즘

알고리즘 내용, sudo-code, 시간복잡도, 장단점 순으로 설명해 보겠다.

1️⃣..알고리즘 내용

1. set A를 통해 “하나”의 Minimum SpanningTree를 만들어 갈 것이다
2. 임의의 Root r로부터 알고리즘을 수행한다
3. 각 Edge에 대해서 순회할 때, (A, V-A)에 대해서 Light Edge를 추가한다
4. Light Edge를 비교하기 위한 Vertex를 추출하기 위해서 Priority Queue를 사용
   1. Priority Queue에는 V-A의 Vertex가 추가된다
   2. 실제 Light Edge의 Weight 비교는 Key[v]를 통해 진행
5. key[v]의 경우에는 각 Cut에 있는 Edge의 Weight를 계산하기 위해 존재
   1. 알고리즘에서 선택되는 v는 아직 set A에 포함되지 않았기 때문에, key[v]는 cut사이에서 가장 작은 Weight의 Edge를 찾기 위해서 사용된다

🚀small tip!!

• 여기서 잠깐!! nil 과 null 차이
  • nil : 클래스 객체를 참조하는데 사용
  • null: 그 밖의 다른 포인터 자료형

2️⃣..sudo-code

Prim Algorithm (sudo-code)


def 프림알고리즘(노드,엣지,가중치) -> sequence :
	Q <- 0
	for 모든 vertex에 대하여,
		key[u] <- (거리)무한대
		부모노드[u] <- NIL
		우선순위큐에 <- (Q,u)삽입 
	key[루트] = 0
#이제 초기화가 끝남

#루트를 기준으로 그래프 그리기 시작
	while Q != 0:
		u <- 최소값 Q추출
		for 모든 v의 인접한 u에 대하여
			if w(u,v) < key[v]:
				(v의 조상님) <- u
				우선순위큐에서 w(u,v)리턴
				key[v] = w(u,v)로 업데이트

3️⃣..시간복잡도

따라서 시간복잡도의 합은 O( ElogV )이다. 여기서는 BST(이진트리)로 만들었다. 하지만 피보나치 힙을 사용하면… O( VlogV + E ) 가 된다. Amortized Time이 O(1)을 만족하기 때문에, key감소 연산 때 시간을 줄일 수 있기 때문이다. (하지만… 피보나치힙은 구현이 너무어렵다ㅠㅠ) 나는 느리더라도 걍 BST쓸래

우리는 이제 MST에서 단 하나의 중요한 사실을 알았고, 이에서 파생되는 두가지 알고리즘을 알게 되었다. 그리고 이 알고리즘의 구현방법과 시간복잡도에 대해서도 정리를 하였다. 또한 문제의 형태에 따라, 그래프의 모양에 따라 시간초과가 날 수도 있고, 빠르게 풀릴수도 있음을 알게되었다. 한번 이를 오늘배운 용어들로 가볍게 정리를 하고 글을 마치도록 하겠다.

☕️크루스칼과 프림의 장단점 정리

Prim은 하나의 트리가 spanning해나가지만, Kruskal은 V개의 set A들이 spanning 해 나가면서(인수합병 해가며..) 하나의 트리를 만들어낸다.

BST(이진트리)를 안쓰면 Prim은 O(ElogV) 이고, Kruskal은 O(ElogE)이다. 따라서 정점의 수가 적으면 프림을 쓰고, 간선의 수가 작으면 크루스칼을 쓰면 된다. 조금 바꿔서 말하면, Vertex보다 Edge가 훨신 많은 Dense한 graph에 대해서는 프림을 사용하고, Vertex가 edge보다 많은 Sparse한 graph에 해해서는 크루스칼을 사용하면 된다.

☀️Sunny의 총 정리

우리는 충대-카이 카르텔을 만들어 나가며, cut을 건너는 light edge가 safe edge임을 확인했다. 그리고 이를 어려운 말로 바꾸면

MST를 만족하는 그룹 A를 respect하는 G의 cut에 대해, light-edge(u,v)는 A에 대해 Safe edge를 보장할 수 있다.

맞다. 위와같은 결론을 얻을 수 있었다. 이 결론으로 부터 얻어낸 두가지 알고리즘은 아래 두가지이다.

크루스칼에서는... 드래곤볼 마냥 흩어져있는 set A에 대해, cut을 건너가는 light edge들을 통해 주변의 setA들끼리 통합 해 나갔다.

프림에서는... 하나의 A를 기준으로, (S, V-S)를 건너가는 light edge들을 갱신해 나가며, 점점 주변 지역을 통합해 나가다가, 세계정복까지 이루어 내는, 그러한 양상을 띄었다.

그렇다!!! 엣지들을 기준으로 최소값을 찾아나가기 때문에, sparse할수록 크루스칼이 유리하고, 프림은 Priority Queue속의 V들을 기준으로 지역짱을 잡아나기 때문에 Dense한 그래프구조에서 강점을 보이는 것이다.

😝마치며..

당최 이해가 안되었던 어제 새벽 3시의 나를 떠올리며 같은말을 반복하면서 이번 적었다. 같은 언어로 피로감을 느꼈다면… 당신은 이미 Go-Su!!

---

😵배우면서 깨달은 내용을 정리해 보았습니다. 틀린 것 같은 개념을 아래 댓글에 달아주시면 감사합니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

swjungle survive 카테고리 내 다른 글 보러가기