내 연구를하고 있는데 질문이 붙어 있습니다 :하나의 노드가 사라질 때 MST를 구성하는 방법은 무엇입니까?
최소 스패닝 트리 (프리즘 알고리즘)를 사용하고 있습니다. 이제는 트리의 한 노드가 삭제되고, 다시 사용할 수있는 방법이 있는지 궁금합니다. 여전히 최적을 유지하는 내 나무를 구성 할 수 있습니까?
여기에 몇 가지 제안 사항이 있습니다. 도움을 주시면 감사하겠습니다.
감사합니다.
삭제 된 버텍스가 MST의 리프 인 경우 아무 것도 할 필요가 없습니다. 여전히 스패닝 트리가 있으며 여전히 최적입니다.
리프가 아닌 경우 이제 두 개의 하위 트리가 있습니다. 두 하위 트리 사이에있는 가장 짧은 가장자리로 다시 연결하기 만하면됩니다. 그 가장자리를 찾는 가장 좋은 방법은 아마도 Prim의 알고리즘 (또는 O (n^2)에서 모든 꼭지점 쌍을 고려하여)에서 사용한 데이터 구조를 사용하는 것입니다.
트리에서 노드를 제거하면 그래프가 둘 이상의 연결되지 않은 구성 요소로 나뉠 수 있습니다. 최악의 경우, 모든 에지가 하나의 중앙 노드에서 다른 모든 것 (스타와 같은)으로가는 MST를 상상해보십시오. 이 경우 중앙 노드가 제거되면 전체 MST를 다시 실행해야합니다. 그래서, 짧은 대답은 것 같아요 - 그것은 노드가 제거됩니다에 따라 달라집니다. 해결 방법은 aix에서 설명한 것처럼 수행합니다. 제거 된 노드로 인해 연결이 끊긴 모든 구성 요소를 찾고이를 탐욕스럽게 연결하는 것입니다. 이것은 0에서 (잎 노드가 제거 된 경우) n-1로 확장 될 수 있습니다 (별의 중심이 제거 된 경우)
이 문제는 잘 연구되었습니다. 2001 년에 수행 된 연구에 따르면 그래프 데이터 구조를 유지 관리하여 에지를 삽입 또는 제거하고 O 시간 (로그 n)의 최소 스패닝 트리를 업데이트 할 수 있음을 알았습니다. 바운드 된 사람은 지금까지 생각해 낼 수있었습니다. 이 알고리즘을 설명하는 논문은 조밀하고 까다 롭습니다하지만 당신이 관심이 있다면 당신은 여기에서 찾을 수 있습니다
희망이 도움이!
좋은 연구 주제이지만, programmers.stackexchnage.com에 더 적합합니다. –
MST가 단위 그래프 (모든 모서리의 가중치가 1임을 의미)에서 생성 된 그래프입니까? 그래프는 방향성이 있습니까? – Davidann
@David : 네, 단위 그래프입니다 – root