Minimum Spanning Tree using Prim's Algorithm

A spanning tree of a connected graph is just a sub-graph that contains all the vertices and has the edges which connects all the vertices. So the number of edges will be 1 less than the number of nodes. Let's take a connected graph which is shown in the Fig 1.Here all these trees are spanning tree and the number of edges is one less than the number of nodes. If graph is not connected. i.e., a graph with n vertices has edges less than n-1 then no spanning tree is possible.

---

Minimum Spanning Tree

---

Given a connected weighted graph G, it is often desired to create a spanning tree T for G such that the sum of weights of the tree edges in T is as small as possible. Such a tree is called a minimum spanning tree. There are number of techniques for creating a minimum spanning tree for a weighted graph but the most famous methods are Prim's and Kruskal algorithm.

---

Prim's Minimum Spanning Tree

---

In this method, we start with any node and add the other node in spanning tree on the basis of weight of edge containing to that node. Suppose we start with the node u then we have to see all the connecting edges and which edge has minimum weight. Then we will add that edge and node to the spanning tree. Suppose if two nodes u₁ and u₂ are in spanning tree and both have edge connecting to v₃ then edge which has minimum weight will be added in spanning tree. Let's see the method.

Prim's Algorithm

MST-PRIM(G,w,r)
for each u ∈ V[G] do
     key[u]<-&infinity;
     π[u]<-NIL
key[r]<-0
Q<-V[G]
while Q!=φ do
     u<-EXTRACT-MIN(Q)
     for each v ∈ Adj[u] do
         if v ∈ Q and weight(u,v)<key[v] then
               π[u]<-u
               key[v]<-weight(u,v)      				

Consider an example to clarify the method.

#include<stdio.h> #include<stdlib.h> #include<limits.h> typedef struct heap_node{ int vertex; int weight; }heap_node; typedef struct heap{ heap_node **heap; int *heapPos; int size; int maxSize; }heap; heap_node *create_min_heap_node(int w, int v){ heap_node *node=(heap_node*)malloc(sizeof(heap_node)); node->vertex = v; node->weight = w; return node; }; heap *create_min_heap(int maxSize){ heap *heapNode = (heap *)malloc(sizeof(heap)); heapNode->heap = (heap_node**)malloc(maxSize * sizeof(heap_node*)); heapNode->heapPos = (int *)malloc(maxSize * sizeof(int)); heapNode->maxSize = maxSize; heapNode->size = 0; return heapNode; } void swap(heap_node **a, heap_node **b){ heap_node* temp = *a; *a = *b; *b = temp; } int right_child(int i){ return (2 * i) + 1; } int left_child(int i){ return (2 * i); } void heapify(heap *min_heap,int position){ int minIndex = position; int left = left_child(position); int right = right_child(position); if(left<min_heap->size && min_heap->heap[minIndex]->weight > min_heap->heap[left]->weight) minIndex = left; if(right<min_heap->size && min_heap->heap[minIndex]->weight > min_heap->heap[right]->weight) minIndex = right; if(minIndex != position){ heap_node* minNode = min_heap->heap[minIndex]; heap_node* node = min_heap->heap[position]; min_heap->heapPos[minNode->vertex] = position; min_heap->heapPos[node->vertex] = minIndex; swap(&min_heap->heap[minIndex], &min_heap->heap[position]); heapify(min_heap, minIndex); } } heap_node *extract_min_heap(heap *min_heap){ if(min_heap->size<0){ return NULL; } heap_node *extractNode = min_heap->heap[0]; heap_node *last = min_heap->heap[min_heap->size-1]; min_heap->heapPos[extractNode->vertex] = min_heap->size-1; min_heap->heapPos[last->vertex] = 0; min_heap->heap[0] = last; min_heap->size--; heapify(min_heap, 0); return extractNode; } void decreaseKey(heap *min_heap, int ver, int wei){ int index = min_heap->heapPos[ver]; min_heap->heap[index]->weight = wei; while(index && min_heap->heap[index]->weight < min_heap->heap[(index-1)/2]->weight){ min_heap->heapPos[min_heap->heap[index]->vertex] = (index - 1) / 2; min_heap->heapPos[min_heap->heap[(index-1)/2]->vertex] = index; swap(&min_heap->heap[index], &min_heap->heap[(index - 1) / 2]); index=(index - 1) / 2; } } int belongsTo(heap *min_heap, int vertex){ if(min_heap->heapPos[vertex] < min_heap->size){ return 1; } return 0; } int prims(heap *min_heap, int **cost_matrix, int *weights, int no_of_vertex){ int weight = 0, startingVertex = 0, i = 0; weights[0] = 0; min_heap->heapPos[0] = 0; min_heap->heap[0] = create_min_heap_node(0, 0); while(min_heap->size >0){ heap_node *temp = extract_min_heap(min_heap); startingVertex = temp->vertex; for(i = 0; i < no_of_vertex; i++){ if(cost_matrix[startingVertex][i] != 0 && belongsTo(min_heap, i) && cost_matrix[startingVertex][i] < weights[i]){ weights[i] = cost_matrix[startingVertex][i]; decreaseKey(min_heap, i, weights[i]); } } } for(i=1;i<no_of_vertex;i++){ weight+=weights[i]; } return weight; } int main(){ int no_of_vertex = 0, **cost_matrix, *weights, i = 0, j = 0; scanf("%d", &no_of_vertex); heap *min_heap = create_min_heap(no_of_vertex); weights = (int *)malloc(no_of_vertex * sizeof(int)); for(i = 0; i < no_of_vertex; i++) weights[i] = INT_MAX; for(i=1;i<no_of_vertex;i++){ min_heap->heap[i] = create_min_heap_node(INT_MAX, i); min_heap->heapPos[i] = i; } min_heap->size = no_of_vertex; cost_matrix = (int **)malloc(no_of_vertex * sizeof(int *)); for(i = 0; i < no_of_vertex; i++) cost_matrix[i] = (int *)malloc(no_of_vertex * sizeof(int)); for(i=0;i<no_of_vertex;i++) for(j=0;j<no_of_vertex;j++) scanf("%d", &cost_matrix[i][j]); printf("%d ", prims(min_heap, cost_matrix, weights, no_of_vertex)); return 0; }

Happy Exploring!