algorithm can be based on queue minimum spanning tree (mstconsists of the minimum number of edges necessary to connect all graph' vertices slight modification of the depth-first search algorithm on an unweighted graph yields its minimum spanning tree in directed graphedges have direction (often indicated by an arrowa topological sorting algorithm creates list of vertices arranged so that vertex precedes vertex in the list if there' path from to topological sort can be carried out only on daga directedacyclic (no cyclesgraph topological sorting is typically used for scheduling complex projects that consist of tasks contingent on other tasks weighted graphs overview in the last we saw that graph' edges can have direction in this we'll explore another edge featureweight for exampleif vertices in weighted graph represent citiesthe weight of the edges might represent distances between the citiesor costs to fly between themor the number of automobile trips made annually between them ( figure of interest to highway engineerswhen we include weight as feature of graph' edgessome interesting and complex questions arise what is the minimum spanning tree for weighted graphwhat is the shortest (or cheapestdistance from one vertex to anothersuch questions have important applications in the real world we'll first examine weighted but non-directed graph and its minimum spanning tree in the second half of this we'll examine graphs that are both directed and weightedin connection with the famous dijkstra' algorithmused to find the shortest path from one vertex to another minimum spanning tree with weighted graphs to introduce weighted graphs we'll return to the question of the minimum spanning tree creating such tree is bit more complicated with weighted graph than with an unweighted one when all edges are the same length it' fairly straightforward--as we saw in the last -for the algorithm to choose one to add to the minimum spanning tree but when edges can have different weightssome arithmetic is needed to choose the right one an examplecable tv in the jungle suppose we want to install cable television line that connects six towns in the mythical country of magnaguena five links will connect the six citiesbut which five links should they bethe cost of connecting each pair of cities variesso we must pick the route carefully to minimize the overall cost figure shows weighted graph with verticesrepresenting the towns ajobordocolinadanzaerizoand flor each edge has weightshown by number alongside