Kruskal 알고리즘을 최소 스패닝 트리로 수정하여 특정 에지 (u, v)를 포함해야한다고 생각하는 사람이 있습니까?변경 사항이 적용된 MST
4
A
답변
5
나는 혼란 스럽지만, kruskal이 음의 가중치를 처리 할 수 있으므로이 가장자리에 무게를 줄 수 있습니다. -infinity
. 물론
- 실제로
-infinity
수 없지만 충분히 낮은 수는 E.
1
에서 각 전자에 대한 -1 * sigma(|weight(e)|)
같은 당신이 할 수있는 경우에, 그것을 무시할 수없는만큼 중요한 것으로 그래프 구조를 수정하면 꼭지점 u
과 v
을 제거하고 u와 v의 가장자리가있는 새 꼭지점 w로 바꿀 수 있습니다. 가장자리가 중복되는 경우 무게가 가장 작은 것을 선택하십시오.
0
우리가 (u, v)의 가장자리 가중치를 알고 있다면 우리는 정렬 된 가장자리 가중치 목록 앞에 간단히 추가 할 수 있습니다. Kruskal은 가장자리 가중치를 증가 순서대로 정렬합니다. 이 경우 에지 (u, v)는 우리 트리에 포함 된 첫 번째 에지가되고 Kruskal은 (u, v)로 최소 가중치의 스패닝 트리를 찾아 정상적으로 실행됩니다.
정확합니다. Kruskal의 알고리즘은 가중치의 값을 전혀 고려하지 않고 상대적인 순서 만 고려합니다. 가중치는 가장자리를 정렬하는 데에만 사용되며 가장자리는 순서를 추가합니다 (사이클을 만드는 순서는 제외). – sdcvvc