2
주어진 트리가 MST이면 선형 시간 O (n)을 어떻게 확인할 수 있습니까?최소 스패닝 트리를 확인하는 방법
A
답변
-1
유니온 찾기 과정에 익숙합니까? 트리을받은 경우에만 이 연결된 그래프인지 여부를 확인해야합니다 (). 단 하나의 구성 요소 만 있으면 쿼리하는 것입니다. 다른 노드 사이의 최소 가중치를 저장하고 주어진 트리를 각 가중치가 최소 가중치와 비교하도록 맵 [pair<int,int>, int] 또는 유사한 해싱 라이브러리를 유지 보수합니다. 그렇지 않다면 MST가 아니라고 확신합니다. 그렇지 않으면 연결되어 있는지 찾아 봅니다. 그렇다면 그 MST.
유니온 찾기에서 트리 쇼팅을 사용하십시오. 트리가 연결되어 있는지 여부를 쿼리하려면 유니언 이전에 각 에지를 쉽게 확인할 수 있습니다. 이미 유니온이면주기가 있고 트리가 아예 없으므로 MST는 아닙니다.
가중치가 같은 그래프 K3을 고려하십시오. 두 노드 사이에 최소 가중치가 있더라도 에지 중 하나는 MST에 없습니다 (실제로는 그 노드 사이의 유일한 가중치입니다). – VF1