Kruskal’s Algorithm

An algorithm which is used to create a minimum spanning tree is attributed to Kruskal’s algorithm. The nodes of the graph are initially considered as n distinct partial trees with one node each. At each step of the algorithm, two distinct partial trees are connected into a single partial tree by an edge of the graph. When only one partial tree exists (after n-1 such steps), it is a minimum spanning tree.

The concern is what connecting arc to use at each step. The answer is to use the arc of minimum cost that connects two distinct trees. To do this, the arcs can be placed in a priority queue based on the weight. The arc of lowest weight is then examined to see if it connects two distinct trees.

To determine if an arc (x, y) connects distinct trees, we can implement the trees with a father field in each node. Then we can traverse all ancestors of x and y to obtain the roots of the trees containing them. If the roots of the two trees are the same node, x and y nodes are already in the same tree, arc (x, y) is discarded, the arc of next lowest weight is examined. Combining two trees simply involves setting the father of the root of one to the root of the other.

Algorithm

• Forming the initial priority queue, i.e., O(e log e)
• Removing the minimum weight arc and adjusting the priority queue, i.e., O(log e).
• Locating the root of a tree, i.e., O(log n).
• Initial formation of n trees, i.e., O(n).
• Assume n < e.

C++ implementation of Kruskal’s Algorithm

#include<iostream.h> #include<process.h> #include<malloc.h> #define MAX 20 struct edge { int u; int v; int weight; edge *link; }*front = NULL; int father[MAX]; /*Holds father of each node */ edge tree[MAX]; /* Will contain the edges of spanning tree */ int n; /*Denotes total number of nodes in the graph */ int wt_tree=0; /*Weight of the spanning tree */ int count=0; /* Denotes number of edges included in the tree */ /* Functions */ void make_tree(); void insert_tree(int i,int j,int wt); void insert_pque(int i,int j,int wt); edge *del_pque(); void create_graph(); void main() { int i; create_graph(); make_tree(); cout<<“Edges to be included in spanning tree are :n”; for(i=1;i<=count;i++) { cout<<tree[i].u; cout<<tree[i].v; } cout<<“Weight of this minimum spanning tree is : “<<wt_tree; }/*End of main()*/ void create_graph() { int i,wt,max_edges,origin,destin; cout<<“Enter number of nodes : “; cin>>n; max_edges=n*(n-1)/2; for(i=1;i<=max_edges;i++) { cout<<“Enter edge “<<i<<” (0 0 to quit): “; cin>>origin; cin>>destin; if( (origin==0) && (destin==0) ) break; cout<<“nEnter weight for this edge : “; cin>>wt; if( origin > n || destin > n || origin<=0 || destin<=0) { cout<<“Invalid edge!n”; i–; } else insert_pque(origin,destin,wt); } if(i<n-1) { cout<<“nSpanning tree is not possiblen”; exit(1); } }/*End of create_graph()*/ void make_tree() { edge *tmp; int node1,node2,root_n1,root_n2; while( count < n-1) /*Loop till n-1 edges included in the tree*/ { tmp=del_pque(); node1=tmp->u; node2=tmp->v; cout<<“nn1= “<<node1; cout<<“nn2= “<<node2; while( node1 > 0) { root_n1=node1; node1=father[node1]; } while( node2 >0 ) { root_n2=node2; node2=father[node2]; } cout<<“nrootn1= “<<root_n1; cout<<“nrootn2= “<<root_n2; if(root_n1!=root_n2) { insert_tree(tmp->u,tmp->v,tmp->weight); wt_tree=wt_tree+tmp->weight; father[root_n2]=root_n1; } } }/*End of make_tree()*/ /*Inserting an edge in the tree */ void insert_tree(int i,int j,int wt) { cout<<“nThis edge inserted in the spanning treen”; count++; tree[count].u=i; tree[count].v=j; tree[count].weight=wt; }/*End of insert_tree()*/ /*Inserting edges in the priority queue */ void insert_pque(int i,int j,int wt) { edge *tmp,*q; tmp = (edge *)malloc(sizeof(edge)); tmp->u=i; tmp->v=j; tmp->weight = wt; /*Queue is empty or edge to be added has weight less than first edge*/ if( front == NULL || tmp->weight < front->weight ) { tmp->link = front; front = tmp; } else { q = front; while( q->link != NULL && q->link->weight <= tmp->weight ) q=q->link; tmp->link = q->link; q->link = tmp; if(q->link == NULL) /*Edge to be added at the end*/ tmp->link = NULL; } }/*End of insert_pque()*/ /*Deleting an edge from the priority queue*/ edge *del_pque() { edge *tmp; tmp = front; cout<<“nEdge processed is “; cout<<tmp->u; cout<<” -> “<<tmp->v; cout<<” “<<tmp->weight; front = front->link; return tmp; }/*End of del_pque()*/

Output: