사용자 도구

사이트 도구


ps:최소_신장_트리

최소 신장 트리 (Minimum Spanning Tree)

  • 기본적인 내용은 위키피디아 참고
  • 최대 신장트리를 푸는 알고리즘은 다양하지만, 기본적으로 배우는 알고리즘은 Kruskal's algorithm과 Prim's algorithm.
  • Kruskal's algorithm은 기본적으로 O(|E|log|V|)이다.
    • Union-Find set 의 구현이 추가적으로 필요해서 조금 번거로운 편.
    • 만약 Edge들이 이미 소팅되어있다면, O(|E|*α(|V|)) 으로 푸는 것이 가능해진다
  • Prim's algorithm은 기본적으로 O(|E|log|V|)이다. (바이너리 힙을 사용하는 경우)
    • 피보나치 힙을 쓰면 O(|E|+|V|log|V|)로 단축시킬수 있는 것이 이론적으로 증명 가능하지만, 피보나치 힙은 바이너리 힙보다 매우 느리기 때문에, 실질적으로 속도 향상을 보려면 V가 매우 커져야 한다. 따라서 이것은 그냥 염두하지 않는 것이 낫다.
    • 그냥 배열을 쓸 경우엔는 O(|V|^2)인데, |E|=O(|V|^2)인 dense graph에서는 오히려 이편이 더 시간복잡도가 유리하다. 근데 실제로 이렇게 푸는 경우를 본적이 없다
      • [TODO] 테스트 및 확인
    • 만약 Edge들의 코스트가 몇가지로 한정되어 있다면, 바이너리 힙을 단순 배열로 바꿔서 O(|E|)에 풀 수도 있다. 하지만 이경우에는 Kruskal's algorithm에서도 카운팅 소트를 써서 역시 O(|E| α(V))에 풀수 있긴 하다.
  • dense한 그래프에서는 Prim이, sparse한 그래프에서는 Kruskal이 좀더 빨리 돈다는 썰도 있긴 한데, 빅오 시간복잡도가 똑같은 이상 그냥 Prim으로 통일해서 쓰는 것이 나을것 같다
  • https://en.wikipedia.org/wiki/Minimum_spanning_tree#Faster_algorithms 를 참고하면, 더 효율적인, 심지어 선형 시간에 결과를 내주는 알고리즘들도 많이 있는 것 같다만.. 실제 실용적인 범위 안에서도 정말 속도가 빠른지는 확인 안해봤다.
  • 그래서 결론은
    • 특수한 경우가 아니라면, 바이너리 힙 기반의 Prim's algorithm으로 구현해서 쓰도록 하자
    • 엣지들이 이미 소팅되어 있거나, 카운팅 소트로 빠르게 소팅이 가능한 경우에는 Kruskal's algorithm을 사용하자
    • (?) 완전그래프에 가까울정도로 dense한 경우에는 O(|V|^2)버전의 Prim's algorithm을 사용하자
  • 대부분의 문제는 MST의 구조보다는, MST를 이루는 엣지들의 가중치 합만 필요한 경우가 많다. 그래서 가중치합만 리턴하도록 함수를 짰다.

코드

토론

댓글을 입력하세요:
A J D H S
 
ps/최소_신장_트리.txt · 마지막으로 수정됨: 2021/06/14 01:58 저자 teferi