# Write a program in C language that will accept a Graph as input and will generate its Minimum Cost Spanning Tree – IGNOU MCA Assignment 2015 – 16

By | September 25, 2015

MASTER OF COMPUTER APPLICATIONS

Course Code : MCSL-025
Course Title : Lab Course
Assignment Number : MCA(II)/L-025/Assignment/15-16
Maximum Marks : 50
Weightage : 25%

Write a program in C language that will accept a Graph as input and will generate its Minimum Cost Spanning Tree.

#include <stdio.h>

#define MAXVERTICES 10
#define MAXEDGES 20
typedef enum {FALSE, TRUE} bool;

int getNVert(int edges[], int nedges)
{
// returns no of vertices = maxvertex + 1;

int nvert = -1;
int j;

for( j=0; j<nedges; ++j )
{
if( edges[j] > nvert )
nvert = edges[j];

if( edges[j] > nvert )
nvert = edges[j];
}
return ++nvert; // no of vertices = maxvertex + 1;
}

bool isPresent(int edges[], int nedges, int v)
{
// checks whether v has been included in the spanning tree.
// thus we see whether there is an edge incident on v
// which has a negative cost. negative cost signifies that
// the edge has been included in the spanning tree.

int j;
for(j=0; j<nedges; ++j)
if(edges[j] < 0 && (edges[j] == v || edges[j] == v))
return TRUE;

return FALSE;
}

void spanning(int edges[], int nedges) {

// finds a spanning tree of the graph having edges.
// uses kruskal’s method.
// assumes all costs to be positive.

int i, j;
int tv1, tv2, tcost;
int nspanedges = 0;
int nvert = getNVert(edges, nedges);

// sort edges on cost.
for(i=0; i<nedges-1; ++i)
for(j=i; j<nedges; ++j)
if(edges[i] > edges[j])
{
tv1=edges[i]; tv2=edges[i]; tcost=edges[i];
edges[i]=edges[j]; edges[i]=edges[j];
edges[i]=edges[j]; edges[j]=tv1;
edges[j]=tv2; edges[j]=tcost;
}
for(j=0; j<nedges-1; ++j) {
// consider edge j connecting vertices v1 and v2.
int v1 = edges[j];
int v2 = edges[j];

// check whether it forms a cycle in the up until now formed
// spanning tree. checking can be done easily by checking
// whether both v1 and v2 are in the current spanning tree!
if(isPresent(edges, nedges, v1) && isPresent(edges,nedges, v2)) // cycle.
printf(“rejecting: %d %d %d…\n”,edges[j],edges[j],edges[j]);
else {
edges[j] = -edges[j];
printf(“%d %d %d.\n”, edges[j], edges[j], -edges[j]);
if(++nspanedges == nvert-1)
return;
}
}
printf(“No spanning tree exists for the graph.\n”);
}

void main()
{
int edges[] = {
{0,1,16},
{0,4,19},
{0,5,21},
{1,2,5},
{1,3,6},
{1,5,11},
{2,3,10},
{3,4,18},
{3,5,14},
{4,5,33}
};
int nedges = sizeof(edges)/3/sizeof(int);
clrscr();
printf(“The spanning tree for the graph is :\n”);
spanning(edges, nedges);
getch();
}

Program Code:

 Source code   ```#include <stdio.h>
#define MAXVERTICES 10
#define MAXEDGES 20
typedef enum {FALSE, TRUE} bool;
int getNVert(int edges[], int nedges)
{
// returns no of vertices = maxvertex + 1;
int nvert = -1;
int j;
for( j=0; j<nedges; ++j )
{
if( edges[j] > nvert )
nvert = edges[j];
if( edges[j] > nvert )
nvert = edges[j];
}
return ++nvert; // no of vertices = maxvertex + 1;
}
bool isPresent(int edges[], int nedges, int v)
{
// checks whether v has been included in the spanning tree.
// thus we see whether there is an edge incident on v
// which has a negative cost. negative cost signifies that
// the edge has been included in the spanning tree.
int j;
for(j=0; j<nedges; ++j)
if(edges[j] < 0 && (edges[j] == v || edges[j] == v))
return TRUE;
return FALSE;
}
void spanning(int edges[], int nedges) {
// finds a spanning tree of the graph having edges.
// uses kruskal's method.
// assumes all costs to be positive.
int i, j;
int tv1, tv2, tcost;
int nspanedges = 0;
int nvert = getNVert(edges, nedges);
// sort edges on cost.
for(i=0; i<nedges-1; ++i)
for(j=i; j<nedges; ++j)
if(edges[i] > edges[j])
{
tv1=edges[i]; tv2=edges[i]; tcost=edges[i];
edges[i]=edges[j]; edges[i]=edges[j];
edges[i]=edges[j]; edges[j]=tv1;
edges[j]=tv2; edges[j]=tcost;
}
for(j=0; j<nedges-1; ++j) {
// consider edge j connecting vertices v1 and v2.
int v1 = edges[j];
int v2 = edges[j];
// check whether it forms a cycle in the up until now formed
// spanning tree. checking can be done easily by checking
// whether both v1 and v2 are in the current spanning tree!
if(isPresent(edges, nedges, v1) && isPresent(edges,nedges, v2)) // cycle.
printf("rejecting: %d %d %d...\n",edges[j],edges[j],edges[j]);
else {
edges[j] = -edges[j];
printf("%d %d %d.\n", edges[j], edges[j], -edges[j]);
if(++nspanedges == nvert-1)
return;
}
}
printf("No spanning tree exists for the graph.\n");
}
void main()
{
int edges[] = {
{0,1,16},
{0,4,19},
{0,5,21},
{1,2,5},
{1,3,6},
{1,5,11},
{2,3,10},
{3,4,18},
{3,5,14},
{4,5,33}
};
int nedges = sizeof(edges)/3/sizeof(int);
clrscr();
printf("The spanning tree for the graph is :\n");
spanning(edges, nedges);
getch();
}```

Screen Shots: 