Minimum Spanning Tree

Greedy Algorithms

Dijkstra's algorithm showed how to find the shortest distance to a point by always choosing the path with the minimum distance. This way you know the shortest distance to each node once you're done with it. This is an example of a greedy algorithm, an algorithm that picks the optimal (or "greedy") choice each time in order to reach an overall solution. Often, the greedy approach can reach an optimal final solution, and it's usually very efficient.

For simple non-graph examples, see the scheduler challenges where you can optimize the overall schedule by always picking the earliest or latest time as you go through the day.

Here's another problem that can be solved with a greedy algorithm that's similar to Dijkstra's.

Minimum Spanning Tree

An electric company needs to connect wires to every building in a city. It wants to use as little wiring as possible which means it will avoid creating any loops. It just needs to create a spanning tree across the graph. In fact, it wants to find the tree with the minimum total length that connects every node on the graph, or the minimum spanning tree. What is an algorithm that can find this?

The above chart shows the minimum spanning tree for a graph. Notice that you can't swap any selected edge with a shorter one and still keep every node connected. What algorithm could be used to discover this tree?

Prim's Animation
Enter a 0 in this visualization and click the button to run Prim's algorithm from node 0. See also Example Networks1 for a walk-through of the algorithm.

Challenge

You will be given a 'adjacency matrix' of input as before. Start from Node 0 and use Prim's Algorithm to find the minimum spanning tree for the input. Print out each edge in the tree in the order that it's added.

Sample Input

1
10
0 4 1 4 0 0 0 0 0 0
4 0 5 0 9 9 0 7 0 0
1 5 0 3 0 0 0 9 0 0
4 0 3 0 0 0 0 10 0 18
0 9 0 0 0 2 4 0 6 0
0 9 0 0 2 0 2 8 0 0
0 0 0 0 4 2 0 9 3 9
0 7 9 10 0 8 9 0 0 8
0 0 0 0 6 0 3 0 0 9
0 0 0 18 0 0 9 8 9 0

Sample Output

1 3 4 7 8 2 2 3 8