Graph Magics

Partners

DocsPal
Free online file Converter and Viewer

Minimal Spanning Tree

Task:

Find a connected ayclic subgraph that contains all nodes of the graph and has the smallest sum of costs of its edges.
Example: Given some villages and a list of possible telephony connections between them having different costs. Find the cheapest way to connect these villages in a telephony network.

Solution:

There are two well-known algorithms for solving this problem: Prim's and Kruskal's.
Prim's algorithm basically runs in O(N²), with some optimizations it runs in O(NlogN) for sparse graphs.
Kruskal's alogrithm basically runs in O(NM), and in O(MlogN) with a good implementation of the algorithm (N is the number of nodes and M is the number of edges).

Here I wil explain Prim's algorithm because it's easier to implement than a good Kruskal's algorithm (the one that runs in O(MlogN)) and because it works substantially faster for a big number of edges.

Prim's Algorithm:

Start with a tree having one node (you can choose anyone). Let this node be i.
Let the distance of a node to a tree represent the cost of the cheapest edge that connects the tree with that node.
Set the distance to i to 0, and the distances to all other nodes to infinity.
If all node are processed then exit, because the minimal spanning tree has been found.
Otherwise, among all unprocessed nodes find the one that has the minimum distance to the tree. Let this node be i. Mark it as processed (thus including it into the tree) and go to point 3.
Note: If distances of all unprocessed nodes are equal to Infinity then no minimal spanning tree exists.
Look at each unprocessed neighbor j (i.e. at those that are not yet included in the tree) of node i. If the distance from j to the tree is greater than the cost of edge between i and j, then set the distance to j to the cost of this edge and mark that j has been reached from i.
Go back to point 2.

Complexity:

All N nodes are processed, and for each the neighbors are updated in O(N). Thus the complexity is O(N²).

Restrictions:

Prim's algorithm doesn't work for graphs that have directed edges.

Optimizations:

For sparse graphs a complexity of O(NlogN) may be obtained. For this purpose a heap is used to store the distances to nodes, and neighbors of each node are stored in lists. In this way the unprocessed node with the minimum distance is found in logN and the update of each node is also done in logN.
Providing that the graph is sparse, each node has few neighbors and thus the average complexity is O(NlogN).

Sample Execution:

Given:

A sample graph made in Graph Magics.

Below execution steps of this algorithm are shown (all images are created in Graph Magics).

Legend:
- unprocessed nodes are colored in light gray
- processed nodes (those that are already included in the tree) are colored in red; same for the edges included in the tree
- a bold gray edge between the tree and a node represents the cheapest one yet found that connects that node to the tree
- the number on a node represents the shortest distance (cheapest edge) from the tree to that node yet found

Starting state:

Node	Processed	Distance from the tree	Parent
1	false	0	null
2	false	Infinity	null
3	false	Infinity	null
4	false	Infinity	null
5	false	Infinity	null
6	false	Infinity	null
7	false	Infinity	null
8	false	Infinity	null
9	false	Infinity	null

Download this graph (viewable with Graph Magics)

Among all unprocessed nodes, 1 has the minimum distance from the tree.

After updating the neighbors of node 1:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	false	11	1
3	false	2	1
4	false	5	1
5	false	Infinity	null
6	false	Infinity	null
7	false	8	1
8	false	3	1
9	false	Infinity	null

Among all unprocessed nodes, 3 has the minimum distance from the tree.

After updating the neighbors of node 3:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	false	11	1
3	true	2	1
4	false	5	1
5	false	Infinity	null
6	false	15	3
7	false	7	3
8	false	3	1
9	false	1	3

Among all unprocessed nodes, 9 has the minimum distance from the tree.

After updating the neighbors of 9:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	false	11	1
3	true	2	1
4	false	5	1
5	false	Infinity	null
6	false	6	9
7	false	7	3
8	false	3	1
9	true	1	3

Among all unprocessed nodes, 8 has the minimum distance from the tree.

After updating the neighbors of 8:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	false	11	1
3	true	2	1
4	false	5	1
5	false	21	8
6	false	6	9
7	false	7	3
8	true	3	1
9	true	1	3

Among all unprocessed nodes, 4 has the minimum distance from the tree.

After updating the neighbors of 4:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	false	11	1
3	true	2	1
4	true	5	1
5	false	21	8
6	false	6	9
7	false	4	4
8	true	3	1
9	true	1	3

Among all unprocessed nodes, 7 has the minimum distance from the tree.

After updating the neighbors of 7:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	false	11	1
3	true	2	1
4	true	5	1
5	false	21	8
6	false	6	9
7	true	4	4
8	true	3	1
9	true	1	3

Among all unprocessed nodes, 6 has the minimum distance from the tree.

After updating the neighbors of 6:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	false	11	1
3	true	2	1
4	true	5	1
5	false	14	6
6	true	6	9
7	true	4	4
8	true	3	1
9	true	1	3

Among all unprocessed nodes, 2 has the minimum distance from the tree.

After updating the neighbors of 2:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	true	11	1
3	true	2	1
4	true	5	1
5	false	5	2
6	true	6	9
7	true	4	4
8	true	3	1
9	true	1	3

Among all unprocessed nodes, 5 has the minimum distance from the tree.

After updating the neighbors of 5:

Node	Processed	Distance from the tree	Parent
1	true	0	null
2	true	11	1
3	true	2	1
4	true	5	1
5	true	5	2
6	true	6	9
7	true	4	4
8	true	3	1
9	true	1	3

All nodes have been processed and thus the minimal spanning tree has been found. It's marked with red in this image.

The cost of this tree is 37 and is equal to the sum of all edges that it contains.

Applications:

Consider some communications stations (for telephony, cable television, Internet etc.) and a list of possible connections between them, having different costs. Find the cheapest way to connect these stations in a network, so that a station is connected to any other (directly, or through intermediate stations). This may be used for example to connect villages to cable television, or to Internet.
The same problem, but instead of connecting communications stations - villages are to be connected with roads.

A graph (arranged in grid) similar to a city rectangular structure

Minimal Spanning Tree applied to the same graph