minimum spanning trees suppose we wish to connect all the computers in new office building using the least amount of cable we can model this problem using weighted graph whose vertices represent the computersand whose edges represent all the possible pairs (uvof computerswhere the weight ((vu)of edge (vuis equal to the amount of cable needed to connect computer to computer rather than computing shortest path tree from some particular vertex vwe are interested instead in finding (freetree that contains all the vertices of and has the minimum total weight over all such trees methods for finding such tree are the focus of this section problem definition given weighted undirected graph gwe are interested in finding tree that contains all the vertices in and minimizes the sum treesuch as thisthat contains every vertex of connected graph is said to be spanning treeand the problem of computing spanning tree with smallest total weight is known as the minimum spanning tree (or mstproblem the development of efficient algorithms for the minimum spanning tree problem predates the modern notion of computer science itself in this sectionwe discuss two classic algorithms for solving the mst problem these algorithms are both applications of the greedy methodwhichas was discussed briefly in the previous sectionis based on choosing objects to join growing collection by iteratively picking an object that minimizes some cost function the first algorithm we discuss is kruskal' algorithmwhich "growsthe mst in clusters by considering edges in order of their weights the second algorithm we discuss is the prim-jarnik algorithmwhich grows the mst from single root vertexmuch in the same way as dijkstra' shortest-path algorithm as in section in order to simplify the description of the algorithmswe assumein the followingthat the input graph is undirected (that isall its edges are undirectedand simple (that isit has no self-loops and no parallel edgeshencewe denote the edges of as unordered vertex pairs ( ,zbefore we discuss the details of these algorithmshoweverlet us give crucial fact about minimum spanning trees that forms the basis of the algorithms crucial fact about minimum spanning trees