Prim 및 Kruskal 알고리즘

Question

Prim 및 Kruskal 알고리즘 모두 최소 스패닝 트리를 생성합니다. cut 속성에 따르면 트리의 총 비용은 이러한 알고리즘에서 동일하지만 여러 선택 사항에 직면했을 때 알파벳 순서로 선택하면이 두 알고리즘이 동일한 총 비용으로 다른 MST를 제공 할 수 있습니다 . 예를 들어, 에지 A-> B 및 B-> C에 대해 max (source, dest)를 비교하면 A-> B에서 A를 비교하고 B-> C에서 B를 비교합니다.

는 비교가 양쪽 가장자리는 비용이 동일하고 (소스, 이명 령) 문자, 그것은 동일한 두 모서리를 선언하지 않습니다 동일한 최대를 가지고있는 경우 처리하는 가정 당신에게

Answer 1

감사드립니다. 여러 MST의 가능성이 있기 위해서는 그래프의 적어도 두 에지가 동일해야합니다. 따라서 MST는 고유하며 Prim과 Kruskal의 알고리즘은 동일한 결과를 반환합니다.

반면에 비교기가 A -> B (비용 1) 및 A -> C (비용 1) 에지를 동일하게 선언하면 알고리즘에 따라 다른 MST가 생성 될 가능성이 있습니다 (A-> B 또는 A-> C).