신장 트리(Spanning Tree)

※ 신장 트리(Spanning Tree): 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

최소 신장 트리: 신장 트리 중 가중치가 가장 작은 신장 트리

  최소 신장 트리 찾는 알고리즘의 대표적인 예시) 크루스칼 알고리즘

 

※ 크루스칼 알고리즘(Kruskal Algorithm) - 그리디 알고리즘, 서로소 집합 개념 사용

   ① 간선 데이터를 가중치에 따라 오름차순으로 정렬

   ② 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인

       ⁎ 발생시키지 않는 경우 신장 트리에 포함

   ③ 모든 간선에 대하여 ①과 ② 과정을 반복적으로 수행

 

최종적으로 최소 신장 트리에 포함되는 간선의 개수 = N-1 (N은 노드의 개수)

 

• 최소 비용: 최소 신장 트리에 포함된 간선의 가중치 합

• 크루스칼 알고리즘의 시간복잡도: O(ElogE) (E는 간선의 개수)

  - 크루스칼 알고리즘의 시간복잡도는 간선을 가중치에 따라 정렬하는 시간을 따라간다.

   (정렬 외의 다른 과정은 정렬보다 시간 복잡도가 작으므로 무시)

 

 

 

출처| 이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)