MINIMUM SPANNING TREE

MINIMUM SPANNING TREE

AIM:

To find the minimum cost spanning tree in a graph using Prims algorithm.

ALGORITHM:

Step 1 : Start the process.

Step 2: Create two classes as POINT and ARC.

Step 3: Define a Graph class which represents the collection of Point and Arc objects.

Step 4: Write a method to find a minimum cost spanning tree in a graph.

Step 5: Enter the Number of nodes, source node, destination node, weight for the corresponding edge.

Step6: Repeat step5 until all vertices, edges and weight are defined.

Step 7: The edge does not form a cycle in the graph, for Minimum Spanning Tree.

Step 8: Thus set of edges is connected and form a Minimum Spanning Tree.

Step 9: Display the adjacency matrix for the graph and the minimum total path of all the edges. 

Step 10: Stop the process.

PROGRAM:

#include<iostream.h>

#include<conio.h>

#define MAX 50

#define TRUE 1

#define FALSE 0

#define MAXINT 250

class node

{

public:

int no;

node()

{}

node (int a)

{

no = a;

}

};

class arc

{

public:

int adj;

int weight;

arc()

{}

arc(int a)

{

adj = a;

}

};

class graph

{

public:

node nodes[MAX];

arc arcs[MAX][MAX];

graph(int n)

{

for(int i=1;i<=n;i++)

{

nodes[i].no = 0;

for(int j=1;j<=n;j++)

arcs[i][j].adj = FALSE;

}

}

void join(node n1, node n2, int w)

{

arcs[n1.no][n2.no].adj = w;

arcs[n2.no][n1.no].adj = w;

}

void displayadj(int n)

{

cout<<"\n The adjacency matrix....";

cout<<endl;

for(int i = 1; i<=n; i++)

{

for(int j = 1; j<=n;j++)

cout<<"\t"<<arcs[i][j].adj;

cout<<endl;

}

cout<<endl;

}

void shortpath(int n)

{

int lcost[20];

int clost[20],i,j,k,min;

for(i = 2; i<=n;i++)

{

lcost[i]=arcs[1][i].adj;

clost[i]=1;

}

cout<<"\n Minimum cost spanning tree edges are:\n";

for(i=2;i<=n;++i)

{

min=lcost[2];

k=2;

for(j=3;j<=n;++j)

if(lcost[j]<min)

{

min = lcost[j];

k=j;

}

cout<<"\n"<<k<<"<->"<<clost[k];

lcost[k]=MAXINT;

for(j=2;j<=n;++j)

if((arcs[k][j].adj<lcost[j])&&(lcost[j]<MAXINT))

{

lcost[j]=arcs[k][j].adj;

clost[j]=k;

}

}

}

};

int main()

{

int n;

clrscr();

cout<<"\n Enter total number of nodes...";

cin>>n;

graph g(n);

cout<<"\n Assigning number for each node...";

for(int i = 1;i<=n;i++)

g.nodes[i].no=i;

char ch ='y';

int w;

do

{

node a,b;

cout<<"\n Create path b/w the nodes";

cout<<"\n Enter the source node...";

cin>>a.no;

cout<<"\n Enter the destination node...";

cin >>b.no;

cout<<"\n Enter the weight:";

cin>>w;

g.join(a,b,w);

cout<<"\n Want to continue...[y]es or [n]:";

cin>>ch;

}while(ch=='y');

g.displayadj(n);

g.shortpath(n);

cin>>n;

getch();

return 0;

}

OUTPUT:

 Enter total number of nodes...4

 Assigning number for each node...

 Create path b/w the nodes

 Enter the source node...1

 Enter the destination node...2

 Enter the weight:1

 Want to continue...[y]es or [n]:y

 Create path b/w the nodes

 Enter the source node...1

 Enter the destination node...4

 Enter the weight:2

 Want to continue...[y]es or [n]:y

 Create path b/w the nodes

 Enter the source node...1

 Enter the destination node...3

 Enter the weight:2

 Want to continue...[y]es or [n]:y

 Create path b/w the nodes

 Enter the source node...2

 Enter the destination node...4

 Enter the weight:4

 Want to continue...[y]es or [n]:y

 Create path b/w the nodes

 Enter the source node...2

 Enter the destination node...3

 Enter the weight:5

 Want to continue...[y]es or [n]:y

 Create path b/w the nodes

Enter the source node...3

 Enter the destination node...4

 Enter the weight:3

 Want to continue...[y]es or [n]:n

 The adjacency matrix....

        0       1       2       2

        1       0       5       4

        2       5       0       3

        2       4       3       0

 Minimum cost spanning tree edges are:

2<->1

3<->1

4<->1

RESULT:

Thus the program to find the minimum cost spanning tree in a graph using Prims algorithm was executed.