### Algorithm Design & Analysis

Product of 2 matrices - Divide and Conquer Kurskal\'s algo to solve Minimum Cost Spanning Tree

### Divide and Conquer Strategy

Towers of Hanoi Problem using Recursive Algorithm Prim\'s algo solve Minimum Spanning Tree - Graphic

### Cubic Time Algorithms

Bubble Sort Algorithm n_th term of fibonacci series - Toplogical Order

### Logrithmic Time Algorithms

Compute, display factorial using recursive algo Product of 2 matrices - Strassen\'s Algorithm Kurskal\'s algo - min cost spanning tree - graphics

### Dynamic Programming Technique

n_th term of fibonacci series - Divide and Conquer Prim\'s algo - min Spanning Tree - Mouse support

### Exponential Time Algorithms

Multiply two matrices Prim\'s algo to solve Minimum Spanning Tree Problem

Binary search algorithm

### Linear Time Algorithms

n_th term of fibonacci series Kurskal\'s - min cost spanning tree - mouse support

# Program to implement the Kurskals Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics

# 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

***************************************************************/

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;
}