Minimum Spanning Trees

Created by Flash-NDQ

I: Introduction

Given:

Suppose that, In a province, there are a lot of villages, and we have to build a electrical system to supply for these villages, it has to ensure that, the minimum cost is achieved. To connect n villages, n-1 wires are needed (each connect two villages).

Model this problem with a connected, un-directed graph G = (V, E)
Where:

• V is the set of villages
• E is the set of possible interconnections between pairs of villages.
• (u,v) is a edge ∈ E
• w(u,v) is the cost (amount of wire needed) to connect u and v.

Required:

Find an acyclic subset T ⊆ E that connects all of the node (vertices, villages) and whose total weight 

is minimized.

• Since T is acyclic and connects all of the vertices, it must form a tree => Called Spanning Tree.
• The tree T in the required the total weight is minimized named Minimum Spanning Tree.

Figure 1: A minimum spanning tree for a connected graph,

weights on edges, the edges in a minimum spanning tree are shaded.

In Figure 1, the total weight of tree is 37. The minimum spanning tree is not unique: removing the edge (b,c) and replacing it with the edge (a,h) yields another spanning tree with weight 37.

The two algorithm in Section III which are greedy algorithms will find a minimum spanning tree. They do yield a spanning tree with minimum weight.

Applications of minimum spanning tree:

• Civil network planning
• Routing protocols computer networks
• Cluster Analysis

II: Growing a minimum spanning tree

In this section introduces a "generic" minimum spanning tree method that grows a spanning tree by adding one edge at a time.

Given:

• A connected, un-directed graph G = (V, E)
• Weight Function w: E -> R

Required:

• Find a minimum spanning tree for G.

Solving problem:

The generic method manages a set of edges A, maintaining the following loop variant;

•    Prior to each iteration, A is a subset of some minimum spanning tree.

At each step, we determine a edge (u,v) that we can add to A without violating this invariant, in the sense that A ∪ {(u, v)} is also a subset of a minimum spanning tree. We call such an edge a safe edge for A, since we can add it safely to A while maintaining the invariant.

?

1 2 3 4 5 6

GENERIC-MST(G,w)     A = Ø     while A does not form a spanning tree  // this means that, all nodes are not connected           Find an edge (u, v) that is safe for A           A = A ∪ {(u,v)}     return A

Explanation:

• Initialization: After line 2, the set A trivially satisfies the loop invariant. 
• Maintenance: The loop in lines 3–5 maintains the invariant by adding only safe edges.  
• Termination: All edges added to A are in a minimum spanning tree, and so the set A returned in line 6 must be a minimum spanning tree.  

How to determine safe edges by using a rule (which is used in the Section III for two algorithms)

Some definitions:

• A cut (S,V - S) of an  undirected graph G = (V, E) is a partition of V. This is illustrated in Figure 2.
• Edge (u,v) ∈ E crosses the cut (S, V - S) if one of its endpoints is in S and the other is in V-S.
• A cut respects a set A of edges if no edge in A crosses the cut .
• An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.  

Rule for recognizing safe edges is given by the following theorem. 

Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a subset of E that is included in some minimum spanning tree for G, let (S, V- S) be any cut of G that respects A, and let (u, v) be a light edge crossing (S, V- S). Then, edge (u, v) is safe for A.

Figure 2: Two ways of viewing a cut (S, S - V) of the graph from Figure 1

III: The algorithms of Kruskal and Prim

These algorithms use a specific rule to determine a safe edge in line 4 of GENERIC-MST.

A. Kruskal's algorithm

Kruskal’s algorithm finds a safe edge to add to the growing forest by finding, of all the edges that connect any two trees in the forest, and edge (u,v) of least weight. Kruskal’s algorithm qualifies as a greedy algorithm because at each step it adds to the forest an edge of least possible weight.

• This algorithm uses disjoint-set data structure to maintain several disjoint sets of elements.
• Each set contains the vertices in one tree of the current forest.  
• The operation FIND-SET(u) returns a representative element from the set that contains u (sub-tree that contain u). Thus, we can determine whether two vertices u and v belong to the same tree by testing whether FIND-SET(u) equals FIND-SET(v).

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

