Union-Find 알고리즘의 레벨 병합 및 경로 압축

합집합 찾기 집합(또는 분리 집합)이라는 알고리즘은 서로 다른 집합을 유지하고 집합의 멤버십을 확인하고 집합을 결합하는 작업을 제공하는 역할을 담당합니다. 요소 간의 현재 연결 정보를 유지하는 데 중요한 통합 및 조회 작업을 전문적으로 처리합니다.

문법

명확성을 위해 먼저 다음 코드 예제에서 사용할 메서드의 구문을 이해해 보겠습니다.

으아악

알고리즘

통합 검색 알고리즘은 통합과 검색이라는 두 가지 기본 작업으로 구성됩니다. 합집합 연산은 두 집합을 결합하고 탐색 연산은 집합의 대표 요소를 결정합니다. Union Lookup 작업을 반복적으로 적용함으로써 효율적인 Union Lookup 데이터 구조를 구축할 수 있습니다.

레벨별로 하나됨

수준별 조인 기술은 작은 나무가 항상 큰 나무의 루트에 연결되도록 하여 조인 작업을 최적화하는 데 사용됩니다. 이 접근 방식은 트리의 균형이 너무 맞지 않아 조회 작업이 비효율적이 되는 것을 방지합니다.

레벨별 결합 알고리즘은 다음과 같습니다 -

• x와 y 요소를 포함하는 집합의 대표(루트 요소)를 찾습니다.

• 대표자가 동일하면 반품하세요.

• x대표의 레벨이 y대표의 레벨보다 높으면 y대표가 x대표를 가리키도록 하고 x대표의 레벨을 업데이트합니다.

• 그렇지 않으면 x의 대표가 y의 대표를 가리키도록 하고 필요한 경우 y의 대표 순위를 업데이트하세요.

경로 압축

경로 압축은 쿼리 데이터 구조에서 트리 높이를 줄이는 또 다른 최적화 기술입니다. 그 목적은 검색 작업 중에 경로를 평탄화하여 후속 작업에 대해 더 짧은 경로를 제공하는 것입니다.

• 경로 압축 알고리즘은 다음과 같습니다 -

• 요소 x를 포함하는 집합의 대표(루트 요소)를 찾습니다.

• x에서 대표자로 경로를 이동할 때 방문한 각 요소가 대표자를 직접 가리키도록 만듭니다.

방법

이제 순위 합집합과 경로 압축의 기본 개념을 이해했으므로 C++에서 합집합 검색 알고리즘을 구현하는 두 가지 방법에 대해 논의해 보겠습니다.

방법 1: 배열 기반 구현

이 방법에서는 각 컬렉션을 배열로 표현합니다. 각 인덱스의 값은 요소의 상위 요소를 나타냅니다. 처음에 각 요소는 자신의 상위 요소로서 컬렉션을 대표함을 나타냅니다.

알고리즘

• 상위 배열의 초기화 프로세스를 시작하겠습니다. 각 요소에는 자체 상위 요소가 할당됩니다.

• 경로 압축을 사용하여 검색 작업을 구현하세요.

• 랭크별 연합을 활용해 연합 운영을 구현해보세요.

예

으아악

출력

으아악

방법 2: 트리 기반 구현

우리 연구의 컬렉션을 설명하기 위해 트리 기반 접근 방식을 사용했습니다. 그룹의 각 항목은 해당 상위 노드와 연결되어 있으며 특정 컬렉션을 나타내기 위해 루트 노드를 지정합니다.

알고리즘

• 각 요소가 자신의 상위인 상위 배열을 초기화합니다.

• 경로 압축 및 재귀 트리 순회를 사용하여 검색 작업을 구현합니다.

• 랭크별 연합을 활용해 연합 운영을 구현해보세요.

• 완전한 실행 코드

예

으아악

출력

으아악

결론

간단히 말하면 계층적 합집합과 경로 압축은 합집합 검색 알고리즘의 핵심 기술입니다. 통합 및 조회 작업을 각각 최적화하여 성능을 향상시키고 효율적인 연결 정보 관리를 가능하게 합니다. C++에서 이러한 기술을 구현함으로써 집합, 연결성 및 그래프와 관련된 문제를 효율적으로 해결할 수 있습니다.

요약하자면, 구문과 단계별 알고리즘을 소개하고 실제 C++ 실행 가능 코드 예제 2개를 제공했습니다. 순위별 통합 및 경로 압축을 이해하고 적용함으로써 알고리즘 기술을 향상하고 복잡한 문제를 보다 효율적으로 해결할 수 있습니다.

위 내용은 Union-Find 알고리즘의 레벨 병합 및 경로 압축의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!