scientist Robert C. Prim in 1957and rediscovered by Edsger Dijkstrain
- Therefore it is also sometimes called the DJP algorithm, the Jarník
algorithm, or the Prim–Jarník algorithm.[69].Prim's algorithm is faster on
dense graphs and it isa simple and fast method to construct the minimum-
cost spanning tree of a graph by selecting edges from the graph one-by-one
and adding those edges to the spanning tree [ 67 ]. This algorithm finds a
subset of the edges that forms a tree that includes every vertex, where the
total weight of all the edges in the tree is minimized. Prim's method starts
with one vertex of a graph, and adds the smallest edge that grows the tree
by one more vertex [ 67 ].
3. 5 .1 Find Minimum Spanning Trees using Prim’ algorithm.
The idea behind minimum spanning trees is simple: given a graph
with weighted edges, find a tree of edges with the minimum total weight.A
spanning tree isa graph that satisfies these properties: connected, acyclic,
and consisting of |V| - 1 edges [ 68 ]. (In fact, any two of the three conditions
imply the third condition.) In practice,this means that a spanning tree is a
collection of edges that connect any two nodes via a single path. Spanning
trees often come up in computer networking [ 39 ]. For instance, if there is a
large LAN with a lot of switches, it might be useful to find a minimum
spanning tree so that only the minimum number of packets need to be
relayed across the network and multiple copies of the same packet donot
arrive via different paths [ 68 ]. Other real-world problems include laying
out electrical grids, reportedly the original motivation for Boruvka's
algorithm, one of the first algorithms for finding minimum spanning trees
[ 68 ]. It shouldnot be surprising that it would be better to find a minimum
spanning tree than just any old spanning tree; if one spanning tree on a
network would involve taking the most congested, slowest path, it is
probably not going tobeideal [ 68 ].So to find a minimum spanning tree, it
turns out that finding minimum spanning trees can be done in polynomial