Prim's MST Algorithm

The MST problem was introduced in Chapter 5, Greedy Algorithms, and is defined as follows:

"Given a graph, G = < V, E >, where V is the set of vertices and E is the set of edges, each associated with an edge weight, find a tree, T, that spans all vertices in V and has the minimum total weight."

In Chapter 5, Greedy Algorithm, we discussed the practical applications of the MST problem and Kruskal's algorithm, which finds an MST in a given graph. Kruskal's algorithm adds all the edges of the graph to a min-heap and greedily adds minimum-cost edges to MST, checking that no cycles are formed in the tree on each addition.

The idea behind Prim's algorithm (also known as Jarvik's algorithm) is similar to that of BFS. The algorithm starts by adding the starting vertex to a frontier, which consists of the set of previously visited vertices and then iteratively explores the vertices adjacent to the current frontier. However, while choosing...