Minimum spanning tree facts for kids

A minimum spanning tree is a special way to connect all the points (called vertices) in a network (called a graph) using the fewest possible connections (called edges) while making sure there are no loops. Imagine you have a bunch of cities, and you want to connect them all with roads so that you can get from any city to any other city. A minimum spanning tree helps you do this using the shortest or cheapest roads possible, without building any unnecessary circular routes.

The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length.

Sometimes, a graph can have more than one minimum spanning tree. This happens if some connections have the exact same "cost" or "length." If all the connections have different costs, then there will be only one unique minimum spanning tree.

Finding a Minimum Spanning Tree

Finding a minimum spanning tree means using a set of steps, called an algorithm, to pick the best connections.

A Simple Idea

Here's a basic idea of how an algorithm might work:

• Start with no connections.
• Keep adding the cheapest connection that doesn't create a loop.
• Do this until all points are connected.

A "loop" means starting at one point, traveling through other points, and ending up back at your starting point without using any connection twice.

Who Discovered These Algorithms?

The very first algorithm for finding a minimum spanning tree was created by a Czech scientist named Otakar Borůvka in 1926. He was trying to figure out the best way to connect cities in Moravia with electricity lines. His method is now known as Borůvka's algorithm.

Today, two other famous algorithms are often used:

• Prim's algorithm: This was first thought of by Vojtěch Jarník in 1930 and later made practical by Robert C. Prim in 1957. Edsger W. Dijkstra also found it independently in 1959.
• Kruskal's algorithm: This was published by Joseph Kruskal in 1956.

All three of these algorithms are considered "greedy" algorithms. This means they make the best choice at each step, hoping it will lead to the best overall solution. They are also quite fast for computers to solve.

The fastest known algorithm for finding a minimum spanning tree was developed by Bernard Chazelle. It's very complex, but it works incredibly quickly, almost as fast as just looking at all the connections once.