Prim과 반대로 Kruskal을 언제 사용해야합니까?

Prim과 반대로 Kruskal을 언제 사용해야합니까?

---

Prim의 알고리즘을 사용해야 할 때와 Kruskal이 언제 최소 스패닝 트리를 찾을 수 있는지 궁금합니다 . 둘 다 쉬운 논리를 가지고 있으며 최악의 경우와 같으며 약간 다른 데이터 구조가 포함될 수있는 구현 만 다릅니다. 그렇다면 결정 요인은 무엇입니까?

---

가장자리가 많은 그래프가있는 경우 Prim의 알고리즘을 사용하십시오.

V 정점 E 모서리가 있는 그래프 의 경우 Kruskal의 알고리즘은 O (E log V) 시간으로 실행되고 Prim의 알고리즘은 Fibonacci Heap 을 사용하는 경우 O (E + V log V) 상각 시간으로 실행될 수 있습니다 .

정점보다 모서리가 더 많은 고밀도 그래프가있는 경우 Prim의 알고리즘이 한계에서 훨씬 빠릅니다. Kruskal은 단순한 데이터 구조를 사용하기 때문에 일반적인 상황 (스파 스 그래프)에서 더 잘 수행됩니다.

---

나는 그물에서 매우 간단한 방법으로 차이점을 설명하는 아주 좋은 스레드를 발견했습니다 : http://www.thestudentroom.co.uk/showthread.php?t=232168 .

Kruskal의 알고리즘은 사이클을 생성하지 않는 한 다음으로 가장 저렴한 에지를 추가하여 가장 저렴한 에지에서 솔루션을 성장시킵니다.

Prim의 알고리즘은 현재 솔루션에 없지만 가장 저렴한 모서리에 연결된 정점 인 다음으로 가장 저렴한 정점을 추가하여 임의의 정점에서 솔루션을 성장시킵니다.

여기에 해당 주제에 대한 흥미로운 시트가 첨부되어 있습니다.

If you implement both Kruskal and Prim, in their optimal form : with a union find and a finbonacci heap respectively, then you will note how Kruskal is easy to implement compared to Prim.

Prim is harder with a fibonacci heap mainly because you have to maintain a book-keeping table to record the bi-directional link between graph nodes and heap nodes. With a Union Find, it's the opposite, the structure is simple and can even produce directly the mst at almost no additional cost.

---

I know that you did not ask for this, but if you have more processing units, you should always consider Borůvka's algorithm, because it might be easily parallelized - hence it has a performance advantage over Kruskal and Jarník-Prim algorithm.

---

Kruskal can have better performance if the edges can be sorted in linear time, or are already sorted.

Prim's better if the number of edges to vertices is high.

---

If we stop the algorithm in middle prim's algorithm always generates connected tree, but kruskal on the other hand can give disconnected tree or forest

---

Kruskal time complexity worst case is O(E log E),this because we need to sort the edges. Prim time complexity worst case is O(E log V) with priority queue or even better, O(E+V log V) with Fibonacci Heap. We should use Kruskal when the graph is sparse, i.e.small number of edges,like E=O(V),when the edges are already sorted or if we can sort them in linear time. We should use Prim when the graph is dense, i.e number of edges is high ,like E=O(V²).

---

One important application of Kruskal's algorithm is in single link clustering.

Consider n vertices and you have a complete graph.To obtain a k clusters of those n points.Run Kruskal's algorithm over the first n-(k-1) edges of the sorted set of edges.You obtain k-cluster of the graph with maximum spacing.

---

The best time for Kruskal's is O(E logV). For Prim's using fib heaps we can get O(E+V lgV). Therefore on a dense graph, Prim's is much better.

---

Prim's is better for more dense graphs, and in this we also do not have to pay much attention to cycles by adding an edge, as we are primarily dealing with nodes. Prim's is faster than Kruskal's in the case of complex graphs.

---

kruskal 알고리즘에서 우리는 주어진 그래프에 많은 수의 모서리와 꼭짓점의 수를 가지지 만 각 가장자리에 우리는 주기적이 아니거나 어느 쪽에서도 가깝지 않아야하는 새로운 그래프를 준비 할 수있는 값이나 무게를 가지고 있습니다

이와 같은 그래프 _____________ | | | | | | | __________ | | 모든 정점 a, b, c, d, e, f에 이름을 지정하십시오.

참고 URL : https://stackoverflow.com/questions/1195872/when-should-i-use-kruskal-as-opposed-to-prim-and-vice-versa