Prim and Kruskal algorithm
The two algorithms serve to generate a minimum generating Tree of a graph.
No Prime
- generates a single tree
- throughout the algorithm, the Set X is always a tree
No Kruskal
- generates a forest, before generating a minimum generating tree
- is guaranteed to be only a tree only after the last iteration
But the biggest doubt is:
What would be the advantage and disadvantage between them?
Additional information
- Dijkstra algorithm solves the shortest path problem in a graph.
- algorithm of Dijkstra and Prim are almost exactly the same, but in Prim you do not sum the result obtained, but the execution is equal.
- the use of these two algorithms are for distinct problems (not be related to the same problem). One solves the shortest path while the other generates an AGM.
1 answers
Some differences between the algorithms:
The prim algorithm initializes with a node, while the prim algorithm initializes with a node Kruskal starts with an ordered edge.
In Prim's algorithm, the graph must be connected, while Kruskal can work on disconnected graphs as well.
The complexity of the prim algorithm in most common implementations for a graph are by adjacency lists and by adjacency matrices and their respective complexities
O(|A|log|V|)andO(V^2)in the worst case. And Kruskal's algorithm has time complexity equal toO(m log n), where m represents the number of edges and n the number of vertices.
In this response from stackoverflow, you have an interesting comparison:
Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it use simpler data structures.
The prim algorithm is significantly faster at the limit when you have a really dense graph with many more edges than vertices. Kruskal works best in typical situations (sparse charts) because it uses simpler data structures.
About the advantages and disadvantages:
Both are simple and find a good solution to the problem, and most of the time it is the optimal solution.
If we stop the algorithm in the middle, in the prim algorithm a connected tree will always be generated. Already in Kruskal, it can be a disconnected tree or forest.
References: