Dasol Hong

I am a master’s student advised by Professor Hyun Myung at KAIST (Urban Robotics Lab).

[ALGO] Lect11. 최소신장트리 문제에 대한 프림, 크루스칼 두 알고리즘

3 minutes to read

강의 정보
강의명: [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고
교수: 성균관대학교 소프트웨어학과 허재필 교수님
사이트: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/course/



이번 시간에는 최소신장트리 문제에 대한 프림, 크루스칼 두 알고리즘에 대해 배운다.


최소신장트리 문제와 프림 알고리즘

그래프에서 발생하는 여러가지 문제들을 해결하는 방법에 대해 알아본다.

Minimum Spanning Trees

■ 정의

image-20210911225434559

Minimum Spanning Tree란 Graph의 모든 nodes가 최소한의 weights로 연결되는 Tree 자료구조이다.


■ 쓰임

각 도시를 연결짓는 도로를 건설하려고 할 때, 건설 비용을 최소화하면서 모든 도시를 연결할 수 있는 길을 찾는 문제에서 Minimum Spanning Tree 자료구조를 사용할 수 있다.


Spanning Tree

image-20210911225919799

Spanning Tree란 Graph의 모든 vertex가 연결되도록 구성된 Tree이다.

  • vertex의 개수가 $V$개일 때, Tree는 언제나 $V-1$개의 edges를 가지므로, Graph로부터 $V-1$개의 edges를 고르는 문제라 생각할 수도 있다.

  • Spanning Tree가 Weighted Tree인 경우, Spanning Tree의 weight는 모든 edges의 weight 합으로 정의된다.

    \[\text{Spanning Tree의 weight} = \sum_{i=1}^{V}{w_i}\]

    ※ Spanning Tree의 weigth를 최소화하는 문제를 Minimum Spanning Tree라고 한다. ※

  • Spanning Tree가 Unweighted Tree인 경우, 모든 edges의 $\text{weigth}=1$이라 가정할 수 있다. 따라서 이 경우 Minimum Spanning Tree의 weight는 언제나 $V-1$이다.


■ 특징

  • Unique하지 않다.

  • $V-1$개의 edges를 선택했을 때, 어떤 vertex를 root로 보느냐에 따라 다른 Tree가 된다.


Algorithms

Minimum Spanning Tree문제를 해결하는 대표적인 알고리즘은 다음과 같다.

  • Prim's Algorithm
  • Kruskal's Algorithm

두 알고리즘 모두 Greedy Algorithm임에도 불구하고 최적의 값을 도출할 수 있음이 증명되었다.

Greedy Algorithm이란?
매 순간 최선의 선택을 취하는 알고리즘


Prim’s Algorithm

개념

$N$개의 vertex를 갖는 graph로부터 minimum spanning tree를 결정하는 방법은 다음과 같다. $k$개의 vertex로 이루어진 minimum spanning tree가 주어졌다면, 기존의 minimum spanning tree에 $k+1$번째 vertex를 추가해나가는 방식으로 $N$개의 vertex를 갖는 minimum spanning tree를 결정할 수 있다.

이때 최소한의 weight를 갖도록 $k+1$번째 vertex를 선택하는 방법은, 기존의 tree에 직접적으로 연결된 edges 중 최소한의 weight를 갖는 edge를 선택하는 것이다.


■ 예시

image-20210911231030263

$e_k$를 minimum spanning tree와 $v_{k+1}$을 연결하는 최소의 weight를 가진 edge라고 할 때, 위 예시에서 $v_{k+1}$을 연결하기 위한 edge로 $e_k$를 선택하는 것이 가장 합리적인지를 생각해보자.

$e_k$를 선택하지 않는다면 다른 어떤 경로($\tilde{e}$)를 통해 $v_{k+1}$으로 연결되어야 한다. 이때 $e_k$가 $v_k$를 연결하는 최소의 weight를 가졌으므로 다른 경로 $\tilde{e}$는 반드시 $e_k$보다 weight값이 클 수밖에 없다. 따라서 $e_k$를 선택하는 것이 가장 합리적인 결정이다.


특징

  • 어떤 vertex에서 시작하든지 상관 없다.


Implementation

■ 배경 지식

  • distance: 현재 minimum spanning tree로부터 어떤 특정 vertex까지의 거리 ※초기값은 ∞. 단, root vertex의 distance=0 ※
  • visit: 해당 vertex가 이미 minimum spanning tree에 포함되었는지를 체크하는 flag ※ 초기값=0 ※
  • parent: 어떤 vertex가 minimu spanning tree에 포함될 때, 어떤 node와 직접적으로 연결되었는가를 체크하는 flag ※ 초기값=NULL ※


■ 알고리즘

  1. minimum distance를 갖는 unvisited vertex를 선택한다.

  2. 해당 vertex를 visited상태로 바꿔준다.
  3. 각 인접 vertex에 대한 distance를 고려하여 기존의 distance값을 업데이트해준다.
  4. ①모든 vertex가 visited상태이거나 ②모든 unvisited vertex의 distance값이 ∞가 될 때 까지 1~3의 과정을 반복한다. ※ ②의 경우 unconnected graph ※


■ 예제

image-20210911231907393


복잡도

image-20210904010142704

최종적으로 Prim’s Algorithm의 복잡도는 $Θ(V^2)$가 된다.


최적화

minimum distance를 구하기에 가장 적합한 자료구조는 min-heap 자료구조이다.

  • min-heap의 nodes의 개수는 $V$개가 된다. ⇒ $Θ(V)$의 memory and run time
  • 최소값을 구하는 데(Pop)에 걸리는 비용은 $\lg(V)$이다.
  • 따라서 최소값을 찾는 데에 드는 총 $(V-1)\lg(V)$가 소요된다. (∵ V-1번 위 과정을 반복) ⇒ $O(V\lg(V))$
  • 최소값을 구한 뒤, neighbors에 대해 distance를 update하는 데에 $E\lg(V)$가 소요된다. (∵ edge만큼 연산되며, 각 update는 $\lg(V)$가 소요됨) ⇒ $O(E\lg(V))$

따라서 total run time은 다음과 같다. \(O(V\lg(V) + E\lg(V)) = O(E\lg(V))\) ※ 이떄 edges의 개수 $E$는 최대 $V^2$의 값을 가질 수 있다. 따라서 edges의 개수가 많은 경우 오히려 min-heap(priority queue)를 사용하지 않는 것이 더 효율적이다. ※



Kruskal’s Algorithm

크루스칼 알고리즘은 프림 알고리즘 보다 간단한 알고리즘이다.

크루스칼 알고리즘은 weight에 따라 edges를 정렬하고, 최소 weight부터 차례로 minimum spanning graph에 추가시켜 나간다. 이때 tree에 cycle이 생기지 않도록(∵ cycle이 생기면 tree가 아니라 graph가 되니까) 추가하는 것이 핵심이다.


■ 예시

image-20210911232526642

  1. graph 내에 존재하는 모든 edges를 weight 순서대로 정렬한다.
  2. 위에서부터 하나씩 순회하며 minimum spanning tree에 삽입 여부를 결정한다.
    1. 해당 edge를 포함시킬 때 cycle이 생성되면 무시한다. (skip)
    2. 해당 edge를 포함시킬 때 cycle이 생성되지 않으면 추가한다. (addition)
  3. 2번 과정을 $V-1$개의 edges를 고를 때 까지 반복한다.


복잡도

  1. edges를 정렬하기 위한 merge sort(or heap sort) : $O(E\lg(E))$
  2. cycle 체크를 위한 DFS(or BFS) : $O(E)=O(V)$ (∵$ E<V$이므로)

따라서 최종적인 run-time은 다음과 같다. \(O(E\lg(E) + E·V)\\ = O(E·V)\ \ (∵ E=O(V^2)\text{이므로 }\lg(E)=\lg(V))\)

특징

  • 프림알고리즘($O(E\lg(V))$ 혹은 $O(V^2)$)에 비해 비효율적($O(E·V)$)이다.

  • 알고리즘이 단순하다.

  • cycle check를 위해 DFS(or BFS) 대신 disjoint set을 사용하면 complexity를 낮출 수 있다.



References

  1. [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고-비선형 자료구조, K-MOOC: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/1158909c057347478d7386a2b7e97214/e9d736660cad4f76bcb9a05974fe0bf2/1?activate_block_id=block-v1%3ASKKUk%2BSKKU_46%2B2021_T1%2Btype%40vertical%2Bblock%4052b62ff6da2147c9a8a65a6056681d91



참고