Sample C Program To Implement Minimum Spanning Tree Using Functions, Pointers & Structures.

ALGORITHM:

STEP 1: Start the program.
STEP 2: Assign MAX a constant value of 20.
STEP 3: Declare a structure edge with structure variable *front.
STEP 4: Define the functions and variables required in the program globally.
STEP 5: Call the function create_graph() inside the main function.

STEP 6: Call the function make_tree().
STEP 7: Set a for loop using i.
for(i = 1; i <= count; i++)
STEP 8: Print the values of tree[i].u and tree[i].v
STEP 9: Stop the program.


FUNCTION OF CREATE_GRAPH ( )

STEP 1: Declare the local variables.
STEP 2: Read the number of nodes n.
STEP 3: Calculate the value of max_edge as
max_edge = n * (n - 1) / 2.
STEP 4: Set a for loop using i.
for(i = 0; i <= max_edge; i++)
STEP 5: Read the values of origin and destiny.

STEP 6: Check whether origin and destiny are equal to 0.
STEP 7: If so exit the loop using break statement
STEP 8: Read the weight of the current edge wt.
STEP 9: Check the following condition.
if(origin > n || destin > n || origin <= 0 || destin <= 0)
STEP 10: If any of the condition is true, print “invalid edge!” and decrement the value of i by 1.

STEP 11: Else call the function insert_pque(origin, destin, wt).
STEP 12: Check whether i is less than n - 1, if so then exit with an error message.


FUNCTION OF MAKE_TREE ( )

STEP 1: Declare the local variables.
STEP 2: Initialize the variable tmp, node1, node2.
STEP 3: Assign the values for node1, node2.
STEP 4: Calculate and print the values of root_n1 and root_n2.
STEP 5: If the two roots are not equal, call the function insert_tree.

STEP 6: Assign the value of root_n1 to father [root_n2].


FUNCTION OF INSERT_TREE (int i, int j, int wt )

STEP 1: Declare the local variables.
STEP 2: Increment the value of count.
STEP 3: Assign values to tree[count].u, tree[count].v, tree[count].weight.


FUNCTION OF INSERT_PQUE (int i, int j, int wt )

STEP 1: Declare the local variables
STEP 2: Allocate the memory space of size, struct edge for tmp.
STEP 3: Assign values to tmp -> u, tmp -> v, tmp -> weight.
STEP 4: Check for the following condition.
if(front == NULL || tmp -> weight < front -> weight)
STEP 5: If any of the conditions are true assign the value of front to tmp -> link and assign tmp to
Front.

STEP 6: Else set a while loop and declare following.
q = q -> link;
tmp -> link = q -> link;
q -> link = tmp;
if(q ->> link == NULL)
tmp -> link = NULL;

FUNCTION OF STRUCT EDGE *DEL_PQUE( )

STEP 1: Declare the local variable.
STEP 2: Assign the value of front to temp.
STEP 3: Print the values of processed edge and return the value of tmp.



SAMPLE PROGRAM:

#include<stdio.h>
#include<conio.h>
#define MAX 20

struct edge
{
int u;
int v;
int weight;
struct edge *link;
}

*front = NULL;
int father[MAX];
struct edge tree[MAX];
int n;
int wt_tree = 0;
int count = 0;

void make_tree();
void insert_tree(int i, int j, int wt);
void insert_pque(int i, int j, int wt);
struct edge *del_pque();

void main()
{

int i;

create_graph();
make_tree();
clrscr();

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

for(i = 1; i <= count; i++)
{
printf(" %d -> ", tree[i].u);
printf(" %d \n ", tree[i].v);
}

printf(" Weight of this minimum spanning tree is: %d \n ", wt_tree);
getch();

}

create_graph()
{

int i, wt, max_edge, origin, destin;
printf(" Enter no. of nodes: ");
scanf(" %d ", &n);
max_edge = n * (n - 1) / 2;

for(i = 0; i <= max_edge; i++)
{
printf(" Enter edge %d (0 0 to quit): ", i);
scanf(" %d %d ", &origin, &destin);

if((origin == 0) && (destin == 0))
break;
printf(" Enter weight for this edge: ");
scanf(" %d ", &wt) ;

if(origin > n || destin > n || origin <= 0|| destin <= 0)
{
printf(" Invalid edge! ");
i- -;
}
else insert_pque(origin, destin, wt);
}

if(i < n - 1)
{
printf(" Spanning tree is not possible.");
exit(1);
}

return 0;

}

void make_tree()
{

struct edge *tmp;
int node1, node2, root_n1, root_n2;

while(count < n - 1)
{
tmp = del_pque();
node1 = tmp -> u;
node2 = tmp -> v;
printf(" n1 =%d ", node1);
printf(" n2 = %d ", node2);
while(node1 > 0)
{
root_n1 = node1;
node1 = father[node1];
}
while(node2 > 0)
{
root_n2 = node2;
node2 = father[node2];
}
printf(" Rootn1 = %d \n ", root_n1);
printf(" Rootn2 = %d \n ", 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;
}
}

}


void insert_tree(int i, int j, int wt)
{

printf(" This Edge inserted in the spanning tree\n ");
count++;
tree[count].u = i;
tree[count].v = j;
tree[count].weight = wt;

}

void insert_pque(int i, int j, int wt)
{

struct edge *tmp, *q;
tmp = (struct edge *)malloc ( sizeof( struct edge ) ) ;
tmp -> u = i;
tmp -> v = j;
tmp -> weight = wt;

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)
tmp -> link = NULL;
}

}


struct edge *del_pque()
{

struct edge *tmp;
tmp = front;
printf(" Edge Processed is %d -> %d %d \n ",tmp -> u, tmp -> v, tmp -> weight);
front = front -> link;
return tmp;

}


NOTE:

If you liked the post/article or if you think this post/article helped you in any way, then please show your appreciation by filling up at least one form from the options given below: