Union-Find 알고리즘, MST

서로소 집합(Disjoint-set) - Union-Find 알고리즘

• 상호 간 중복 원소가 없는 집합
• 교집합이 없으므로, 각 집합에서 아무 원소나 뽑아도 각 집합의 대표자(representative)가 된다.
• Make-Set, Find-Set, Union 3가지 연산이 존재
• Make-Set: 최소 단위 집합으로 크기가 1인 집합
• Find-Set: x가 속한 집합을 찾는 것으로, x가 속한 집합의 대표자를 찾음
• Union: 각각의 원소가 속한 집합을 합치는 연산으로, 두 원소가 같은 집합일 경우 합치지 않는다.

연결리스트로 구현

• 같은 집합의 원소들은 하나의 연결리스트로 관리
• 연결리스트의 맨 앞 원소를 집합의 대표 원소로 삼고, 각 원소는 집합의 대표 원소를 가리키는 링크를 가짐(바로 대표자에 접근할 수 있는 링크)

트리로 구현

• 같은 집합의 원소들을 하나의 트리로 표현
• 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 됨
• 트리의 편향을 완화하기 위해 Path compression을 사용함

최소 신장 트리(MST)

• 모든 정점을 탐방하는 경로 중 가중치의 합이 최소가 되는 트리
• 최소 비용 문제, 최단 경로 문제
• 신장 트리: n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
• 최소 신장 트리(Minimum Spanning Tree): 신장 트리 중 가중치 합이 최소인 신장 트리

Kruskal 알고리즘

• 비용이 작은 간선부터 선택하여 최소 신장 트리를 완성하는 알고리즘
• 모든 간선을 가중치에 따라 오름차순으로 정렬(간선 중심 연산 → 간선 리스트 필요)
• Union-Find 알고리즘을 이용하여 구현
• 간선을 n-1개를 찾으면 끝이 난다.

Prim 알고리즘

• 하나의 정점에서 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택(정점 중심 연산 → 인접 행렬 혹은 인접 리스트 필요)
• 각 정점의 선택 유무를 관리하기 위한 배열 필요