Tuesday, 10 May 2011

What is the use of kruskal's algorithn in our daily life?

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