찾기 MST는 하나가 PLZ 어떻게 프림 알고리즘을 사용하여 MST 찾기하는 나를 도울 수 프림 알고리즘

Question

를 사용하여. 노드가 MST에 추가되는 순서 .. 감사

Answer 1

The Directed Minimum Spanning Tree Problem 인용 산악 표준시의 가장자리를 선택하고 쓰기 :

1. 이 호 루트 (있는 경우)를 입력 폐기를; 루트가 아닌 각 노드에 대해 최소 비용이 인 입력 호를 선택하십시오. 선택된 n-1 호를 집합 S로합니다.
2. 사이클이 형성되지 않으면 G (N, S)는 MST입니다. 그렇지 않으면 계속하십시오.
3. 주기의 노드를 의사 노드 (k)로 계약하고 외부 노드 (i)에서주기 의 노드 (j)에 들어가는 각 호 의 비용을 수정합니다 다음 식에 따라 사이클 . (x (j), j) -min_ {j} (c (x (j), j)) 여기서 c (x (j), j) ., J)가 들어가는 사이클 J 각 가상 노드 용
4. 호의 비용이 가장 작은 변성 비용이 진입 아크를 선택; 는 S에서 동일한 실제 노드 진입 아크 바꾸기 새로운 선택된 아크.
5. 이동 수축 그래프 (2)로 진행한다.
가

알고리즘의 핵심 아이디어을 갖는 대체 아크 (들)를 발견한다 주기를 없애기위한 최소 추가 비용. 주어진 방정식 은 관련된 추가 비용을 나타냅니다.