union-find, minheap, Kruskal 및 정렬 알고리즘을 사용하여 최소 비용 스패닝 트리를 만드는 방법은 무엇입니까? (C++)

Question

이 질문이 다소 광범위하다면 사과드립니다.하지만 최소 비용 스패닝 트리를 만드는 방법을 이해하는 데 어려움을 겪고 있습니다. 이것은 C++에서 중요합니다.

내가 알고있는 것으로부터, 당신은 스패닝 트리를 만들기위한 최소 비용 가장자리를 선택하기 위해 Kruskal 's를 사용할 것입니다. 내 생각은 가장자리를 최소 비용으로 읽는 것이고 최소 비용으로 가장자리를 얻으려면 상단에서 제거 할 수 있습니다.

지금까지만 minheap을 구현하고 유니온 찾기를 설정할 수 있었지만 스패닝 트리를 만들기 위해 union-find 및 sorting 알고리즘의 목적을 아직 모르고 있습니다.

나는 조언을 크게 부탁드립니다.

편집 : 유니온 찾기, minheap, kruskals 및 정렬 알고리즘에 국한되지 않으며, 필자도이를 수행 할 필요가 없습니다. 이것들은 강사가 제안한 항목들입니다.

Answer 1

이 두 구조는 알고리즘에서 다른 용도로 사용됩니다. Kruskal의 알고리즘은 사이클을 형성하지 않는 각 포인트에서 가능한 가장 저렴한 에지를 추가하여 작동합니다. 특히 복잡한 수학과는 다른 결과를 사용하여 결과 스패닝 트리가 최소화된다는 것을 보여줄 수 있습니다. 이것이 왜 작동하는지에 대한 직감은 다음과 같습니다. Kruskal의 알고리즘이 최적이 아니며 저렴한 스패닝 트리가 있다고 가정합니다. 해당 트리의 모든 가장자리를 가중치로 정렬 한 다음 정렬 된 순서로 해당 가장자리를 Kruskal의 알고리즘에 의해 선택된 순서대로 비교합니다. Kruskal의 알고리즘이 최적이 아니라는 모순이 있다고 가정하기 때문에 불일치가있는 시퀀스의 일부가 있어야합니다. 이러한 불일치가 Kruskal의 알고리즘이 최적 해보다 가벼운 경우, 그 가장자리를 추가하고 생성 된주기를 찾은 다음주기에서 가장 무거 운 모서리를 삭제하여 최적 솔루션을 훨씬 더 효과적으로 만들 수 있습니다. Kruskal의 알고리즘에 의해 생성 된 MST에서 사이클을 생성하고 Kruskal의 알고리즘이주기를 만드는 에지를 추가하지 않기 때문에 그 에지는 우리가 방금 추가 한 에지가 될 수 없습니다. 이것은 Kruskal의 알고리즘이 밝은 부분을 추가하지 않아 최적의 해를 벗어 났음을 의미합니다. 그러나 Kruskal의 알고리즘이 가장자리를 건너 뛰는 유일한 이유는 그것이주기를 생성하는 경우이며 이는 최적의 MST에주기가 있어야한다는 것을 의미합니다. 또한 모순입니다. 이것은 우리의 가정이 틀렸고 Kruskal의 알고리즘이 최적이어야한다는 것을 의미합니다.

Kruskal의 알고리즘에 힙과 공용 구조체가 필요한 이유를 알 수 있습니다. 정렬 된 순서로 모든 가장자리를 되돌릴 수 있도록 힙이 필요합니다. 이 순서대로 가장자리를 방문하지 않으면 위의 증명이 깨지고 모든 베팅이 해제됩니다. 흥미롭게도 실제로 힙이 필요하지는 않습니다. 정렬 된 순서로 모든 가장자리를 방문하는 방법이 필요합니다. 원하는 경우 거대한 배열에 모든 가장자리를 덤프 한 다음 배열을 정렬 할 수 있습니다. 빠른 정렬을 사용하는 경우이 알고리즘의 런타임은 이진 힙 경우에서 변경되지 않습니다.

union-find 구조는 조금 복잡합니다. Kruskal 알고리즘의 각 점에서 가장자리를 추가하면 그래프에 사이클이 생성되는지 여부를 알 수 있어야합니다. 이를 수행하는 한 가지 방법은 이미 어떤 노드가 서로 연결되어 있는지 추적하는 구조를 저장하는 것입니다. 이렇게하면 가장자리를 추가 할 때 끝점이 이미 연결되어 있는지 확인할 수 있습니다. 그렇다면 가장자리가주기를 형성하고 무시되어야합니다. 노조 찾기 구조는이 정보를 효율적으로 유지 관리하는 방법입니다. 특히, 두 가지 연산 인 union과 find는 이전에 연결되지 않은 두 개의 서로 다른 노드 그룹을 연결하는 작업에 해당합니다. 예를 들어, 서로 다른 부분에 포함 된 두 개의 트리를 연결하는 가장자리를 추가 한 경우와 같습니다 숲. 찾기 단계는 두 노드가 이미 연결되어 있는지 확인하는 방법을 제공합니다. 그렇다면 현재 가장자리를 건너 뜁니다.

희망이 도움이됩니다.