Prim의 MST : 시작 노드가 중요합니까?

Question

그래프의 최소 스패닝 트리를 찾기 위해 Prim의 알고리즘을 사용하는 경우 어떤 루트 노드가 선택되었는지는 상관이 없습니다. 결과 MST는 상관없이 동일한 가중치를가집니다. 이 올바른지?

Answer 1

맞습니다. 다른 시작 노드를 선택하면 다른 스패닝 트리를 얻을 수 있지만 항상 최소한의 가중치를 유지합니다.

Answer 2

최소값의 고유성 때문입니다.

증명 :

Suppose there are 2 "different" minimum weights W1 and W2 

W1 is minimum 
W2 is minimum 
W1 != W2 

This leads to contradiction because 
if W1 != W2 then 
    W1 < W2 -> W1 is minima 
    or 
    W1 > W2 -> W2 is minima 
Hence if W1 must equal W2. 

Answer 3

웨이트/트리의 비용없이 노드/정점 개시 동일 할 것이다; 그러나 나무의 모양이 다를 수 있습니다. 입후보를위한 두 개의 가장자리가 현재 최소치가되는 동일한 가중치를 가지면 그 선택은 구현에 따라 다릅니다. 진정한 타이 브레이킹 단계가 없다면 (이것은 거의 같지 않습니다. 많은 가중치 가장자리를 가진 그래프에서 실제 이득이 없으면 O (n)까지 올라갈 수 있습니다.) "가장 먼저 발견 된"것 같습니다. 즉, 노드/버텍스가 추가되고 방문한 순서가 타이 브레이크에 대한 순서이므로 시작 노드/버텍스가 모양에 영향을 미칠 수 있습니다.

두 번째로 성능에 영향을 줄 수 있지만 제어하기가 어렵습니다. 힙 작업의 크기가 커지면서 가능한 한 적은 수의 가장자리를 추가하는 것이 좋으며, 특히 초기에 추가하는 것이 좋습니다. 저조도에 우선 순위를 부여하는 근거로 사용할 수 있습니다. 그러나 이것은 첫 번째 노드/정점을 훨씬 넘어서는 문제는 아닙니다.

TL : DR : 총 비용/중량 : 아니오. 모양 : 여러 MST가있는 경우 예.