### Divide and Conquer Strategy

Kurskal\'s algo to solve Minimum Cost Spanning Tree Towers of Hanoi Problem using Recursive Algorithm

### Cubic Time Algorithms

Prim\'s algo solve Minimum Spanning Tree - Graphic Bubble Sort Algorithm

### Logrithmic Time Algorithms

n_th term of fibonacci series - Toplogical Order Compute, display factorial using recursive algo Product of 2 matrices - Strassen\'s Algorithm

### Dynamic Programming Technique

Kurskal\'s algo - min cost spanning tree - graphics n_th term of fibonacci series - Divide and Conquer

### Exponential Time Algorithms

Prim\'s algo - min Spanning Tree - Mouse support Multiply two matrices

Prim\'s algo to solve Minimum Spanning Tree Problem Binary search algorithm

### Linear Time Algorithms

n_th term of fibonacci series

### Minimum Cost Spanning Tree Problem

Kurskal\'s - min cost spanning tree - mouse support Product of 2 matrices - Divide and Conquer

# Program to implement the Prims Algorithm to solve Minimum Spanning Tree Problem (MST)

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

# define MAX_VERTICES  10
# define MAX_EDGES     15

//-------------------------------  Vertex  ------------------------------//

class Vertex
{
public:
int label;

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

void SetVertex(const int);
};

//-------------------------------  Edge  --------------------------------//

class Edge
{
public:
int weight;

Vertex V1;
Vertex V2;

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

void SetEdge(const Vertex,const Vertex,const int);
};

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

void Vertex::SetVertex(const int _label)
{
label=_label;
}

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

void Edge::SetEdge(const Vertex _V1,const Vertex _V2,const int _weight)
{
V1=_V1;
V2=_V2;

weight=_weight;
}

int main( )
{
clrscr( );
textmode(BW80);

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

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

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

cout<<endl;

int v1;
int v2;
int weight;

cout<<\" **********  Edges and their Weights  ********* \"<<endl;

for(count=0;count<edges;count++)
{
cout<<\"    ----------       ---------->\";

gotoxy(2,wherey( ));
cin>>v1;

gotoxy(35,(wherey( )-1));
cin>>v2;

gotoxy(17,(wherey( )-1));
cin>>weight;

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

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

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

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

cout<<endl<<\"Press any key to Apply PRIMS Algorithm...\";

getch( );
clrscr( );

int U[MAX_VERTICES]={0};
int vertex_1[MAX_VERTICES]={0};
int vertex_2[MAX_VERTICES]={0};
int edge_weights[MAX_VERTICES]={0};
int resultant_weights[MAX_VERTICES]={0};

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) )
{
resultant_weights[(u_count-2)]=E[i].weight;

break;
}
}
}

else
break;
}
while(1);

cout<<\"*******************  Input  ********************\"<<endl;
cout<<\" V = { \";

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

cout<<count<<\" } \"<<endl;

cout<<\" E = { \";

for(count=0;count<edges;count++)
{
cout<<\"(\"<<(E[count].V1.label+1)<<\",\"<<(E[count].V2.label+1)<<\")\";

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

cout<<\" } \"<<endl<<endl;

cout<<\"*******************  Result  ********************\"<<endl;
cout<<\" U = { \";

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

cout<<(U[count]+1)<<\" }\"<<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<<endl<<endl;

cout<<endl<<\" Press any Key to Exit...\";

getch( );
return 0;
}
```