Applications of Kruskal and Prim's algorithms

Could anyone please give some applications of the two algorithms开发者_开发技巧, where and which applications they can be used for?

Minimum spanning trees were first studied for ways to lay out electrical networks in a way that minimizes the total cost of the wiring. In a minimum spanning tree, all the nodes (houses) would be connected to power by wires in a way that has minimum cost and redundancy (cutting any wire necessarily cuts the power grid into two pieces).

Since then, the problem has been well-studied and is often used as a subroutine in more complex algorithms. The Christofides algorithm for finding approximate solutions to the Traveling Salesman Problem uses it in a key step, as do some algorithms for finding Steiner trees.

Minimum spanning trees have also been used to generate mazes. Both Kruskal's and Prim's algorithm have been used this way, often creating high-quality mazes.

If you're interested in a full history of the minimum spanning tree problem, its applications, and its algorithms, there is a truly excellent paper available here that covers all of these. I'd strongly suggest giving it a read!

Hope this helps!

Quoting Wikipedia:

One example would be a cable TV company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost.

Source: http://en.wikipedia.org/wiki/Minimum_spanning_tree

First you must understand that both Prim's and Kruskal's algorithm are useful for finding Minimum spanning Tree in a Graph. One of the pratical applications of minimal spanning tree, I can think of is connecting different offices of the same company with least cost.

Both Prims And Kruskal Algorithms are used to find the minimum spanning trees. Now the applications of Kruskal and Prims Algorithm are basically the applications of MST. So what are the applications of MST?

Well, to answer a few, here are some of the areas in which you will find them usable:

1. If you want to connect several cities using highways or rail networks, you can use these algos to find the minimum length of roads/railtracks connecting all these cities.
2. Network Design - Suppose you have a business with several offices. You have to lease phone cables to connect all these offices. So you can make use of these algos to find out what is the minimum cost to connect all your offices with minimum use of phone cables.
3. Can be used to find the travelling salesman problem. This is a very famous problem using MST.
4. You want to apply a set of houses with - Electric Power, Telephone Lines, Sewage Lines.
5. Designing Local Area Networks.

• Topology
• Cartography
• Geometry
• Clustering
• Routing Algorithms
• Generation of Mazes
• Mechanical / Electrical / Computer Networks
• Study of Molecular bonds in Chemistry

Applications of Kruskal and Prim's algorithms often come up in computer networking. For example, if you have a large LAN with many switches, finding a minimum spanning tree will be vital to ensure that only a minimum number of packets will be transmitted across the network.