목록동치류문제 (1)

W 개발 일지

[ 자료구조 ] Union-Find 알고리즘 (동치류 문제) / 크루스칼 알고리즘

Union-Find 알고리즘 : 정점으로 구성된 집합을 관리하는 방법으로 집합의 합병과 요소가 어떤 부분집합에 속하는가를 판정하는 두 가지 연산. find 연산으로 특정 원소들을 집합 안에 있는지 없는지 판별하고, 없다면 두 원소들이 속한 트리들을 합병한다. Union = 2개의 원소로 이루어진 집합을 합치는 연산. = 합집합 Find = 특정 원소가 속한 집합을 찾아주는 연산. 총 세 가지 방법이 있다. 첫번째 방법 : 부모 노드 활용 Find 연산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 //자기 자신을 가지는 노드로 초기화. void initgroup() { for(i=0;i 1 -> 2 -> 3 -> 5 -> 10 -> 13 Find 연산 연결리스트의 검색 연산으로 찾으려는..
C/자료구조-알고리즘 2021. 6. 11. 02:27
이전 Prev 1 Next 다음