[알고리즘] 합집합 찾기(Union-Find)

 

 

 

 

 

알고리즘 개요 및 소개

​

 

Union-Find는 그래프 알고리즘 중 하나로 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 이 두 노드가 서로 같은 그래프에 속하는지 판단하는 알고리즘이다. 

 

 

 

 

 

소스코드

#include<iostream>
constexpr int MAX_LIST = 11;
int g_nodeList[MAX_LIST];
void InitNode();
void UnionNode(int,int);
bool FindNode(int,int);
int CheckNode(int);


int main() {
	InitNode();
	UnionNode(1, 2);
	UnionNode(2, 3);
	UnionNode(3, 4);
	UnionNode(5, 6);
	UnionNode(6, 7);
	UnionNode(7, 8);

	std::cout << FindNode(1, 5) << "\n";
	UnionNode(1, 5);
	std::cout << FindNode(1, 5) << "\n";

}
void InitNode() {
	for (int i = 1; i < MAX_LIST; ++i) {
		g_nodeList[i] = i;
	}
}

int CheckNode(int node) {

	if (g_nodeList[node] == node)
		return node;
	else {
		return g_nodeList[node] = CheckNode(g_nodeList[node]);
	}
}

void UnionNode(int lhs, int rhs) {

	lhs = CheckNode(lhs);
	rhs = CheckNode(rhs);

	if (lhs < rhs) {
		g_nodeList[rhs] = lhs;
	}
	else {
		g_nodeList[lhs] = rhs;
	}
}

bool FindNode(int lhs,int rhs) {
	lhs = CheckNode(lhs);
	rhs = CheckNode(rhs);

	return lhs == rhs;
}

 

후기

전에 작성했던 크루스칼 알고리즘에서 그래프의 사이클을 확인하는 방법에 사용되는 것이 합집합 찾기이다. 

2020/02/11 - [자료구조 알고리즘/탐색 알고리즘] - 최소 비용 신장 트리(Minimum Cost Spanning Tree)

 

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/서로소_집합_자료_구조

Blog: https://blog.naver.com/ndb796/221230967614