변경 사항이 적용된 MST

Question

Kruskal 알고리즘을 최소 스패닝 트리로 수정하여 특정 에지 (u, v)를 포함해야한다고 생각하는 사람이 있습니까?

Answer 1

나는 혼란 스럽지만, kruskal이 음의 가중치를 처리 할 수 ​​있으므로이 가장자리에 무게를 줄 수 있습니다. -infinity. 물론

• 실제로 -infinity 수 없지만 충분히 낮은 수는 E.

Answer 2

에서 각 전자에 대한 -1 * sigma(|weight(e)|) 같은 당신이 할 수있는 경우에, 그것을 무시할 수없는만큼 중요한 것으로 그래프 구조를 수정하면 꼭지점 u과 v을 제거하고 u와 v의 가장자리가있는 새 꼭지점 w로 바꿀 수 있습니다. 가장자리가 중복되는 경우 무게가 가장 작은 것을 선택하십시오.

Answer 3

우리가 (u, v)의 가장자리 가중치를 알고 있다면 우리는 정렬 된 가장자리 가중치 목록 앞에 간단히 추가 할 수 있습니다. Kruskal은 가장자리 가중치를 증가 순서대로 정렬합니다. 이 경우 에지 (u, v)는 우리 트리에 포함 된 첫 번째 에지가되고 Kruskal은 (u, v)로 최소 가중치의 스패닝 트리를 찾아 정상적으로 실행됩니다.