크루스칼 알고리즘과 프림알고리즘의 차이.

신장 트리

 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

최소 신장 트리(Minimum Spanning Tree)

 - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

 

일단 두 알고리즘 최소신장트리(MST)를 만들기 위한 알고리즘이다.

즉, 주어지는 간선의 정보로 최소의 비용을 지불해서 하나의 집합을 만드는 알고리즘이다.

 

크루스칼 알고리즘

크루스칼 알고리즘은 정점에 비해 간선의 개수가 적을때 MST(최소신장트리)로 만들기에 적합하다.

Union-Find 알고리즘(혹은 상호배타적 집합(Disjoint-Set)알고리즘)을 선행학습해야한다.

 

로직은 다음과 같다.

 

1. parents테이블을 각자의 값으로 초기화시킨다.

  -> parents테이블은 각자의 정점이 어떤 정점을 부모로 하고있는지 관리하는 테이블이다.

      초기에는 자기자신으로 초기화시켜놓는다.

 

2. 간선을 가중치값기준으로 오름차순 정렬을 한다.

->  최소비용으로 트리를 만드는게 목적이기 때문이다. 작은비용의 간선부터 시작해서 트리를 만들어 나가기 때문에 최소       신장트리인 걸 보장받을 수 있다.(..라는 의도로 시작된 알고리즘이 아닐까 한다.)

 

     당연히 정렬속도는 간선개수가 적을수록 빠르다.

     C++에선 보통 algorithm.h에 포함된 sort함수를 사용하게 될 텐데, 이 함수는 quickSort로 작성되어 있다고 한다.

      quickSort의 시간복잡도는 nlogn 이다.

     크루스칼에서는 간선의 개수가 n이니까 E logE 라 표현해도 맞는 표현이다.

 

3. 반복문 돌면서 해당 간선이 사이클인지 검사한다.

->  매번 간선을 트리에 포함시키려고 할 때마다 사이클 검사가 필요하다.

     사이클검사란, 선택한 간선의 시작지점 노드와 도착지점 노드의 부모가 같은지 검사를 해주는 것이다.

     Union-Find 알고리즘 중 Find를 수행한다. 각자의 부모가 같으면 return true, 아니면 return false.

 

     왜 사이클 검사를 해야할까?

     이 알고리즘의 목적은 '최소비용'으로 하나의 집합을 형성하는 것이다.

     이미 두 원소가 같은 집합인데 굳이 비용을 더 지불하고 연결을 할 필요가 전혀 없다.

      

4. 사이클을 이루지 않는다면(시작정점과 도착정점이 같은 집합이아니라면) 합친다.

  ->  같은집합 아니니까 같은집합으로 만들기 위해 합쳐준다.

       Union-Find 알고리즘 중 Union을 수행한다. 

       먼저 각자의 부모번호를 알아낸다. 그다음 번호가 더 작은쪽이 상위라고 기준을 잡았을 때,

       '부모번호가 큰쪽의 부모번호'를 '부모번호가 작은쪽의 부모번호'로 업데이트시킨다.

        

       만약 그래프말고 비용까지 구해야하는 문제면 이때 비용도 같이 더해주면된다.

       그러면 끝.

     

시간복잡도 

크루스칼알고리즘의 시간복잡도는 처음에 가중치값 기준으로 정렬을 할 때 의존한다.

보통 퀵소트를 사용하며, 퀵소트의 시간복잡도는 평균적으로 nlogn 이다.(최악의 경우는 n^2 이지만, '평균적'으로 nlogn)

정렬이후에는 간선의 개수만큼(O(E)) 사이클검사(O(1))를 하지만, 정렬에 비해 매우 적은 시간이기 때문에 고려하지 않는다. 크루스칼에서는 간선의 개수가 n이니까 E logE 라 표현하기도 한다.

 

 

                                                                                                                                                                                                 

프림 알고리즘

정점에 비해 간선이 많을 때 MST로 만들기 적합.

    -> 크루스칼과 다르게 정점을 기준으로 간선을 선택하기 때문.

        모든 간선을 다 탐색할필요가 없다. 최소거리의 간선만 선택.

 

크루스칼알고리즘에서 했던 사이클체크를 어떻게 하는가?

-> 프림알고리즘에서는 해당노드를 방문체크함으로써 사이클을 방지한다.

 

minHeap 우선순위큐를 사용한다. 가중치가 제일 작은 노드(정점)을 우선으로 꺼낸다.

 

로직은 다음과 같다.

1. 아무 노드를 큐에 넣는다.

    -> 여기서 노드는 정점번호와 가중치값을 가지고있는 구조체다.

        만약 처음넣은 노드의 정점이 1번이라면, Node(1,0)이 된다. (자기자신은 가중치가 0이니까)

2. 큐에서 노드를 꺼낸다. 

     ->  꺼낸 노드가 방문한적 있는지 체크. 방문 안했었으면 방문체크 한다음, 가중치값 누적시킨다.(sum += 가중치)

          그래프에서 꺼낸 노드의 정점과 연결된 인접정점들을 노드로 만들어서 큐에 삽입.

           2번과정을 큐가 비워질때까지 반복.

          혹은 방문한 노드개수를 카운팅하다가 전체정점개수와 같아지면 바로 반복문을 종료시켜도 된다.

      

 

방문체크를 하는 알고리즘에서 큐를 이용할 때, 바로 위에있는 로직처럼 꺼낸 다음 방문체크를 하는식으로 해도 되고,

아예 큐에 넣을 때 방문체크를 해서 방문한적 있는거는 큐에 안넣어버리게 짤 수도 있다.

방문체크자체는 O(1)의 시간밖에 걸리지 않으니 그냥 큐에 넣을때 검사해서 큐에 너무 많이 넣는걸 방지하는것도 좋다.

 

시간복잡도 

프림알고리즘의 시간복잡도는 E log V 이다. 이것은 트리에 포함된 노드들 중에 최소거리값을 찾는 노드를 찾을 때, 어떤 자료구조를 사용하느냐에 의존한다. E log V는 우선순위큐를 사용할 때의 시간복잡도이며, unsorted-array, 즉 정렬되지않은 배열을 이용하여 일일이 탐색할 경우 시간복잡도는 n^2 까지 오르게 된다.

 

이해하기 쉽게 이미지로 로직 보고 싶으면 아래 블로그로.. 잘 정리해놓으셨다

https://wondy1128.tistory.com/98?category=666635