Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » AlgorithmsRSS Feeds

Shortest Path using kruskal algorithm

Posted By: Anitha Hs     Category: C++ Programming     Views: 14460

 # include <iostream.h>
# include <graphics.h>
# include <string.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(const int,const int,const int);
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,const int);
void ShowEdge( );
};

/*************************************************************************/
//---------------------------- SetVertex( ) ---------------------------//
/*************************************************************************/

void Vertex::SetVertex(const int _x,const int _y,const int _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);

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

/*************************************************************************/
//----------------------------- SetEdge( ) ----------------------------//
/*************************************************************************/

void Edge::SetEdge(const Vertex _V1,const Vertex _V2,const int _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);
}


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 Kruskal's Algorithm *******************"<<endl;

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

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

for(int i=0;i<edges;i++)
{
for(int j=0;j<(edges-1);j++)
{
if(E[j].weight>=E[(j+1)].weight)
{
Edge Temp;

Temp=E[j];
E[j]=E[(j+1)];
E[(j+1)]=Temp;
}
}
}

int e_count=0;
int cycle_flag=0;

Edge _E[MAX_EDGES];

int mst[MAX_VERTICES][MAX_VERTICES]={0};

for(i=0;i<=vertices;i++)
{
mst[i][0]=i;

for(int j=1;j<vertices;j++)
mst[i][j]=-1;
}

for(count=0;count<edges;count++)
{
cycle_flag=0;

for(i=1;i<vertices;i++)
{
if(mst[E[count].V1.label][i]==E[count].V2.label ||
mst[E[count].V2.label][i]==E[count].V1.label)
cycle_flag=1;
}

if(!cycle_flag)
{
_E[e_count]=E[count];
_E[e_count].ShowEdge( );

e_count++;

for(i=1;i<vertices;i++)
{
if(mst[E[count].V1.label][i]==E[count].V2.label)
break;

if(mst[E[count].V1.label][i]==-1)
{
mst[E[count].V1.label][i]=E[count].V2.label;

break;
}
}

for(i=1;i<vertices;i++)
{
if(mst[E[count].V2.label][i]==E[count].V1.label)
break;

if(mst[E[count].V2.label][i]==-1)
{
mst[E[count].V2.label][i]=E[count].V1.label;

break;
}
}

for(i=0;i<vertices;i++)
{
for(int j=0;j<vertices;j++)
{
for(int k=1;k<vertices;k++)
{
if(mst[j][k]!=-1)
{
for(int l=1;l<vertices;l++)
{
if(mst[mst[j][k]][l]!=-1)
{
for(int m=0;m<vertices;m++)
{
if(mst[mst[j][k]][l]==mst[j][m])
break;

if(mst[j][m]==-1)
{
mst[j][m]=mst[mst[j][k]][l];

break;
}
}
}
}
}
}
}
}

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

getch( );

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

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

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

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

cout<<count<<" }"<<endl<<" E = { ";

for(count=0;count<(e_count-1);count++)
cout<<"("<<(_E[count].V1.label+1)<<","<<(_E[count].V2.label+1)<<"),";

cout<<"("<<(_E[count].V1.label+1)<<","<<(_E[count].V2.label+1)<<") }"<<endl;

cout<<" Total Cost = ";

int cost=0;

for(count=0;count<e_count;count++)
{
cost+=_E[count].weight;

if(count<(e_count-1))
cout<<_E[count].weight<<"+";
}

cout<<_E[count-1].weight<<" = "<<cost;

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

getch( );
return 0;
}
  
Share: 

 
 
 

Didn't find what you were looking for? Find more on Shortest Path using kruskal algorithm Or get search suggestion and latest updates.

Anitha Hs
Anitha Hs author of Shortest Path using kruskal algorithm is from Australia.
 
View All Articles

Related Articles and Code:


 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
Asif Raza from United States Comment on: Oct 08
A working code for Kruskal's Algorithm in C++. Its one page code..

in.docsity.com/.../Kruskals_Algorithm_-_C_plus_plus_Code

ANTONIO UY from United States Comment on: Oct 14
its not working at all :(

View All Comments