MST-KRUSKAL(G,w)        A =  Ø   // Init the set A ti the empty set.        for each vertex v ∈ G.V    // Create |V| trees (or element), one containing each vertex        {                MAKE-SET(v)         }        Sort the edges of G.E into nondecreasing order by weight w  // examines edges in order of weight, lowest to highest        for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight        {               if FIND-SET(u) ≠ FIND-SET(v) // whether the endpoints u and v belong the same tree or not (to ensure no circle)               {                       A = A ∪ {(u,v)}  // add edge (u,v) to A if it satisfies.                       UNION(u,v)  // merge the vertices of the two trees.               }        }        return A

Here is an example of this algorithm

Figure 3:  The execution of Kruskal’s algorithm on the graph from Figure 1

Here is an example code of Kruskal' algorithm
// Code: 

?

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include <string.h>  
4. // a structure to represent a weighted edge in graph  
5. struct Edge  
6. {  
7.     int src, dest, weight;  // source, destination nodes.  
8. };  
9.     
10. // a structure to represent a connected, undirected and weighted graph  
11. struct Graph  
12. {  
13.     // V-> Number of vertices, E-> Number of edges  
14.     int V, E;  
15.     
16.     // graph is represented as an array of edges. Since the graph is  
17.     // undirected, the edge from src to dest is also edge from dest  
18.     // to src. Both are counted as 1 edge here.  
19.     struct Edge* edge;  
20. };  
21.     
22. // Creates a graph with V vertices and E edges  
23. struct Graph* createGraph(int V, int E)  
24. {  
25.     struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );  
26.     graph->V = V;  
27.     graph->E = E;  
28.     
29.     graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );  
30.     
31.     return graph;  
32. }  
33.     
34. // A structure to represent a subset for union-find  
35. struct subset  
36. {  
37.     int *list;  // store vaule of vertice which has been unioned into a tree.  
38.     int index; // index for list above or number of elements  
39. };  
40.     
41. // A utility function to find set of the element i  
42. int find(struct subset subsets[], int i, int V)  
43. {  
44.     // find root and make root as parent of i (path compression)  
45.     int subsetIndex;  
46.     for(subsetIndex = 0; subsetIndex < V; subsetIndex++)  
47.     {  
48.         int listIndex;  
49.         for(listIndex = 0; listIndex < subsets[subsetIndex].index; listIndex++)  
50.         {  
51.             if(i == subsets[subsetIndex].list[listIndex])  
52.             {  
53.                 return subsetIndex;  
54.             }  
55.         }  
56.     }  
57. }  
58.     
59. // A function that does union of two sets of x and y  
60. // (uses union by rank)  
61. void Union(struct subset subsets[], int x, int y, int V)  
62. {  
63.     int xroot = find(subsets, x, V);  
64.     int yroot = find(subsets, y, V);  
65.    
66.     // Attach smaller rank tree under root of high rank tree  
67.     // (Union by Rank)  
68.     if (subsets[xroot].index < subsets[yroot].index)  
69.     {  
70.         //subsets[xroot].parent = yroot;  
71.         int index1;  
72.         for(index1  = 0; index1 < subsets[xroot].index; index1++)  
73.         {  
74.             subsets[yroot].list[subsets[yroot].index++] = subsets[xroot].list[index1];  
75.         }  
76.         subsets[xroot].index = 0;  
77.     }  
78.     else  
79.     {   
80.         int index1;  
81.         for(index1  = 0; index1 < subsets[yroot].index; index1++)  
82.         {  
83.             subsets[xroot].list[subsets[xroot].index++] = subsets[yroot].list[index1];  
84.         }  
85.         subsets[yroot].index = 0;  
86.     }  
87. }  
88.     
89. // Compare two edges according to their weights.  
90. // Used in qsort() for sorting an array of edges  
91. int myComp(const void* a, const void* b)  
92. {  
93.     struct Edge* a1 = (struct Edge*)a;  
94.     struct Edge* b1 = (struct Edge*)b;  
95.     return a1->weight > b1->weight;  
96. }  
97.     
98. // The main function to construct MST using Kruskal's algorithm  
99. void KruskalMST(struct Graph* graph)  
100. {  
101.     int V = graph->V;  
102.     int E = graph->E;  
103.     struct Edge result[V];  // This will store the resultant MST  
104.     int e1 = 0;  // An index variable, used for result[]  
105.     int i = 0;  // An index variable, used for sorted edges  
106.     
107.     // Step 1:  Sort all the edges in non-decreasing order of their weight  
108.     // If we are not allowed to change the given graph, we can create a copy of array of edges  
109.    
110.     qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);  
111.     
112.     // Allocate memory for creating V subsets  
113.     struct subset *subsets = (struct subset*) malloc( V * sizeof(struct subset));  
114.     
115.     // Create V subsets with single elements  
116.     int e;  
117.     int v = 0;  
118.     int usedArray[V];  
119.     int arrayIndex = 0;  
120.     int subsetIndex = 0;  
121.     for (e = 0; e < E; ++e)  
122.     {  
123.         struct Edge checkEdge = graph->edge[e];  
124.         int sourceNum = checkEdge.src;  
125.         int index;  
126.         int flag  = 0;  
127.         //--------------- For source node---------------------------  
128.         for(index = 0; index < arrayIndex; index++)  
129.         {  
130.             if(sourceNum == usedArray[index])  
131.             {  
132.                 flag = 1;  
133.                 break;  
134.             }  
135.         }  
136.         if(flag == 0)  
137.         {  
138.             usedArray[arrayIndex++] = sourceNum;  
139.             subsets[subsetIndex].list = (int*) malloc(sizeof(int));  
140.             subsets[subsetIndex].list[subsets[subsetIndex].index++] = sourceNum;  
141.             subsetIndex++;  
142.         }  
143.         //----------------- For destination node---------------------  
144.         flag = 0;  
145.         int DesNum = checkEdge.dest;  
146.         for(index = 0; index < arrayIndex; index++)  
147.         {  
148.             if(DesNum == usedArray[index])  
149.             {  
150.                 flag = 1;  
151.                 break;  
152.             }  
153.         }  
154.         if(flag == 0)  
155.         {  
156.             usedArray[arrayIndex++] = DesNum;  
157.             subsets[subsetIndex].list = (int*) malloc(sizeof(int));  
158.             subsets[subsetIndex].list[subsets[subsetIndex].index++] = DesNum;  
159.             subsetIndex++;  
160.         }  
161.     }  
162.     // Number of edges to be taken is equal to V-1  
163.     while (e1 < V - 1)  
164.     {  
165.         // Step 2: Pick the smallest edge. And increment the index for next iteration  
166.         struct Edge next_edge = graph->edge[i++];  
167.         int x = find(subsets, next_edge.src, V);  
168.         int y = find(subsets, next_edge.dest, V);  
169.         // If including this edge does't cause cycle, include it  
170.         // in result and increment the index of result for next edge  
171.         if (x != y)  
172.         {  
173.             result[e1++] = next_edge;  
174.             Union(subsets, next_edge.src, next_edge.dest, V);  
175.         }  
176.         // Else discard the next_edge  
177.     }  
178.     // print the contents of result[] to display the built MST  
179.     printf("Following are the edges in the constructed MST\n");  
180.     int sum = 0;  
181.     for (i = 0; i < e1; ++i)  
182.     {  
183.         printf(" Edge :%d -> %d == %d\n", result[i].src, result[i].dest, result[i].weight);  
184.         sum = sum + result[i].weight;  
185.     }  
186.     printf("\n ------> Minimum weight = %d\n",sum);  
187.     return;  
188. }  
189.     
190. // Driver program to test above functions  
191. int main()  
192. {  
193.     /* Let us create following weighted graph 
194.              10 
195.         20-------30 
196.         |  \     | 
197.        6|   5\   |15 
198.         |      \ | 
199.         70-------50 
200.             4       */  
201.     int V = 4;  // Number of vertices in graph  
202.     int E = 5;  // Number of edges in graph  
203.     struct Graph* graph = createGraph(V, E);  
204.     
205.     // add edge 0-1  
206.     graph->edge[0].src = 20;  
207.     graph->edge[0].dest = 30;  
208.     graph->edge[0].weight = 10;  
209.     
210.     // add edge 0-2  
211.     graph->edge[1].src = 20;  
212.     graph->edge[1].dest = 70;  
213.     graph->edge[1].weight = 6;  
214.     
215.     // add edge 0-3  
216.     graph->edge[2].src = 20;  
217.     graph->edge[2].dest = 50;  
218.     graph->edge[2].weight = 5;  
219.     
220.     // add edge 1-3  
221.     graph->edge[3].src = 30;  
222.     graph->edge[3].dest = 50;  
223.     graph->edge[3].weight = 15;  
224.     
225.     // add edge 2-3  
226.     graph->edge[4].src = 70;  
227.     graph->edge[4].dest = 50;  
228.     graph->edge[4].weight = 4;  
229.    
230.     KruskalMST(graph);  
231.     
232.     return 0;  
233. }  

// Output:

B: Prim's algorithm