ps:최소_신장_트리
목차
최소 신장 트리 (Minimum Spanning Tree / MST)
- 기본적인 내용은 위키피디아 참고
- 최대 신장 트리는, 웨이트에 모두 마이너스를 붙인 그래프에서 최소 신장 트리 찾는 방식으로 찾을수 있다.
알고리즘
- 최소 신장트리를 푸는 알고리즘은 다양하지만, 기본적으로 배우는 알고리즘은 Kruskal's algorithm과 Prim's algorithm.
- Kruskal's algorithm은 기본적으로 O(|E|log|V|)이다.
- Disjoint Set이 필요해서, 전체 코드는 prim보다 좀더 길어진다. 하지만, Disjoint Set을 제외한 구현 부분은 prim보다 짧고, 이해도 더 간단하다.
- 인접리스트 형태로 그래프를 만들어서 넘겨줄 필요가 없다. 그냥 엣지 리스트를 갖고서 돌리면 된다.
- 엣지들을 소팅하는 데에 O(|E|log|E|) = O(|E|log|V|) 가 걸리고, 각 엣지들을 유니온하는데에 O(|E|*α(|V|))이 걸려서 저런 시간복잡도가 나온다.
- 만약 Edge들이 이미 소팅되어있다면, O(|E|*α(|V|)) 으로 푸는 것이 가능해진다
- 최악의 경우에는 |E|개의 엣지를 모두 봐야 하지만, 보통은 그것보다 더 적은 수의 엣지만 보게 되는 경우가 많다. 그럴 경우에는 모든 엣지를 소팅하는 것보다, 우선순위큐에 넣고 하나씩 꺼내서 쓰는것이 더 빠를수도 있다.
- Prim's algorithm은 기본적으로 O(|E|log|V|)이다. (바이너리 힙을 사용하는 경우)
- 피보나치 힙을 쓰면 O(|E|+|V|log|V|)로 단축시킬수 있는 것이 이론적으로 증명 가능하지만, 피보나치 힙은 바이너리 힙보다 매우 느리기 때문에, 실질적으로 속도 향상을 보려면 V가 매우 커져야 한다. 따라서 이것은 그냥 염두하지 않는 것이 낫다.
- 만약 Edge들의 코스트가 몇가지로 한정되어 있다면, 바이너리 힙을 단순 배열로 바꿔서 O(|E|)에 풀 수도 있다. 하지만 이경우에는 Kruskal's algorithm에서도 카운팅 소트를 써서 역시 O(|E| α(V))에 풀수 있긴 하다.
- 힙 대신 그냥 배열을 써서 구현할 경우에는 O(|V|^2)인데, |E|=O(|V|^2)인 dense graph에서는 오히려 이편이 더 시간복잡도가 유리하다.
- 실제로 구현해서 테스트해본 결과는, 대부분의 경우 Kruskal이 Prim보다 속도도 빠르고, 변형해서 다른 문제에 활용하기에도 유리했다. Prim이 더 빠른 경우는 dense한 그래프에서 O(V^2) 구현을 사용하는 경우인데, V가 500이상은 되어야 Prim이 살짝 빨라지는 정도였다.
- https://en.wikipedia.org/wiki/Minimum_spanning_tree#Faster_algorithms 를 참고하면, 더 효율적인, 심지어 선형 시간에 결과를 내주는 알고리즘들도 많이 있는 것 같다만.. 실제 실용적인 범위 안에서도 정말 속도가 빠른지는 확인 안해봤다.
- 그래서 결론은
- 특수한 경우가 아니라면, Kruskal's algorithm으로 구현해서 쓰도록 하자
- 완전그래프에 가까울정도로 dense한 경우에는 O(|V|^2)버전의 Prim's algorithm을 사용하자
구현
- 위에서 얘기했듯이 Kruskal's algorithm 으로 구현하기로 하고.. 구현 과정에서 생각했던 몇가지 옵션들 정리
- 입력을 엣지 리스트로 받을것인가? WGraph로도 받을것인가? 두가지를 다 구현할것인가?
가중치 있는 그래프에 동작하는 다른 알고리즘들 (다익스트라, spfa 등)은 다 WGraph를 인자로 받는다. 일관성을 위해서는 여기서도 그렇게 해주는 것이 낫지만, 결국 엣지 리스트로 변환해서 처리해야 하니까 비효율적이다. 엣지 리스트를 인자로 받되, 함수 이름을 minimum_spanning_tree_from_edges 라고 만들어서 입력으로 엣지리스트를 받는다는 것을 명확하게 하고, 나중에 필요하면 WGraph를 인자로 받는 minimum_spanning_tree를 추가 구현하자- tgraph.py에서 graph.py로 바꾸면서, 그래프의 표현은 인접리스트/인접행렬/엣지리스트 형태를 모두 지원하고, 알고리즘에 따라서 적합한 형태를 받는걸로 바뀌었다. 따라서 여기에서는 당연히 엣지리스트를 정의한 EdgeWGraph타입을 인자로 받는다. 함수 이름도 굳이 from_edges를 붙일 필요 없이, 그냥 minimum_spanning_tree로 쓰기로 했다.
- (참고: EdgeWGraph는 항상 undirected 이다)
- 엣지 리스트를 sort한뒤 쓸것인가? 힙에 넣고 쓸것인가? 두가지 버전을 다 구현할것인가?
문제에 따라서 정렬이 빠른것도 힙이 빠른것도 있다. 하지만, 정렬이 빠른 경우에는 힙보다 큰 차이는 안났었고, 힙이 빠른 경우에는 차이가 크게 나는 경우가 있었다. 힙으로 구현하자- 전체를 sort하는 것으로 하자.
- 그래프가 dense할 경우에.. 전체 엣지의 갯수 E에 비해서, mst를 구성하는 엣지를 찾는데 필요한 엣지의 수 E'이 작을 경우에는, 정렬해서 찾는 ElogE보다, 힙을 이용해서 상위 E'개의 노드만 정렬하는 E+E'logE 방법이 더 빠른 경우도 있기는 하다
- 그러나 많은 경우에 전체를 정렬하는 것으로 충분하다. 게다가 이제는 라이브러리 구현상으로도 힙을 이용하려면 오버헤드가 더 걸린다. 이전에는 이 함수에서만 엣지 리스트를 인자로 받게 했기에, 엣지의 표현을 편한대로 (w, u, v)순으로 저장하게 할수 있었고, 그 경우에는 바로 힙에 넣을수 있었다. 이제는 (u,v,w)순으로 저장된 EdgeWGraph 타입을 인자로 받으므로, 힙에 넣기 위해서는 순서를 바꾸어서 리스트를 새로 만들어야 하고, 이경우에 속도 페널티가 생긴다.
- 전력난에서, 힙 버전으로는 2400ms, 정렬 버전으로는 1448ms가 걸렸다.
- 엣지들이 이미 소팅되어 있는 경우는 어떻게 지원할것인가?
- 추가 인자로 받을수도 있고, 별개의 함수를 만들수도 있는데.. 필요한 경우가 많지는 않은것 같아서 그냥 라이브러리에서는 따로 지원하지 않는걸로. 필요한 경우에 그때그때 구현하도록 했다. 이미 소팅된 리스트를 한번 더 소팅한다고 속도상 큰 차이가 있을거 같지도 않다.
- dense그래프를 위한 O(|V|^2)버전의 Prim's algorithm 을 따로 제공할것인가?
이것도 필요한 경우를 거의 못봐서 라이브러리에서는 지원하지 않기로. 필요하면 그때그때 구현하도록.- 유클리디안 MST를 포함해서, 완전그래프에 대해서 돌려야 하는 경우가 간혹 있기는 하다. |V|가 커질경우에는 Prim이 조금 더 빨라지는데, 사실 큰 차이는 아니다.
- 별자리 만들기: |V|≤100, Krusal 76ms, Prim 108ms
- Arctic Network: |V|≤500, Krusal 484ms, Prim 356ms
- 우주신과의 교감: |V|≤1000, Krusal 756ms, Prim 508ms
- (프림의 구현은 좀더 최적화할 여지가 있기는 하다)
- 오히려 장점은, V^2 개의 엣지들을 모두 다 만들 필요없이 view를 이용해서 메모리를 아낄수 있다는 점일지도 모르겠다.
- teflib.graph.minimum_spanning_dense 로 구현해 두긴 했는데, 딱히 효율이 없다고 생각되면 없애는 것도 고민중.
- 리턴값을 최대신장트리 전체를 리턴할것인가, 최대신장트리의 웨이트의 합을 리턴할것인가
- 이건 좀 중요하다. 대부분의 문제에서는 웨이트의 합만 필요로 하고, 이 경우에 최대신장트리 전체를 리턴하는 것은 리턴받은 다음에 웨이트 합을 수동으로 계산해야하는 불편함을 요구한다. 하지만, 정말로 최대신장트리가 어떻게 생겼는지를 구해야 하는 경우도 있다. 이런 경우를 라이브러리에서 지원하지 않는것이 맞는것인지도 고민할 문제이다
- 다른 함수들과의 일관성 면에서도 신경써야 한다. 예를들어 이분매칭 함수에서 최대 매칭 크기만 리턴하는것 vs 매칭 페어들을 리턴하는것. 또는 최단경로 알고리즘에서, 최단경로의 길이를 리턴하는것 vs 경로 전체를 리턴하는것과 같은 고민거리와 비슷한 부분이라 일관성이 필요하다.
- 어느정도 가능한 후보는..
- 1) 웨이트 합만 리턴하고, 최대신장트리 자체를 구해야 하는 문제는 라이브러리에서 지원하지 않는다
- 2) 최대신장트리 자체를 리턴하고, 웨이트 합이 필요하면 거기에서 추가로 구하도록 한다
- 3) 웨이트 합과 최대신장트리를 둘다 만들어서 페어로 리턴한다
- 4) 웨이트 합을 리턴하는 함수와 최대신장트리를 리턴하는 함수, 두가지를 모두 제공한다.
- 고민끝에 처음에 1)로 만들었던것을 2)로 바꾸도록 했다. 최대 신장트리에서 웨이트 합을 다시 계산하더라도 코드상에서는 1줄정도 추가해서 해결되고, 속도 저하도 미미하다. 리턴타입도 EdgeWGraph 를 사용하도록 했다.
- 전력난 기준으로 1448ms에서 1480ms로 증가.
- 실제 문제들
- 최대신장트리 자체가 필요한 문제들: 도시 분할 계획,
코드
벤치마크
라이브러리를 직접 사용하지 못한 문제
기본 관련 문제
- 네트워크 연결 가장 기초. V≤1,000, E≤100,000
- 최소 스패닝 트리 가장 기초. 음의 가중치도 있지만, 알고리즘이 바뀔 필요는 없다. V≤10,000, E≤100,000
- 완전그래프의 최소 스패닝 트리 V≤10,000인 완전그래프
유클리디안 최소 스패닝 트리
- 주어진 점들을 연결하는 최소 스패닝 트리를 만드는 문제이다. 가중치는 점들간의 유클리디안 거리로 주어진다.
- 기본적인 방법은 모든 점들간에 엣지를 추가해서 완전 그래프를 만들고, 거기에서 MST 알고리즘을 돌리는 것이다. 위에 얘기했듯, 완전그래프에서는 O(ElogV)의 크루스칼 알고리즘보다, O(V^2)의 프림 알고리즘이 더 효율적이다.
- 유클리디안 거리를 갖고서 뭔가를 할때의 일반적인 요령은, 루트를 씌우지 않은 거리^2 값만 계산해서 그것으로 비교를 하고, 마지막에 최종 값을 구할때에만 루트를 씌우는 것이다. 당연히 MST를 구할때도 가능하다. 하지만, 그렇게 하는 것보다도 그냥 math.dist를 사용해서 처리하는 것이 실제로는 더 빠르다.
- 하지만 더 효율적인 방법은, 들로네 삼각분할을 O(nlogn)에 수행해서 O(n)개의 엣지만 남긴 다음에 그것들을 대상으로 MST를 O(nlogn)에 찾는 것이다. 총 시간복잡도는 O(nlogn)이다
- MST에 해당되는 엣지들이 들로네 삼각분할로 만들어진 부분그래프 안에 반드시 포함되기 때문에 이 방법이 가능하다 (왜 항상 포함되는지 이유는 안찾아봤다.)
- 관련된 좀더 자세한 내용을 https://algoshitpo.github.io/2020/05/20/EMST/ 에서 찾을수 있다.
- 좀더 조건이 추가되면 O(nloglogn)에도 가능하다고 한다.. 자세한건 위키를 읽어보자.
Directed MST
- 방향그래프에서도 MST를 정의하고 구할수 있다고 한다. 제대로 공부은 안해봤지만 일단 참고 링크만 붙여둠..
- https://gina65.tistory.com/23 - O(VE) 알고리즘
- https://koosaga.com/265 - O((V+E)logE) 알고리즘
최소 병목 신장 트리 (Minimum bottleneck spanning tree)
- 스패닝 트리 중에서, 웨이트의 최대값을 최소로 하는 트리를 최소 병목 신장 트리라고 한다.
- 최소 신장 트리는 항상 최소 병목 신장 트리가 된다. 따라서, 최소 병목 신장 트리를 찾고 싶을때에도 그냥 최소 신장 트리 알고리즘을 돌려서 구하면 된다.
- Camerini's algorithm 를 이용하면, 최소 병목 신장 트리는 O(E)에 구할수 있다. 하지만, 이것은 중간값을 선형시간에 찾는 알고리즘이 필요한데.. 이거를 돌리려면 실질적으로는 그냥 소팅해서 O(ElogE)에 구하는 것보다 느릴거 같은 느낌.
- 하지만 역은 성립하지 않는다. 최소 병목 신장 트리가 항상 최소 신장 트리가 되는것은 아니다.
Bottleneck shortest path problem
- 경로에 포함되는 엣지들 중 가장 작은 가중치를 갖는 엣지의 가중치가 최대화되는 경로를 찾는 문제를 Widest path problem, 반대로 가장 큰 가중치를 갖는 엣지의 가중치가 최소화되는 경로를 찾는 문제를 minimax path problem 또는 Bottleneck shortest path problem이라고 한다고 한다.
- 해법은 간단하다. Bottleneck shortest path는 최소 병목 신장 트리 안에 존재하게 된다. 이론적으로는 최소 병목 신장 트리를 먼저 구하고, 그 안에서 구하려는 s→t 경로를 bfs나 dfs를 돌려서 구하면 된다. 그리고, 실질적으로는 최소 병목 신장트리를 최소신장트리 알고리즘을 통해서 구하게 되기 때문에, 최소신장트리를 만들다가 s→t가 연결되면 거기에서 멈추고, 그 안에서 경로를 찾으면 된다. bottleneck 엣지의 웨이트를 찾는 문제라면, 그때까지 찾은 엣지들의 웨이트중 가장 큰것을 찾으면 된다
ps/최소_신장_트리.txt · 마지막으로 수정됨: 2022/10/18 08:22 저자 teferi
토론