union-find
-
합집합 찾기(Union-Find)알고리즘/탐색 2021. 12. 25. 01:16
서로소 집합 알고리즘 : 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별. (1) 자기 자신을 부모로 가진다. (2) A,B가 연결되어 있을 때 더 작은 값을 부모로 합친다 (Union) (3) A,B,C가 연결되어 있을 때 재귀함수를 이용해서 가장 작은 값인 A로 부모를 지정한다.(Union-Find) Find 알고리즘 : 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘. Union-Find는 최소 비용 신장 트리를 만들기 위한 알고리즘인 Kruskal 알고리즘에 주로 사용됨. //부모 노드를 찾는 함수 int getParent(int parent[], int x){ if(parent[x] == x) retu..