A connected graph is a graph that has a path from every node to every other node. For this project, you are given a connected, undirected, weighted graph in which every edge has a non-negative number called its weight. You must create a new graph with the same vertices as the original graph, but possibly fewer edges. Such a graph is called a subgraph, and we are looking for a particular subgraph called the minimal spanning tree, which has these properties:

1. It is a subgraph of the original graph.

2. It is still connected.

3. Among all possible connected subgraphs, it has a minimal total weight of its edges.

The algorithm you’ll use was first devised by the Czech mathematician Vojtech Jarnik in 1930 and later rediscovered by Robert Prim (1957) and Edsger Dijkstra (1959). The algorithm starts by picking any vertex and creating a set V that contains only this vertex.We also create a set of edges, E, that initially begins as the empty set. The remainder of the algorithm adds edges to E one at a time. Each new edge that you add must be the lowest-weight edge that connects a vertex from V to a vertex that is not in V—and after the edge is added, the vertex that was not in V is added to V. The process continues until V contains all vertices.