크루스칼 알고리즘은 비방향성 가중치가 있는 그래프에서 최소비용 신장트리를 구하기 위한 알고리즘이다. 위 그림과 같은 그래프가 있다고 가정 할 때, 각 이음선의 가중치를 오름차순으로 정렬하면 다음과 같다. (v1, v2) 1(v3, v5) 2(v1, v3) 3(v2, v3) 3(v3, v4) 4(v4, v5) 5(v2, v4) 6 이젠 이음선을 차례로 선택하기만 하면 된다. 단, 조건이 하나 있는대 선택한 이음선에 연결된 각 정점이 적어도 하나는 선택되지 않은 파란색 정점이어야 한다. 이 조건을 만족시키며 선택하면 다음 그림과 같이 전개도를 확인가능하다. (v1, v2) 선택 (v3, v5) 선택 (v1, v3) 선택 (v2, v4) 선택 크루스칼 알고리즘도 항상 최소비용 신장트리를 보장한다.

이 알고리즘은 가중치가 있는 비방향 그래프에서 최단경로를 구하기 위한 알고리즘이다. 알고리즘을 간단하게 설명하자면 1. A집합(선택된 정점의 집합) 중 이음선의 가중치가 가장 낮은 이음선을 선택한다. 2. 선택한 이음선에 연결된 정점을 A집합에 추가한다. 3. [1~2 과정]을 모든 정점이 A집합에 추가 될 때 까지 반복한다. 집합 A = { }, B ={v1, v2, v3, v4, v5}A는 선택 된 정점,B는 선택되지 않은 정점의 집합이다. 집합 A = {v1}, B ={v2, v3, v4, v5}v1을 기본적으로 우선 선택한다. 집합 A = {v1, v2}, B ={v3, v4, v5}v1에 연결된 이음선 중에서 가중치가 1인 이음선을 선택한다.그리고 v2를 집합 A에 추가한다. 집합 A = {v1..

상호배타적 집합을 표현 할 때 쓰는 자료구조이다. 최적화 하지 않은 Union-Find 복잡도는 O(n) union-by-rank, path compression을 통해 최적화를 한 Union-Find는 O(a(N))의 복잡도를 가진다. 상수시간에 동작한다고 봐도 됨. 자세한 내용은 -> http://blog.secmem.org/521