무향 그래프의 MST

Question

그래프 G = (V, E)와 무게 함수 w : E-> R +가 있습니다. 또한 나는 G의 MST T를 가지고있다.

우리는 다음과 같은 알고리즘을 만들어야한다.우리는 가중 w (e ')가 E 인 새로운 에지 e'를 추가하면
을 알고리즘에 추가해야한다. 이는 새로운 그래프 G '= (V, EUe')의 MST가 될 수 있도록 T를 업데이트한다.
복잡성 : O (V). 내가 무엇을 제안

은 다음과 같습니다

1) 한 사이클을 포함 '우리는 새로운 그래프 그것은 T 전화 받기 T.에'전자를 추가합니다.
2) T '에서 DFS를 실행하고 방문하는 모든 정점을 표시하십시오. 또한 스택에 모든 정점과 모든 에지 가중치를
저장하십시오.
3) 우리가 이미 방문한 정점을 방문 할 때 우리는 달리기를 멈 춥니 다.
4) 우리가 정점에 도착할 때까지 스택에서 철수하기 시작합니다.
5) 철수하는 동안 우리는 스택에서 철회 한 최대 에지 무게를 저장합니다.
6) 최대 에지 무게가 w (e ')보다 큰 경우 교체합니다.
7) 그렇지 않으면 우리는 같은 T를 유지합니다.

나는 희망합니다.
나는 그것이 작동하거나 나에게 다른 사람을 줄 사람이 내게 줄 수 있다면 매우 고마워
솔루션 및 제안. 가장자리 (T 등) 동일한 수의 노드와 그래프의 노드의 일부 (어쩌면 없음)에 뿌리를 둔 나무와 간단한 사이클 구성되어 있기 때문에

Answer 1

는 예를 제안 솔루션은 정확 이주기.

T에서 정확히 1 에지를 삭제해야 나머지 그래프가 계속 연결됩니다. 분명히 가장 좋은 선택은 가장 큰 모서리를 삭제하는 것입니다. 그래프를 연결된 상태로 유지하면서 삭제할 수있는 유일한 가장자리는주기에있는 가장자리 (스택에 추가하는 가장자리)뿐입니다.

다른 해결책은 그래프에서 bridges을 찾은 다음 최대 비 브리지 에지를 찾아서 삭제하는 것입니다. 그러나 이것은 특별한 그래프이므로 언급 한 솔루션은 훨씬 쉬울 것입니다 (브리지가 아닌 가장자리는주기의 가장자리입니다).