Search:

Submit Article

# Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics

Posted By: Easy Tutor     Category: C++ Programming     Views: 11514

## Code for Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics in C++ Programming

``` # include <iostream.h>
# include <graphics.h>
# include   <stdlib.h>
# include    <conio.h>

# define MAX_VERTICES  10
# define MAX_EDGES     15

/*************************************************************************///-------------------------------  Vertex  ------------------------------///*************************************************************************/class Vertex
{
public:
int x;
int y;
int label;

private:
char Label[5];

public:
Vertex( )   {  }
~Vertex( )  {  }

void SetVertex(constint,constint,constint);
void ShowVertex( );
};

/*************************************************************************///-------------------------------  Edge  --------------------------------///*************************************************************************/class Edge
{
public:
int weight;

Vertex V1;
Vertex V2;

private:
char Weight[5];

public:
Edge( )   { }
~Edge( )  { }

void SetEdge(const Vertex,const Vertex,constint);
void ShowEdge( );
};

/*************************************************************************//*************************************************************************///------------------------  Function Definitions  -----------------------///*************************************************************************//*************************************************************************//*************************************************************************///----------------------------  SetVertex( )  ---------------------------///*************************************************************************/void Vertex::SetVertex(constint _x,constint _y,constint _label)
{
x=_x;
y=_y;
label=_label;

itoa((label+1),Label,10);
}

/*************************************************************************///----------------------------  ShowVertex( )  --------------------------///*************************************************************************/void Vertex::ShowVertex( )
{
setcolor(1);
setfillstyle(1,1);
pieslice(x,y,0,360,10);

setcolor(9);
circle(x,y,10);

setcolor(15);
settextstyle(2,0,4);

if(label<9)
outtextxy((x-2),(y-6),Label);

elseif(label>=9)
outtextxy((x-5),(y-6),Label);
}

/*************************************************************************///-----------------------------  SetEdge( )  ----------------------------///*************************************************************************/void Edge::SetEdge(const Vertex _V1,const Vertex _V2,constint _weight)
{
V1=_V1;
V2=_V2;

weight=_weight;

itoa(weight,Weight,10);
}

/*************************************************************************///----------------------------  ShowEdge( )  ----------------------------///*************************************************************************/void Edge::ShowEdge( )
{
setlinestyle(0,0,3);

setcolor(11);
line(V1.x,V1.y,V2.x,V2.y);

setlinestyle(0,0,0);

V1.ShowVertex( );
V2.ShowVertex( );

int x=(((V1.x+V2.x)/2)-6);
int y=(((V1.y+V2.y)/2)-8);

setcolor(12);
settextstyle(2,0,7);
outtextxy(x,y,Weight);
outtextxy((x+1),y,Weight);
outtextxy((x+1),(y+1),Weight);
}

/*************************************************************************//*************************************************************************///------------------------------  main( )  ------------------------------///*************************************************************************//*************************************************************************/int main( )
{
textmode(C4350);

int driver=VGA;
int mode=VGAHI;
int error_code;

initgraph(&driver,&mode,"..\\Bgi");

error_code=graphresult( );

if(error_code!=grOk)
{
restorecrtmode( );
textmode(BW80);
clrscr( );

cout<<" \n Fatal Error  : Graphic Driver not initialized"<<endl;
cout<<" Error Reason : "<<grapherrormsg(error_code)<<endl;
cout<<" \n Press any key to exit...";

getch( );
exit(1);
}

/***************************************************************            Sample Input            ************         Vertices  ,  Edges            6  ,  10           Vertex_1 , Vertex_2            320 , 100            170 , 200            320 , 250            470 , 200            220 , 400            420 , 400          Vertxe_1 ---->  Vertex_2 ,  Weight            1  ---->  2        ,  6            1  ---->  4        ,  5            1  ---->  3        ,  1            2  ---->  3        ,  5            2  ---->  5        ,  3            3  ---->  5        ,  6            3  ---->  6        ,  4            3  ---->  4        ,  5            4  ---->  5        ,  2            5  ---->  5        ,  6         Answer : 15    ***************************************************************/int vertices=0;
int edges=0;

cout<<"*******************  Input  ********************"<<endl;
cout<<"Enter the Total Number of Vertices (1-10) = ";
cin>>vertices;

vertices=((vertices<1)?1:vertices);
vertices=((vertices>10)?10:vertices);

cout<<"Enter the Total Number of Edges (1-15) = ";
cin>>edges;

edges=((edges<0)?0:edges);
edges=((edges>15)?15:edges);

Vertex  V[MAX_VERTICES];
Edge    E[MAX_EDGES];

cleardevice( );

setcolor(15);
rectangle(45,85,595,415);

int x;
int y;

for(int count=0;count<vertices;count++)
{
gotoxy(1,1);
cout<<"*******  XY-Coordinates of Vertex-"<<(count+1)<<"  *******";

gotoxy(1,2);
cout<<"Enter value of x-coordinate (060-580) = ";
cin>>x;

x=((x<60)?60:x);
x=((x>580)?580:x);

gotoxy(1,3);
cout<<"Enter value of y-coordinate (100-400) = ";
cin>>y;

y=((y<100)?100:y);
y=((y>400)?400:y);

V[count].SetVertex(x,y,count);
V[count].ShowVertex( );

gotoxy(1,1);
cout<<"                                                       ";
gotoxy(1,2);
cout<<"                                                       ";
gotoxy(1,3);
cout<<"                                                       ";
}

gotoxy(1,28);
cout<<" V = { ";

for(count=1;count<vertices;count++)
cout<<count<<",";

cout<<count<<" } ";

gotoxy(1,30);
cout<<" E = { ";

x=wherex( );

int v1;
int v2;
int weight;

for(count=0;count<edges;count++)
{
gotoxy(1,1);
cout<<"******  Vertex Numbers for Edge-"<<(count+1)<<"  ******";

gotoxy(1,2);
cout<<"Enter the Vertice-1 (1-"<<vertices<<")  = ";
cin>>v1;

v1=((v1<1)?1:v1);
v1=((v1>vertices)?vertices:v1);

gotoxy(1,3);
cout<<"Enter the Vertice-2 (1-"<<vertices<<")  = ";
cin>>v2;

v2=((v2<1)?1:v2);
v2=((v2>vertices)?vertices:v2);

gotoxy(1,4);
cout<<"Enter the Edge Weight = ";
cin>>weight;

weight=((weight<=0)?0:weight);

E[count].SetEdge(V[(v1-1)],V[(v2-1)],weight);
E[count].ShowEdge( );

gotoxy(x,30);
cout<<"("<<v1<<","<<v2<<")";

if(count<(edges-1))
cout<<",";

x=wherex( );

gotoxy(1,1);
cout<<"                                                     ";
gotoxy(1,2);
cout<<"                                                     ";
gotoxy(1,3);
cout<<"                                                      ";
gotoxy(1,4);
cout<<"                                                      ";
}

gotoxy(x,30);
cout<<" } ";

getch( );
cleardevice( );

gotoxy(5,3);
cout<<" ********************  Applying PRIMS Algorithm  ********************";

setcolor(15);
rectangle(45,85,595,415);

for(count=0;count<vertices;count++)
V[count].ShowVertex( );

int U[MAX_VERTICES];
int vertex_1[MAX_VERTICES];
int vertex_2[MAX_VERTICES];
int edge_weights[MAX_VERTICES];
int resultant_weights[MAX_VERTICES];

int flag_1=0;
int flag_2=0;
int u_count=1;
int temp_vertex=0;
int temp_vertex_1=0;
int temp_vertex_2=0;
int lowest_edge_weight=0;

U[0]=0;

do
{
count=0;

for(int i=0;i<vertices;i++)
{
vertex_1[i]=0;
vertex_2[i]=0;
edge_weights[i]=0;
}

for(i=0;i<u_count;i++)
{
flag_1=0;

for(int j=0;j<edges;j++)
{
if(E[j].V1.label==U[i] || E[j].V2.label==U[i])
{
flag_2=0;

if(E[j].V1.label!=U[i])
{
temp_vertex=E[j].V1.label;
temp_vertex_1=E[j].V2.label;
}

else
{
temp_vertex=E[j].V2.label;
temp_vertex_1=E[j].V1.label;
}

for(int k=0;k<u_count;k++)
{
if(temp_vertex==U[k])
{
flag_2=-1;

break;
}
}

if(flag_2!=-1)
{
if(flag_1==0 || lowest_edge_weight>E[j].weight)
{
lowest_edge_weight=E[j].weight;
temp_vertex_2=temp_vertex;
flag_1=1;
}
}
}
}

if(flag_1==1)
{
vertex_2[count]=temp_vertex_2;
vertex_1[count]=temp_vertex_1;
edge_weights[count]=lowest_edge_weight;

count++;
}
}

flag_1=0;

for(i=0;i<count;i++)
{
if(flag_1==0 || lowest_edge_weight>edge_weights[i])
{
lowest_edge_weight=edge_weights[i];
temp_vertex_1=vertex_1[i];
temp_vertex_2=vertex_2[i];
flag_1=1;
}
}

if(flag_1==1)
{
U[u_count]=temp_vertex_2;
u_count++;

for(i=0;i<edges;i++)
{
if((E[i].V1.label==temp_vertex_1 && E[i].V2.label==temp_vertex_2) ||
(E[i].V1.label==temp_vertex_2 && E[i].V2.label==temp_vertex_1) )
{
E[i].ShowEdge( );
resultant_weights[(u_count-2)]=E[i].weight;

gotoxy(48,28);
cout<<"Press any Key to Continue...";

getch( );

gotoxy(48,28);
cout<<"                            ";

break;
}
}
}

elsebreak;
}
while(1);

gotoxy(1,1);
cout<<"                                                                         "<<endl;
cout<<"                                                                         "<<endl;
cout<<"                                                                         "<<endl;
cout<<"                                                                         "<<endl;
cout<<"                                                                         "<<endl;

gotoxy(1,1);
cout<<"*******************  Result  ********************"<<endl;
cout<<" U = { ";

for(count=0;count<(u_count-1);count++)
cout<<(U[count]+1)<<",";

cout<<(U[count]+1)<<" }"<<endl<<endl;
cout<<" Total Cost = ";

int cost=0;

for(count=0;count<(u_count-1);count++)
{
cost+=resultant_weights[count];

if(count<(u_count-2))
cout<<resultant_weights[count]<<"+";
}

cout<<resultant_weights[(count-1)]<<" =  "<<cost;

gotoxy(54,28);
cout<<"Press any Key to Exit.";

getch( );
closegraph( );
return 0;
}

```
Share:

 Easy Tutor author of Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics is from United States. Easy Tutor says Hello Friends,I am Free Lance Tutor, who helped student in completing their homework. I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] comI have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada. I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.Thanks,Happy Programming :) View All Articles

 Please enter your CommentComment should be atleast 30 Characters.Please put code inside [Code] your code [/Code]. No Comment Found, Be the First to post comment!