서로소 집합 데이터 구조 또는 공용체 찾기 알고리즘 소개

결합 검색 알고리즘이라고도 알려진 분리 집합 정보 구조는 아마도 할당 및 네트워킹과 관련된 문제를 해결하기 위한 효율적인 방법을 제공하는 컴퓨터 과학의 기본 개념일 것입니다. 이는 구성요소 세트와 관련된 문제를 해결하고 해당 연결을 결정하는 데 특히 유용합니다. 이 기사에서는 C++에서 서로소 집합 정보 구조를 구현하는 언어 구성, 알고리즘 및 두 가지 고유한 방법을 살펴보겠습니다. 또한 이러한 방법을 설명하는 완전히 실행 가능한 코드 예제도 제공합니다.

문법

알고리즘을 자세히 살펴보기 전에 다음 코드 예제에 사용된 구문을 숙지해 봅시다 -

으아아아

알고리즘

연속되지 않은 데이터 구조를 활용하는 것은 여러 개의 분리된 컬렉션을 처리할 때 매우 유용할 수 있습니다. 각 개별 그룹에는 이를 특성화하기 위한 특정 대표자가 지정됩니다. 시작점은 각 구성 요소가 해당 대표자(자기 자신이기도 함)에 해당하는 고유한 격리된 집합을 형성하는 것과 관련됩니다. 서로소 집합에 대해 수행되는 두 가지 주요 작업은 합집합과 검색입니다.

합동작전

• 합치고 싶은 두 세트의 대표자를 찾아보세요.

• 대표자가 다른 경우 한 지점에서 다른 지점을 확인하여 세트를 효과적으로 병합하세요.

• 대표자가 동일할 경우 세트가 병합된 것이므로 추가 조치가 필요하지 않습니다.

작업 찾기

• 주어진 요소에서 해당 요소가 속한 집합의 대표자를 찾으세요.

• 대표 노드에 도달할 때까지 상위 포인터를 따릅니다.

• 대리자를 결과로 반환합니다.

방법 1: 순위 기반 병합 및 경로 압축

서로소 집합 데이터 구조를 구현하는 효과적인 방법은 순위별 합집합 및 경로 압축 기술을 사용하는 것입니다.

이 방법에서는 각 컬렉션에 관련 순위가 있으며 처음에는 0으로 설정됩니다.

두 세트 간의 합집합 연산을 수행할 때 높은 순위의 세트가 우선적으로 적용되고, 낮은 순위의 세트가 병합됩니다. 두 집합의 순위가 비슷한 경우 어느 집합에 누가 포함되는지 임의로 선택해야 합니다. 두 경우 모두 새로운 세트로 병합되면 순위가 1씩 증가합니다. 또한 조회 작업 속도를 높이고 시간 복잡성을 줄이기 위해 경로 압축은 이러한 작업 중에 트리 구조를 평면화하는 데 도움이 됩니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

으아아아

출력

으아아아

방법 2: 크기 및 경로 압축을 사용한 크기 기반 병합

서로소 집합 데이터 구조를 처리하는 또 다른 방법은 크기별 병합 및 경로 압축 기술을 사용하는 것입니다.

• 이 방법에서는 각 컬렉션에 연관된 크기가 있으며 처음에는 1로 설정됩니다.

• 합집합 작업에서는 더 작은 집합이 더 큰 집합으로 병합됩니다.

• 결과 세트의 크기는 이에 따라 업데이트됩니다.

• 이전 방법과 유사하게 검색 작업 중에 경로 압축을 적용하여 트리 구조를 평면화합니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

으아아아

출력

으아아아

결론

서로소 집합 데이터 구조 또는 합집합 검색 알고리즘은 집합 및 연결성과 관련된 문제를 해결하기 위한 강력한 도구입니다. 이 기사에서는 C++의 서로소 집합 데이터 구조 구문과 해당 알고리즘을 광범위하게 연구합니다. 이해를 넓히기 위해 우리는 독자들에게 경로 압축과 결합된 순위 기반 통합과 크기와 경로 압축을 통한 크기 기반 통합이라는 두 가지 고유한 접근 방식을 제공합니다. 이러한 방법을 이해하고 구현하면 분리 집합 추적이 필요한 다양한 문제를 효과적으로 해결할 수 있습니다.

위 내용은 서로소 집합 데이터 구조 또는 공용체 찾기 알고리즘 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!