유니온-파인드
-
[그래프] 유니온-파인드(Union-Find)Problem-Solving/Algorithm 2022. 6. 1. 17:09
🍀 목차 유니온-파인드 알고리즘 기본 이해 구현(JavaScript) 활용 예 시간 복잡도 유니온-파인드 알고리즘 집합을 관리하는 자료구조 유니온-파인드를 활용해 합집합을 찾는 알고리즘이며, Disjoint Set(서로소 집합, 상호 배타적 집합), Merge find Set 알고리즘이라고도 불린다. 유니온-파인드는 루트 노드 밑에 자식 노드들이 엮인 트리 구조를 따른다. 여러 개의 노드 중 선택된 두 노드가 같은 그래프에 속해 있는지 판별한다. 크게 3가지의 과정을 거친다. Initialization(초기화) : 각 노드가 각각의 집합에 포함되도록 초기화하는 과정 Find(찾기) : 특정 노드의 부모를 찾는다. (해당 노드가 속한 집합의 루트를 반환한다.) Union(합치기) : 두 노드 A와 B를 한..
