of graph is subgraph that is tree which connects all the vertices togetherso it 'spansthe original graph but using fewer edges hereminimal refers to the sum of all the weights of the edges contained in that treeso minimal spanning tree has total weight less than or equal to the total weight of every other spanning tree as we shall seethere will not necessarily be unique minimal spanning tree for given graph observations concerning spanning trees for the other graph algorithms we have covered so farwe started by making some observations which allowed us to come up with an idea for an algorithmas well as strategy for formulating proof that the algorithm did indeed perform as desired soto come up with some ideas which will allow us to develop an algorithm for the minimal spanning tree problemwe shall need to make some observations about minimal spanning trees let us assumefor the time beingthat all the weights in the above graph were equalto give us some idea of what kind of shape minimal spanning tree might have under those circumstances here are some exampleswe can immediately notice that their general shape is such that if we add any of the remaining edgeswe would create circle then we can see that going from one spanning tree to another can be achieved by removing an edge and replacing it by another (to the vertex which would otherwise be unconnectedsuch that no circle is created these observations are not quite sufficient to lead to an algorithmbut they are good enough to let us prove that the algorithms we find do actually work greedy algorithms we say that an algorithm is greedy if it makes its decisions based only on what is best from the point of view of 'local considerations'with no concern about how the decision might affect the overall picture the general idea is to start with an approximationas we did in dijkstra' algorithmand then refine it in series of steps the algorithm is greedy in the sense that the decision at each step is based only on what is best for that next stepand does not consider how that will affect the quality of the final overall solution we shall now consider some greedy approaches to the minimal spanning tree problem prim' algorithm greedy vertex-based approach suppose that we already have spanning tree connecting some set of vertices then we can consider all the edges which connect vertex in to one outside of sand add to one of those that has minimal weight this cannot possibly create circlesince it must add vertex not yet in this process can be repeatedstarting with any vertex to be the sole element of swhich is trivial minimal spanning tree containing no edges this approach is known as prim' algorithm when implementing prim' algorithmone can use either an array or list to keep track of the set of vertices reached so far one could then maintain another array or list closest whichfor each vertex not yet in skeeps track of the vertex in closest to that isthe