210708 최소 신장 트리 with Kruskal, Prim 알고리

최소 신장 트리 (Minimum Spannig Tree, MST)

신장 트리(spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리

 

//신장 트리(spanning Tree) : 모든 정점을 포함하고, 정점 간 서로 연결이 되며 사이클이 존재하지 않는 그래프

 

 

Kruskal, Prim 알고리즘은 최소 신장 트리를 구하기 위한 알고리즘 

 

Kruskal

 

모든 간선들 중에서 가중치가 가장 낮은 간선부터 선택하는 방식

단, 선택하는 과정에서 사이클이 만들어지는 경우에는 선택하지 않는다

n개의 정점을 가지는 그래프일 경우, n-1 개의 간선 선택하면 종료

 

시간복잡도 : 간선을 오름차순으로 정렬하는 것에 수행시간 좌우되기에 최선의 선택을 한다고 가정하면,

O((간선의 수) * log_2 (간선의 수)

 

예시

 

 

Prim

 

prim 은 kruskal 과 다르게 시작 노드를 가지고 인접 간선들 중 가중치가 가장 낮은 간선부터 선택한다.

간선을 선택함으로서 확장된 트리에서 가중치가 낮은 인접 간선을 선택하는 과정을 반복하며, 트리를 유지한 채로 확장해 나가 완성한다.

 

 

시간 복잡도 :  인접리스트와 우선 순위 큐를 활용한 경우

• 우선 순위 큐의 push/pop 연산에 O(log (정점의 수))
• push / pop 연산이 최대 간선의 수 만큼 수행

고로 O( (간선의 수) * log (정점의 수))