Minimum Spanning Tree using Prim's Algorithm - BunksAllowed

BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

  • Home
    • demo-image
    Home Data Structures Technology Minimum Spanning Tree using Prim's Algorithm

    Minimum Spanning Tree using Prim's Algorithm

    Share This

    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.

    prim-example-step2
    prim-example-step1
    prim-example-step3
    prim-example-step4
    prim-example-step5
    prim-example
    

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    #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){
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    
            



    

    



    

    

    Happy Exploring!
    

    

    

    

Tags




    

    


    

    

    
Share This 

    

    

    


    

    
bunksAllowed

    
About BunksAllowed

    


    

    



    

    

    

    







    

    


    

    

By



on












    


    

    

    

Labels:
,



    

    



    

    

      
    
    

    


    

    


    

    

    
Subscribe to:
Post Comments (Atom)

    

    

    

    

    Comment Using!!
    

    


    No comments:
    

    

    

    

    

    

    


    Post a Comment
    

    

    

    Note: Only a member of this blog may post a comment.
    





    

    


    



    

    
         
    

    

            
          

    

    
          

    

            
          

    

    

    

    

    

    About BunksAllowed