그래프 G = (V, E)와 무게 함수 w : E-> R +가 있습니다. 또한 나는 G의 MST T를 가지고있다.무향 그래프의 MST
우리는 다음과 같은 알고리즘을 만들어야한다.우리는 가중 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 등) 동일한 수의 노드와 그래프의 노드의 일부 (어쩌면 없음)에 뿌리를 둔 나무와 간단한 사이클 구성되어 있기 때문에