Minimum spanning tree (MST) shown in green!

# The Minimum Spanning Tree Algorithm

A telecommunication company wants to connect all the blocks in a new neighborhood. However, the easiest possibility to install new cables is to bury them alongside existing roads. So the company decides to use hubs which are placed at road junctions. How can the installation cost be minimized if the price for connecting two hubs corresponds to the length of the cable attaching them?

Considering the roads as a graph, the above example is an instance of the Minimum Spanning Tree problem. Prim's and Kruskal's algorithms are two notable algorithms which can be used to find the minimum subset of edges in a weighted undirected graph connecting all nodes.

SVG Download

## Legend

 Node Edge with weight 50

## Which graph do you want to execute the algorithm on?

### Modify it to your desire:

• To create a node, make a double-click in the drawing area.
• To create an edge, first click on the output node and then click on the destination node.
• The edge weight can be changed by double clicking on the edge.
• Right-clicking deletes edges and nodes.

Download

### Upload an existing graph:

A occured when reading from file: the contents:

SVG Download

## Legend

 Root Node, an arbitrary node which is used as the root of MST. Node that is currently being processed Node that is in the queue Edge used for building Minimum Spanning Tree.

## Algorithm status

BEGIN

T ← ∅

FOR i ← 1, ..., n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

d(v[1]) ← 0, parent(v[1]) ← v[1]

WHILE queue ≠ ∅ DO

u ← queue.extractMin()

IF parent(u) ≠ u

T.add({parent(u), u})

FOR ALL {u, w} ∈ E do

IF w ∈ queue AND l(u, w) < d(w) THEN

d(w) ← l(u, w), parent(w) ← u

ELSE IF parent(w) = NULL THEN

d(w) ← l(u, w), parent(w) ← u

queue.insert(w)

END

### Queue:

Your browser does not support HTML5 Canvas. Please use a modern browser, i.e.Mozilla Firefox

## Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.

SVG Download

## Legend

 Root Node, an arbitrary node which is used as the root of MST. Node removed from the queue

## In which order are the nodes removed from the queue?

Your task is to click on the nodes of the graph in the order they are removed from the queue.
This corresponds to the order which the nodes were marked red during the execution of the algorithm.

## Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.

SVG Download

## Legend

 Root Node, an arbitrary node which is used as the root of MST. Node that is currently being processed Node that is in the queue Edge used for building Minimum Spanning Tree.

## Test your knowledge: How does the algorithm decide?

BEGIN

T ← ∅

FOR i ← 1, ..., n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

d(v[1]) ← 0, parent(v[1]) ← v[1]

WHILE queue ≠ ∅ DO

u ← queue.extractMin()

IF parent(u) ≠ u

T.add({parent(u), u})

FOR ALL {u, w} ∈ E do

IF w ∈ queue AND l(u, w) < d(w) THEN

d(w) ← l(u, w), parent(w) ← u

ELSE IF parent(w) = NULL THEN

d(w) ← l(u, w), parent(w) ← u

queue.insert(w)

END

## Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.