싸이클이 존재하지 않고 모든 노드들이 연결된 최소 가중치 트리를 구해야한다
크루스칼 알고리즘
- 그래프의 모든 간선을 가중치의 오름차순으로 정렬
- 최소 간선부터 스패닝에 하나씩 추가하되 싸아클이 존재하지 않도록 한다
- 모든 정점을 독립적인 집합으로 만든다
- 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교
- 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다 (사이클이 생기지 않기 위해 확인)
개요
간선 추가시 싸이클의 존재 여부 확인하기
상호 배타적 집합을 표현하는 Union-Find Tree자료구조를 이용하여 해결한다
Union - Find 알고리즘
- Disjoint Set(상호 배타적 집합)을 표현할때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘이다
- 노드들 중에 연결된 노드를 찾거나(find), 노드들을 서로 연결(union)할 때 사용한다
- Disjoint Set이란?
- 서로 중복되지 않은 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
- 공통 원소가 없는(서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조
초기화
- n개의 원소가 개별집합으로 이뤄지도록 초기화
Union
- 두 개별 집합을 하나의 집합으로 합친다 or 두 트리를 하나의 트리로 합친다
Find
- 여러 노드가 존재할 때, 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 해당 노드의 루트노드를 비교한다 (같으면 같은 그래프에 속하는 것을 의미)
주의사항
Union의 순서에 따라서, 최악의 경우 트리구조가 아닌 한쪽으로만 합쳐져서 링크드 리스트 형태처럼 나올 수 있다
이때, Find/Union시 계산량이 O(N)이 될 수 있으므로, 이를 해결하기 위해 union-by-rank, path compression기법을 사용한다
Union-by-rank 기법
- 각 트리에 대해 높이(rank)를 기억해두고,
높이가 다른경우
- Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙인다
- 즉, 높이가 큰 트리의 루트노드가 합친 집합 노드의 루트노드가 되게 한다
높이가 같은 경우
- 아무 한쪽의 트리 높이를 1 증가시키고, 다른쪽의 트리를 해당 트리에 붙여준다
- 결국 높이가 큰 트리의 루트노드가 최종 루트노드가 된다
설명
- 초기화시 모든 원소는 높이(rank)가 0인 개별 집합인 상태에서 하나씩 원소를 합칠 때, union-by-rank기법을 사용한 경우
- 높이가 h인 트리가 만들어질려면, 높이가 h-1인 2개의 트리가 합쳐져야 한다
- 높이가 h-1인 트리를 만들기 위해 최소 n개의 원소가 필요하다면, 높이가 h인 트리가 만들어지기 위해서는 최소 2n개의 원소가 필요하다.
- 즉, 높이마다 2배의 요소가 필요, 노드의 루트 노드를 알기위해 높이 1씩 올라갈때마다 루트노드를 알기위해 체크해야할 원소를 1/2로 줄일수 있다
- 따라서 union-by-rank기법을 사용하면, union/find 시간복잡도는 O(log N)으로 낮출 수 있다
path-compression
- Find를 실행한 특정 노드에서부터 거쳐간 모든 노드를 다이렉트로 연결하는 기법
- Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있다
내꿈은 숲속의잠자는공주