- an old mst methodcalled baruvka' algorithmworks as follows on graph having vertices and edges with distinct weightslet be subgraph of initially containing just the vertices in while has fewer than edges do for each connected component ci of do find the lowest-weight edge (uvin with in ci and not in ci add (uvto (unless it is already in return prove that this algorithm is correct and that it runs in ( log ntime - let be graph with vertices and edges such that all the edge weights in are integers in the range [ ngive an algorithm for finding minimum spanning tree for in ( logntime - consider diagram of telephone networkwhich is graph whose vertices represent switching centersand whose edges represent communication lines joining pairs of centers edges are marked by their bandwidthand the bandwidth of path is equal to the lowest bandwidth among the path' edges give an algorithm thatgiven network and two switching centers and boutputs the maximum bandwidth of path between and - nasa wants to link stations spread over the country using communication channels each pair of stations has different bandwidth availablewhich is known priori nasa wants to select channels (the minimum possiblein such way that all the stations are linked by the channels and the total bandwidth (defined as the sum of the individual bandwidths of the channelsis maximum give an efficient algorithm for this problem and determine its worst-case time complexity consider the weighted graph (ve)where is the set of stations and is the set of channels between the stations define the weight (eof an edge in as the bandwidth of the corresponding channel - inside the castle of asymptopia there is mazeand along each corridor of the maze there is bag of gold coins the amount of gold in each bag varies noble knightnamed sir paulwill be given the opportunity to walk through the mazepicking up bags of gold he may enter the maze only through door marked "enterand exit through another door marked "exit while in the maze he may not retrace his steps each corridor of the maze has an arrow painted on the wall sir paul may only go down the corridor in the direction of the arrow there is no way to traverse "loopin the maze given map of the mazeincluding the amount of gold in each corridordescribe an algorithm to help sir paul pick up the most gold