Using Spanning Trees to Reduce Costs, Application of Trees in Graph Theory

The video begins with the definitions of tree, spanning tree, and minimum spanning tree. Then we solve an application in which a company needs to lay lay down cables to connect several cities. They want to minimize the cost of connecting all the cities while ensuring that each city is reachable from every other city. The cost estimates in thousands of dollars for connecting pairs of cities are given. We draw a complete graph in which vertices represent cities and edges represent the cost of connecting the cities. Then we use Kruskal's algorithm to to find the minimum spanning tree and estimate the cost of the project based on that minimum spanning tree.

[srividya]

Hello Ms Hern! Thank you very much for sharing these easy-to-learn videos. They impart better and a clear understanding of concepts. Could you please explain Prim’s Algorithm. Thanks so much.