of all the spanning trees given in fig the one that is highlighted is called the minimum spanning treeas it has the lowest cost associated with it (weighted grapha (total cost (total cost (total cost (total cost (total cost (total cost (total cost (total cost (total cost figure weighted graph and its spanning trees applications of minimum spanning trees msts are widely used for designing networks for instancepeople separated by varying distances wish to be connected together through telephone network minimum spanning tree is used to determine the least costly paths with no cycles in this networkthereby providing connection that has the minimum cost involved msts are used to find airline routes while the vertices in the graph denote citiesedges represent the routes between these cities no doubtmore the distance between the citieshigher will be the amount charged thereforemsts are used to optimize airline routes by finding the least costly path with no cycles msts are also used to find the cheapest way to connect terminalssuch as citieselectronic components or computers via roadsairlinesrailwayswires or telephone lines msts are applied in routing algorithms for finding the most efficient path prim' algorithm prim' algorithm is greedy algorithm that is used to form minimum spanning tree for connected weighted undirected graph in other wordsthe algorithm builds tree that includes every vertex and subset of the edges in such way that the total weight of all the edges in the tree is minimized for thisthe algorithm maintains three sets of vertices which can be given as belowtree vertices vertices that are part of the minimum spanning tree fringe vertices vertices that are currently not part of tbut are adjacent to some tree vertex unseen vertices vertices that are neither tree vertices nor fringe vertices fall under this category the steps involved in the prim' algorithm are shown in fig choose starting vertex branch out from the starting vertex and during each iterationstep select starting vertex select new vertex and an edge step repeat steps and until there are fringe vertices basicallyduring each iteration step select an edge connecting the tree vertex and of the algorithmwe have to fringe vertex that has minimum weight step add the selected edge and the vertex to the select vertex from the fringe minimum spanning tree vertices in such way that the [end of loopedge connecting the tree vertex step exit and the new vertex has the figure prim' algorithm minimum weight assigned to it