[MST] Prim & Greedy

MST 중 prim알고리즘은 그리디알고리즘을 만족하는 몇 안 되는 알고리즘이다.
여기서 mst = minimum spaning tree로 최소신장트리이다.

신장트리 중 가중치의 총합이 가장 최소임을 의미한다.
특징으로는

1. 간선의 가중치의 합이 최소여야 한다.
2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1) 개의 간선만을 사용해야 한다.

노드 1번에서 가질 수 있는 간선의 수 : 2(N-1)
노드 2번에서 가질 수 있는 간선의 수 : 2(N-2)
노드 3번에서 가질 수 있는 간선의 수 : 2(N-3)

이를 모두 더하면

2(N-1 + N-2 + N-3 + .... + N-N)
2*(N^2 - (N(N+1)/2))
E = N(N-1)
이다.

이때 prim알고리즘은 현재 보이는 것 중 가장 좋은 (최소 or 탐욕적인)해를 택한다.
prim은

selected[MAX_VERTEX]
distance[MAX_VERTEX] 이다.

여기서 그리디로 간선을 고를 때 큰간선을 골랐을 때, 더 시간이 빠를 수도 있지 않을까? 에 관한 의문을 품을 수 있다.

이는 그림을 보고 이해 할 수 있다.

그런 경우는 수학적으로 증명되어 있고 절대로 그럴 일 이 없다.

따라서 제일 작은 경우를 골랐을 때, 최소가 된다.

보면, 최소값을 고를 때, 더 큰 간선보다 그거를 골라야
그 노드를 다시 갈 때 더작게 갈 수 있는 경우의 수가 생기고 더 작게 갈 수 있는 방법이 있다.
왜냐면 distance리스트에 최소로 작아지는 값을 update하면서 계속 기록하고 있기 때문이다.
따라서 이를 통해 고른 vertex들은

최단거리로 이은상태가 된다.

 

이때 시작정점으로부터 트리집합으로 뻗어나가기 때문에 이 그래프는 사이클이 없는 Tree 모양이 된다. 

또한, 이런 간선의 값을 heap == 즉, minimum heap ==  minimum tree로 구성하여 가지고 있으면서 

root node를 항상 뽑아서 mst를 완성시켜야 

원래 알고있는 시간복잡도 O(E*log(E)인 복잡도를 지닌다.

위에서 말한바와 같이 E = N(N-1) 최대 이 정도의 크기를 가진다.

이는 

kruskal알고리즘을 적용시켰을 때 얘기이다.

 

prim알고리즘은 

주 반복문이 정점의 수 n만큼 반복하기에, prim 알고리즘 o(n^2) == o(v^2)의 시간복잡도를 지닌다.

kruskal = O(E*log(E) prim = o(v^2) = O((V + E)logV)

prim은 인접행렬을 사용하면 o(v^2)
우선순위 큐를 사용하면 O((V + E)logV)

 

따라서 우선순위큐를 사용하느냐에 따라서 시간복잡도가 많이 차이 난다.

이때, kruskal알고리즘은 union-find알고리즘을 사용한다.