The Kruskal’s algorithm is usually used to find minimum spanning tree i.e. the possible smallest tree that contains all the vertices. The standard application is to a problem like phone network design. Suppose, you have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn't a tree you can always remove some edges and save money. A less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.
No comments:
Post a Comment