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 u1
and u2 are in spanning tree and both have edge
connecting to v3 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!
Posts
No comments:
Post a Comment