그래프 이론: 신장 트리

01. 정의

하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

(모든 노드를 포함되어 서로 연결되면서, 사이클이 존재하지 않는 그래프 == 트리)

 

02. 최소 신장 트리

신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘

 

03. 크루스칼 알고리즘

과정

 

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대하여 2번의 과정을 반복한다.

 

특징 

▶ 크루스칼 알고리즘은 거리가 짧은 간선부터 취하는 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다.

▶ 최종적인 신장트리에 포함되는 간선의 개수는 노드의개수-1 이다. (사이클이 발생하지 않으므로)

 

시간복잡도 (E: 간선개수)

▶ O(ElogE) 

크루스칼 알고리즘은 간선을 정렬하는 작업이 가장 오래걸리며, 이 때의 시간복잡도가 O(ElogE)이다. 크루스칼 내부에서 사용되는 서로소 집합 알고리즘의 시간복잡도는 이보다 작기 때문에 무시한다.

---

공부하는 책 및 내용 출처

 

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=247882118

이것이 취업을 위한 코딩 테스트다 with 파이썬