C Program for Creating Minimum Spanning Tree using Prim’s Algorithm

By | 11.07.2017

Minimum Spanning Tree using Prim’s Algorithm


Write a C Program for Creating Minimum Spanning Tree using Prim’s Algorithm. Here’s simple Program for minimum cost spanning tree using prim’s algorithm example in C Programming Language.


Prim’s Algorithm


 

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.

It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

This algorithm is directly based on the MST( minimum spanning tree) property.

How does Prim’s Algorithm Work?   The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.

The steps for implementing Prim’s algorithm are as follows:

  1. Initialize the minimum spanning tree with a vertex chosen at random.
  2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
  3. Keep repeating step 2 until we get a minimum spanning tree

Also Read : : C Program to find Shortest Path Matrix by Modified Warshall’s Algorithm

Below is the source code for C Program for Creating Minimum Spanning Tree using Prim’s Algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program for Creating Minimum Spanning Tree using Prim's Algorithm */

#include<stdio.h>
#include<stdlib.h>

#define MAX 10
#define TEMP 0
#define PERM 1
#define infinity 9999
#define NIL -1

struct edge
{
        int u;
        int v;
};

int n;
int adj[MAX][MAX];

int predecessor[MAX];
int status[MAX];
int length[MAX];

void create_graph();
void maketree(int r, struct edge tree[MAX]);
int min_temp();

int main()
{
        int wt_tree = 0;
        int i, root;
        struct edge tree[MAX];

        create_graph();

        printf("\nEnter root vertex : ");
        scanf("%d",&root);

        maketree(root, tree);

        printf("\nEdges to be included in spanning tree are : \n");

        for(i=1; i<=n-1; i++)
        {
                printf("%d-> ",tree[i].u);
                printf("%d\n",tree[i].v);
                wt_tree += adj[tree[i].u][tree[i].v];
        }
        printf("\nWeight of spanning tree is : %d\n", wt_tree);

        return 0;

}/*End of main()*/

void maketree(int r, struct edge tree[MAX])
{
        int current,i;
        int count = 0;/*number of vertices in the tree*/

        /*Initialize all vertices*/
        for(i=0; i<n; i++)
        {
                predecessor[i] = NIL;
                length[i] = infinity;
                status[i] = TEMP;
        }

        /*Make length of root vertex 0*/
        length[r] = 0;

        while(1)
        {
                /*Search for temporary vertex with minimum length
                and  make it current vertex*/
                current = min_temp();

                if(current == NIL)
                {
                        if(count == n-1) /*No temporary vertex left*/
                                return;
                        else /*Temporary vertices left with length infinity*/
                        {
                                printf("\nGraph is not connected, No spanning tree possible\n");
                                exit(1);
                        }
                }

                /*Make the current vertex permanent*/
        status[current] = PERM;

                /*Insert the edge ( predecessor[current], current) into the tree,
                except when the current vertex is root*/
                if(current != r)
                {
           count++;
                   tree[count].u = predecessor[current];
                   tree[count].v = current;
                }

                for(i=0; i<n; i++)
                        if(adj[current][i] > 0 && status[i] == TEMP)
                                if(adj[current][i] < length[i])
                                {
                                        predecessor[i] = current;
                                        length[i] = adj[current][i];
                                }
        }

}/*End of make_tree( )*/

/*Returns the temporary vertex with minimum value of length
  Returns NIL if no temporary vertex left or
  all temporary vertices left have pathLength infinity*/
int min_temp()
{
        int i;
        int min = infinity;
        int k = -1;

        for(i=0; i<n; i++)
        {
                if(status[i] == TEMP && length[i] < min)
                {
                        min = length[i];
                        k = i;
                }
        }

        return k;
}/*End of min_temp()*/

void create_graph()
{
        int i,max_edges,origin,destin,wt;

        printf("\nEnter number of vertices : ");
        scanf("%d",&n);
        max_edges = n*(n-1)/2;

        for(i=1; i<=max_edges; i++)
        {
                printf("\nEnter edge %d(-1 -1 to quit) : ",i);
                scanf("%d %d",&origin,&destin);
                if((origin == -1) && (destin == -1))
                        break;
                printf("\nEnter weight for this edge : ");
                scanf("%d",&wt);
                if( origin >= n || destin >= n || origin < 0 || destin < 0)
                {
                        printf("\nInvalid edge!\n");
                        i--;
                }
                else
                {
                        adj[origin][destin] = wt;
                        adj[destin][origin] = wt;
                }
        }
}

OUTPUT : :


/* C Program for Creating Minimum Spanning Tree using Prim's Algorithm */

Enter number of vertices : 5

Enter edge 1(-1 -1 to quit) : 0 1

Enter weight for this edge : 2

Enter edge 2(-1 -1 to quit) : 0 2

Enter weight for this edge : 4

Enter edge 3(-1 -1 to quit) : 0 3

Enter weight for this edge : 1

Enter edge 4(-1 -1 to quit) : 0 4

Enter weight for this edge : 2

Enter edge 5(-1 -1 to quit) : 1 3

Enter weight for this edge : 3

Enter edge 6(-1 -1 to quit) : 2 3

Enter weight for this edge : 1

Enter edge 7(-1 -1 to quit) : 1 4

Enter weight for this edge : 2

Enter edge 8(-1 -1 to quit) : 3 4

Enter weight for this edge : 2

Enter edge 9(-1 -1 to quit) : -1 -1

Enter root vertex : 0

Edges to be included in spanning tree are :
0-> 3
3-> 2
0-> 1
0-> 4

Weight of spanning tree is : 6

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post…


Recommended Posts : :

4 1 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments