크루스칼 알고리즘
위키백과 ― 우리 모두의 백과사전.
크루스칼 알고리즘(Kruskal's algorithm)은 최소 비용 걸침 나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭지점의 개수를 V라고 하면 이 알고리즘은 O(E log V)의 시간복잡도를 가진다.
[편집] 알고리즘
크루스칼 알고리즘은 아래의 순서대로 작동한다:
- 그래프의 각 정점이 각각 하나의 트리가 되도록 하는 포레스트 F을 만든다
- 모든 변을 원소로 갖는 집합 S를 만든다
- S가 비어있지 않는 동안
- 가장 작은 가중치의 변을 S에서 하나 빼낸다
- 그 변이 어떠 두개의 트리를 연결한다면 두 트리를 연결하여 하나의 트리로 만든다
- 그렇지 않다면 그 변은 버린다
알고리즘이 종료됐을 때 포레스트 F는 하나의 최소 비용 걸침 나무만을 가지게된다.
[편집] 같이 보기
[편집] 바깥 고리
- ((영어)) 크루스칼 알고리즘을 애니메이션으로 설명하는 곳
