Graph Magics



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(N2), 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:
  1. 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.

  2. 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.

  3. 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(N2).

Restrictions:

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

Optimizations:

  1. 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

 
Copyright 2004-2017 Dumitru Ciubatii. All rights reserved.
Protected by copyright laws and international treaties.