This is a step through of an exam style question demonstrating the use of both Prim's and [url=https://en.wikipedia.org/wiki/Kruskal's_algorithm]Kruskal's[/url] algorithms.[br]Prim or Kruskal is selected with the slider. [br]Decide on each step and use the vertical slider to check your answers as you go.[br]The whole sequence can be run as an animation.

[b][url=https://en.wikipedia.org/wiki/Kruskal%27s_algorithm]Kruskal's algorithm[/url][/b] is a [url=https://en.wikipedia.org/wiki/Minimum_spanning_tree#Algorithms]minimum-spanning-tree algorithm[/url] which finds an edge of the least possible weight that connects any two trees in the forest.[sup][url=https://en.wikipedia.org/wiki/Kruskal%27s_algorithm#cite_note-:0-1][1][/url][/sup] It is a [url=https://en.wikipedia.org/wiki/Greedy_algorithm]greedy algorithm[/url] in [url=https://en.wikipedia.org/wiki/Graph_theory]graph theory[/url] as it finds a [url=https://en.wikipedia.org/wiki/Minimum_spanning_tree]minimum spanning tree[/url] for a [url=https://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29]connected[/url] [url=https://en.wikipedia.org/wiki/Glossary_of_graph_theory#Weighted_graphs_and_networks]weighted graph[/url] adding increasing cost arcs at each step.[br][br][b][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm]Prim's algorithm[/url][/b] was developed in 1930 by [url=https://en.wikipedia.org/wiki/Czech_people]Czech[/url] mathematician [url=https://en.wikipedia.org/wiki/Vojt%C4%9Bch_Jarn%C3%ADk]Vojtěch Jarník[/url][sup][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm#cite_note-1][1][/url][/sup] and later rediscovered and republished by [url=https://en.wikipedia.org/wiki/Computer_scientist]computer scientists[/url] [url=https://en.wikipedia.org/wiki/Robert_C._Prim]Robert C. Prim[/url] in 1957[sup][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm#cite_note-2][2][/url][/sup] and [url=https://en.wikipedia.org/wiki/Edsger_W._Dijkstra]Edsger W. Dijkstra[/url] in 1959.[sup][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm#cite_note-3][3][/url][/sup] Therefore, it is also sometimes called the [b]DJP algorithm[/b],[sup][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm#cite_note-pr02-4][4][/url][/sup] [b]Jarník's algorithm[/b],[sup][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm#cite_note-5][5][/url][/sup] the [b]Prim–Jarník algorithm[/b],[sup][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm#cite_note-6][6][/url][/sup] or the [b]Prim–Dijkstra algorithm[/b].[sup][url=https://en.wikipedia.org/wiki/Prim%27s_algorithm#cite_note-chertar-7][7][/url][/sup]