Introduction
Create a graph
Run the algorithm
Description of the algorithm
Exercise 1
Exercise 2
More

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.

This tutorial presents Prim's algorithm which calculates the minimum spanning tree (MST) of a connected weighted graphs. For a comparison you can also find an introduction to Kruskal's algorithm.

What do you want to do first?

SVG Download

Legend

	Node
	Edge with weight 50

Legend

Which graph do you want to execute the algorithm on?

Start with an example graph:

Select

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 the modified graph:

Download

Upload an existing graph:

occured when reading from file:

the contents:

What next?

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.

Legend

Algorithm status

rewind fast forward

Explanation
Pseudocode

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:

Task is terminated if the tab is changed.

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

What is the cheapest way to connect all vertices?

Minimum Spanning Tree

Given a connected, undirected graph, a spanning tree of that graph is an acyclic subgraph that connects all vertices. Obviously, a graph may have many spanning trees. Weights may be assigned to each edge of the graph, then the total weight of a subgraph is the sum of its edge weights. The spanning tree with the weight less than or equal to all other spanning trees is called the minimum spanning tree (MST). More generally, any undirected graph has a minimum spanning forest (MSF), which is a union of minimum trees for its connected components.

Prim's algorithm is a greedy algorithm (a problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum) that efficiently finds the minimum spanning tree for the connected weighted undirected graphs. Although this algorithm may be modifed to find minimum spanning forest for unconnected graphs, other methods such as Kruskal's algorithm are recommended.

Idea of the algorithm

Kante vor Update — Vertices are added to the tree using the shortest possible edge which connects them to one of the nodes already in the tree.

The algorithm initializes a tree with a single vertex chosen arbitrarily, and in each round the tree is grown by one edge. This edge has the minimum weight among all the edges that connect the tree to the vertices not yet on the tree. The process is continued until all the vertices are added to the tree.

The most efficient way to implement the algorithm is using a queue. This queue keeps track of all the nodes that are visited but not yet added to the tree. The order of the nodes in the queue is determined using the distance of each node to the tree. Hence, in each round the vertex that is connected to the tree by the cheapest edge is removed from the queue.

The algorithm may be described step-by-step. First is the initialization part:

an arbitrary node is selected as the root of the tree.
a distance array keeps track of minimum weighted edge connecting each vertex to the tree. The Root node has distance zero, and for all other vertices there is no edge to the tree, so their distance is set to infinity.
the root node is added to the queue.

Next, the algorithm iterates over the queue. In each round, the node in front of the queue is extracted. Initially this may be only the root node. Then all the neighbouring vertices of the removed node are considered with their respective edges. Each neighbour is checked whether it is in the queue and its connecting edge weighs less than the current distance value for that neighbour. If this is the case, the cost of this neighbour can be reduced to the new value. Otherwise, if the node has not yet been visited then it most be inserted into the queue, so the edges going out of it may be considered later.

The above iteration continues until no more nodes are included in the queue. Then the algorithm is finished and as the result it returns all the edges used for building the minimum spanning tree.

Construction of the MST

At each update of the distance array, the algorithm stores the updated edge as the predecssor of the node. The resulting tree may be represented as the union of all these edges.

What now?

Create a graph and play through the algorithm

Test your knowledge in the exercises

SVG Download

Legend

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

Legend

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.

Legend

Test your knowledge: How does the algorithm decide?

rewind Forward: Next question

Explanation
Pseudocode

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.

What is the pseudocode of the algorithm?

Input: Weighted, connected, undirected graph G = (V, E) with weight function l.
Output: A list T of edges representing the MST.

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

How fast is the algorithm?

Speed of the algorithms

The Speed of an algorithm is the total number of individual steps which are performed during the execution. These steps are for example:

Assignments – Set distance of a node to 20.
Comparisons – Is 20 greater than 23?
Comparison and assignment – If 20 is greater than 15, set variable n to 20
Simple Arithmetic Operations – What is 5 + 5?

Since it can be very difficult to count all individual steps, it is desirable to only count the approximate magnitude of the number of steps. This is also called the running time of an algorithm. Particularly, it is intersting to know the running time of an algorithm based on the size of the input (in this case the number of the vertices and the edges of the graph).

Running time of Prim's algorithm

Suppose that the MST for a graph with n vertices and m edges is going to be computed.

Since each node of the graph is considered separately, there are at least n iterations.

