재귀 최소 스패닝 트리 알고리즘

Question

최소 스패닝 트리를 찾는 데 적합한 알고리즘입니까?

그래프를 똑같이 연결된 두 부분으로 나누십시오. 최소 스패닝 트리를 찾습니다. 그들을 연결하는 가장 작은 가장자리를 사용하여 연결하십시오. 나는이 알고리즘의 반례를 얻으려고하지만 그렇게 할 수는 없다.

Answer 1

왼쪽 가장자리가 비용 10이고 모든 다른 가장자리가 비용 1 인 사각 그래프로 생각하십시오. 순환 단계를 위해 그래프를 왼쪽과 오른쪽으로 나누면 결국 비용 3 대신에 비용 12의 스패닝 트리.

MST는 "분할 및 정복"알고리즘에 적합하지 않습니다. 가장 가까운 것은 아마도 Reverse-Delete 알고리즘입니다. 모서리를 제거하지 않을 때마다 (그래프 연결이 끊어지기 때문에) 나머지 단계는 그 모서리의 양면에서 재귀 적으로 실행되는 것으로 생각할 수 있습니다.