최소 신장 트리를 위한 C++의 Boruvka 알고리즘

그래프 이론에서 연결된 가중치 그래프의 최소 신장 트리(MST)를 찾는 것은 일반적인 문제입니다. MST는 모든 정점을 연결하고 총 간선 가중치를 최소화하는 그래프 간선의 하위 집합입니다. 이 문제를 해결하기 위한 효율적인 알고리즘은 Boruvka 알고리즘입니다.

문법

으아아아

알고리즘

이제 Boruvka 알고리즘에서 최소 스패닝 트리를 찾는 단계를 간략하게 설명하겠습니다 −

• MST를 빈 세트로 초기화하세요.

• 각 정점에 대해 하위 집합을 만듭니다. 여기서 각 하위 집합에는 하나의 정점만 포함됩니다.

• 최소 스패닝 트리(MST)가 V-1 모서리를 가질 때까지 다음 단계를 반복합니다(V는 그래프의 정점 수) −

  • 각 하위 집합에 대해 이를 다른 하위 집합에 연결하는 가장 저렴한 가장자리를 찾습니다.

  • 최소 스패닝 트리에 선택한 가장자리를 추가합니다.

  • 선택한 가장자리의 하위 집합에 대해 합집합 작업을 수행합니다.

• 최소 스패닝 트리를 출력합니다.

방법

Boruvka 알고리즘에는 각 하위 집합을 연결하는 가장 저렴한 가장자리를 찾는 여러 가지 방법이 있습니다. 다음은 두 가지 일반적인 방법입니다 −

방법 1: 간단한 방법

각 하위 집합에 대해 모든 가장자리를 반복하고 이를 다른 하위 집합에 연결하는 가장 작은 가장자리를 찾습니다.

선택한 가장자리를 추적하고 공동 작업을 수행합니다.

예

으아아아

출력

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

먼저 Edge와 Subset이라는 두 가지 구조를 정의합니다. 가장자리는 가장자리의 소스, 대상 및 가중치를 포함하여 그래프의 가장자리를 나타냅니다. 하위 집합은 상위 및 순위 정보를 포함하여 통합 쿼리 데이터 구조의 하위 집합을 나타냅니다.

찾기 기능은 경로 압축을 사용하여 요소의 하위 집합을 찾는 도우미 기능입니다. 요소가 속한 하위 집합의 대표(상위 노드)를 반복적으로 찾고 경로를 압축하여 향후 쿼리를 최적화합니다.

unionSets 함수는 순위 병합을 사용하여 두 하위 집합을 병합하는 또 다른 보조 함수입니다. 두 하위 집합의 대표자를 찾아 순위에 따라 병합하여 균형 잡힌 트리를 유지합니다.

boruvkaMST 함수는 가장자리 벡터와 정점 수(V)를 입력으로 사용합니다. MST를 찾기 위해 Boruvka 알고리즘을 구현합니다.

boruvkaMST 함수 내에서 MST의 가장자리를 저장하기 위해 selectedEdges 벡터를 만듭니다.

부분 집합을 표현하기 위해 부분 집합 구조의 배열을 만들고 기본값으로 초기화합니다.

또한 각 하위 집합의 가장 저렴한 가장자리를 추적하기 위해 가장 저렴한 배열을 만듭니다.

변수 numTrees는 정점 수로 초기화되고 MSTWeight는 0으로 초기화됩니다.

알고리즘은 모든 구성 요소가 트리에 포함될 때까지 구성 요소를 반복적으로 결합하여 작동합니다. 메인 루프는 numTrees가 1이 될 때까지 실행됩니다.

메인 루프의 각 반복에서 모든 가장자리를 반복하고 각 하위 집합에 대해 최소 가중치 가장자리를 찾습니다. 가장자리가 두 개의 서로 다른 하위 집합을 연결하는 경우 가장 가중치가 낮은 가장자리의 인덱스로 가장 저렴한 배열을 업데이트합니다.

다음으로 모든 하위 집합을 반복합니다. 하위 집합에 최소 가중치의 가장자리가 있는 경우 이를 selectedEdges 벡터에 추가하고 MSTWeight를 업데이트한 다음 하위 집합의 합집합 연산을 수행하고 numTrees 값을 줄입니다.

마지막으로 MST 가중치와 선택한 가장자리를 출력합니다.

주 기능에서는 사용자에게 정점과 가장자리의 수를 입력하라는 메시지가 표시됩니다. 그런 다음 각 모서리에 대한 입력(소스, 대상, 가중치)을 가져와 입력과 함께 boruvkaMST 함수를 호출합니다.

방법 2: 우선순위 큐 사용

가장자리를 저장하기 위해 가중치별로 정렬된 우선순위 대기열을 만듭니다.

각 하위 집합에 대해 우선순위 대기열의 다른 하위 집합에 연결하는 최소 가중치 가장자리를 찾습니다.

선택한 가장자리를 추적하고 공동 작업을 수행합니다.

예

으아아아

출력

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

이 접근 방식에서는 우선순위 대기열을 사용하여 각 하위 집합에 대한 최소 가중치 간선을 찾는 프로세스를 최적화합니다. 아래는 코드에 대한 자세한 설명입니다 −

코드 구조와 도우미 함수(예: find 및 UnionSets)는 이전 방법과 동일하게 유지됩니다.

boruvkaMST 함수는 우선순위 큐를 사용하여 각 하위 집합에 대한 최소 가중치 간선을 효율적으로 찾도록 수정되었습니다.

가장 저렴한 어레이를 사용하는 대신 이제 에지의 우선순위 큐(pq)를 생성합니다. 그래프의 가장자리로 초기화합니다.

메인 루프는 이전 방법과 유사하게 numTrees가 1이 될 때까지 실행됩니다.

각 반복마다 우선순위 큐에서 최소 가중치 가장자리(minEdge)를 추출합니다.

그런 다음 찾기 기능을 사용하여 minEdge의 소스와 타겟이 속하는 하위 집합을 찾습니다.

하위 집합이 다른 경우에는 selectedEdges 벡터에 minEdge를 추가하고, MSTWeight를 업데이트하고, 하위 집합 병합을 수행하고, numTrees를 줄입니다.

모든 구성 요소가 트리에 포함될 때까지 프로세스가 계속됩니다.

마지막으로 MST 가중치와 선택한 가장자리를 출력합니다.

주요 기능은 이전 방법과 동일하며 테스트 목적으로 사전 정의된 입력이 있습니다.

결론

Boruvka의 알고리즘은 가중치 그래프의 최소 신장 트리를 찾는 효율적인 솔루션을 제공합니다. 우리 팀은 C++에서 알고리즘을 구현할 때 전통적인 접근 방식 또는 "순진한" 접근 방식이라는 두 가지 경로를 심층적으로 탐색했습니다. 다른 하나는 우선순위 대기열을 활용합니다. 주어진 문제의 특정 요구 사항에 따라 다릅니다. 각 방법에는 특정 장점이 있으며 이에 따라 구현할 수 있습니다. Boruvka 알고리즘을 이해하고 구현하면 C++ 프로젝트의 최소 스패닝 트리 문제를 효율적으로 해결할 수 있습니다.

위 내용은 최소 신장 트리를 위한 C++의 Boruvka 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!