In each iteration, the node in front of the queue is removed and all its neighbours are checked. Updating the distance value for each neighbour and selecting the node with minimum distance requires n steps. So in the case that the queue is implemented using a simple list, the algorithm need n · n steps.

It is possible to improve the running time of the algorithm by improving the queue operations. Using a Fibonnaci heap, the running time of the algorithm may be reduced to m + n · log(n) .

Does the algorithm work correctly?

Let G=(V, E) be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in the subgraph that is constructed to a vertex outside the subgraph. Since G is connected, there will always be a path to every vertex. The output T of Prim's algorithm is a tree, because the edge and vertex added to tree T are connected.

Let T1 be a minimum spanning tree of graph G. If T1=T then T is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree T that is not in tree T1, and P be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set P and the other is not. Since tree T1 is a spanning tree of graph G, there is a path in tree T1 joining the two endpoints. As one travels along the path, one must encounter at least one edge f joining a vertex in set P to one that is not in set P. Now, at the iteration when edge e was added to tree T, edge f could also have been added and it would be added instead of edge e if its weight was less than e, and since edge f was not added, we conclude that

w(f) ≥ w(e)

Example graph — (Left) Sets P, and edges e, f.
(Right) T1 shown in green.

Let tree T2 be the graph obtained by removing edge f from and adding edge e to tree T1. It is easy to show that tree T2 is connected, has the same number of edges as tree T1, and the total weights of its edges is not larger than that of tree T1, therefore it is also a minimum spanning tree of graph G and it contains edge e and all the edges added before it during the construction of set P. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph G that is identical to tree T. This shows T is a minimum spanning tree.

The algorithm is very similar to the Dijikstra's algorithm! Is there any difference between the two?

Comparing the two algorithms one will find that both algorithms are using a queue of unvisited nodes with corresponding distance value d. In each round the minimum element of the queue is extracted, and the distane values are modified accordingly. (If you are not familiar with the Dijikstra's algorithm this tutorial will help you.)

Dijkstra's algorithm constructs a shortest path tree starting from some source node. A shortest path tree is a tree that connects all nodes in the graph and has the property that the length of any path from the root to any other node in the graph is minimized (figure below). Prim's algorithm constructs a minimum spanning tree for the graph, which is a tree that connects all nodes in the graph and has the least total cost among all trees that connect all the nodes. However, the length of a path between the root and any other node in the MST might not be the shortest path between those two nodes in the original graph.

In order to provide such a functionality in Dijikstra's algorithm, the distance array is updated using the sum of the new edge's weight and the length of the parent node from root. But in Prim's algorithm only the new edge's weight (distance of the new node from the MST) is used for updating the distance array.

Djikstra's algorithm:
// initialization ...
WHILE queue ≠ ∅ DO
    // dequeue...
    FOR ALL {u, w} ∈ E DO
        dist ← d(u) + l(u, w)
        IF w ∈ queue AND dist < d(w) THEN
            d(w) ← dist
        // The rest of algorithm ...

Prim's algorithm:
// initialization ...
WHILE queue ≠ ∅ DO
    // dequeue...
    FOR ALL {u, w} ∈ E DO
        IF w ∈ queue AND l(u, w) < d(w) THEN
            d(w) ← l(u, w)
        // The rest of algorithm ...

Where can I find more information about graph algorithms?

Other graph algorithms are explained on the Website of Chair M9 of the TU München.

Furthermore there is an interesting book about shortest paths: Das Geheimnis des kürzesten Weges

Studying mathematics at the TU München answers all questions about graph theory (if an answer is known).

A last remark about this page's content, goal and citations

Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the mathematical optimization of applied problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the daily research conducted at the chair reaches far beyond that point). These pages shall provide pupils and students with the possibility to (better) understand and fully comprehend the algorithms, which are often of importance in daily life. Therefore, the presentation concentrates on the algorithms' ideas, and often explains them with just minimal or no mathematical notation at all.

Please be advised that the pages presented here have been created within the scope of student theses, supervised by Chair M9. The code and corresponding presentation could only be tested selectively, which is why we cannot guarantee the complete correctness of the pages and the implemented algorithms.

Naturally, we are looking forward to your feedback concerning the page as well as possible inaccuracies or errors. Please use the suggestions link also found in the footer.

To cite this page, please use the following information:

Title: Prim's Algorithm
Authors: Wolfgang F. Riedl, Reza Sefidgar; Technische Universität München
Link: https://www-m9.ma.tum.de/graph-algorithms/mst-prim