Prim and Kruskal algorithm

Asked

Viewed 7,529 times

15

The two algorithms serve to generate a Minimum Generating Tree of a Graph.

In the Prim

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

In the Kruskal

  • Generates a forest, before generating a Minimum Generating Tree
  • It is guaranteed to be only one tree after the last iteration

But the bigger question is:

What would be the Upside and Downside among them?

Additional information

  • Algorithm of Dijkstra 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 obtained result, but the execution is equal.
  • The use of these two algorithms are for distinct problems (no are related to the same problem). One solves the shortest path while the other generates an AGM.
graph

  • If I’m not mistaken Kruskal is possible to be distributed...

  • 1

    Related question: https://answall.com/questions/123522/diferen%C3%A7a-na-aplica%C3%A7%C3%A3o-dos-algoritmos-de-dijkstra-e-prim

1 answer

7


Some differences between algorithms:

  • The Prim algorithm initializes with a node, while the Prim algorithm 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 the most common implementations for a graph is by adjacency lists and adjacency matrices and their respective complexities O(|A|log|V|) and O(V^2) worst-case. And Kruskal’s algorithm has time complexity equal to O(m log n), where m represents the number of edges and n the number of vertices.

In that reply stackoverflow, has 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.

Prim’s algorithm is significantly faster on the limit 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.

On the advantages and disadvantages:

  • Both are simple and find a good solution to the problem, most of the time being the optimal solution.

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


References:

Browser other questions tagged graph

You are not signed in. Login or sign up in order to post.