Algorithm of Prim and Kruskal

Navigation
14

Both algorithms serve to generate a Minimum Generating Tree from a graph.

No Prim

  • Generate a single tree
  • Throughout the algorithm, the set X is always a tree

No Kruskal

  • Generate a forest before generating a Minimum Generating Tree
  • There is a guarantee that it will only be a tree after the last iteration

But the biggest question is:

What would be the Advantage and Disadvantage between them?

Additional information

  • Algorithm of Dijkstra solves the problem of the shortest path in a graph.
  • Dijkstra and Prim algorithms are almost exactly the same, but Prim you do not add the result, but the execution is the same.
  • The use of these two algorithms is for distinct problems (not are related to the same problem). One solves the shortest path while the other generates an AGM.
asked by anonymous 27.06.2017 / 18:51

1 answer

4

Some differences between algorithms:

  • The Prim algorithm initializes with a node, whereas the algorithm of Kruskal starts with an ordered edge.

  • In the Prim algorithm, the graph must be connected, whereas Kruskal can work on disconnected graphs as well.

    • The complexity of the Prim algorithm in most common implementations for a graph is by adjacency lists and by adjacency matrices and their respective complexities O(|A|log|V|) and O(V^2) in the worst case. And the Kruskal algorithm has time complexity equal to O(m log n) , where m represents the number of edges and n the number of vertices.

In this stackoverflow answer , there is 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 uses   simpler data structures.

The Prim algorithm is significantly faster at the edge when you have a really dense graph with many more edges than vertices. Kruskal works best in typical situations (sparse graphics) 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 is the optimal solution.

  • If we stop the algorithm in the middle, a connected tree will always be generated in the Prim algorithm. In Kruskal, it may be a disconnected tree or forest.


References:

05.07.2017 / 02:34
Xpath with Python Should I take any action on Heartbleed?