0

# What are the Prim and Kruskal algorithms?

Updated: 4/28/2022

Wiki User

13y ago

we use them to find minimum spanning trees.

Wiki User

13y ago

Earn +20 pts
Q: What are the Prim and Kruskal algorithms?
Submit
Still have questions?
Related questions

### Which one is better kruhskal's algorithm or prim's algorithm?

Both algorithms have the same efficiency and both are based on the same greedy approach. But Kruskal's algorithm is much easier to implement.

### Why prims algorithm is better than kruskals algorithm?

"What are difference between Prim's algorithm and Kruskal's algorithm for finding the minimum spanning tree of a graph?" Prim's method starts with one vertex of a graph as your tree, and adds the smallest edge that grows your tree by one more vertex. Kruskal starts with all of the vertices of a graph as a forest, and adds the smallest edge that joins two trees in the forest. Prim's method is better when * You can only concentrate on one tree at a time * You can concentrate on only a few edges at a time Kruskal's method is better when * You can look at all of the edges at once * You can hold all of the vertices at once * You can hold a forest, not just one tree Basically, Kruskal's method is more time-saving (you can order the edges by weight and burn through them fast), while Prim's method is more space-saving (you only hold one tree, and only look at edges that connect to vertices in your tree).

### What is the Complexity of kruskal and prim's algorithm?

Complexity prim = O(E+ V logV). E edge and V vertex. kurskal = O(E lgV ).

### Will either kruskal or prim's algorithm work on negative edge graph?

The correctness of either Prim's or Kruskal's algorithm, is not affected by negative edges in the graph. They both work fine with negative edges. The question boils down to "Does a Priority Queue of numbers work with negative numbers?" because of the fact that both Prim's and Kruskal's algorithm use a priority queue. Of course -- as negative numbers are simply numbers smaller than 0. The "&lt;" sign will still work with negative numbers.

### When was William Kruskal born?

William Kruskal was born in 1919.

### When did Joseph Kruskal die?

Joseph Kruskal died in 2010.

### When was Joseph Kruskal born?

Joseph Kruskal was born in 1928.

### When did William Kruskal die?

William Kruskal died in 2005.

### When was Clyde Kruskal born?

Clyde Kruskal was born on 1954-05-25.

### When was Martin David Kruskal born?

Martin David Kruskal was born on 1925-09-28.

### When did Martin David Kruskal die?

Martin David Kruskal died on 2006-12-26.