Minimum Spanning Tree Demonstration
- Author:
- Šárka Voráčová, slik
This is a step through of an exam style question demonstrating the use of both Prim's and Kruskal's algorithms.
Prim or Kruskal is selected with the slider.
Decide on each step and use the vertical slider to check your answers as you go.
The whole sequence can be run as an animation.
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
Prim's algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník[1] and later rediscovered and republished by computer scientists Robert C. Prim in 1957[2] and Edsger W. Dijkstra in 1959.[3] Therefore, it is also sometimes called the DJP algorithm,[4] Jarník's algorithm,[5] the Prim–Jarník algorithm,[6] or the Prim–Dijkstra algorithm.[7]