time [ 69 ]. Even better, the algorithms required for fast calculations are not
too complicated (one common algorithm, Prim's algorithm, is, in fact, very
similar to Dijkstra's algorithm for finding the shortest paths) [ 68 ]. The
operation of this algorithm starts out with an array of distances, d, from the
minimum spanning tree for each vertex in the graph. Initially, all distances
should be set to infinity (or another large number) except for the vertex that
we will use to "seed" the minimum spanning tree (the first vertex in the
tree) [ 68 ]. After that vertex is added to the tree, each of its neighbors will
have their distances to the tree updated appropriately [ 68 ]. The closest
vertex to the minimum spanning tree should then be added to the tree, and
the process of checking its neighbors to see if they can reach the tree more
quickly via the new vertex than any other vertex in the tree should be
repeated [ 68 ].To implement Prim’s Algorithm on a network example and
find its minimum spanning tree.The following steps are used[ 70 ]:
- At first we declare an array namedclosed list.
- And consider the open list as a priority queuewith min-heap.
Adding a node and its edge to the closed list indicates that we
have found an edge that links the node into the minimal spanning tree. As a
node is added to the closed list, its successors (immediately adjacent nodes)
are examined and added to a priority queue of open nodes (as shown in
figure 3.3) [ 70 ].