# include <iostream.h>
# include <stdlib.h>
# include <conio.h>
# define MAX_VERTICES 10
# define MAX_EDGES 15
class Vertex
{
public:
int label;
public:
Vertex( ) { }
~Vertex( ) { }
void SetVertex(const int);
};
class Edge
{
public:
int weight;
Vertex V1;
Vertex V2;
public:
Edge( ) { }
~Edge( ) { }
void SetEdge(const Vertex,const Vertex,const int);
};
void Vertex::SetVertex(const int _label)
{
label=_label;
}
void Edge::SetEdge(const Vertex _V1,const Vertex _V2,const int _weight)
{
V1=_V1;
V2=_V2;
weight=_weight;
}
int main( )
{
clrscr( );
Sample Input
************
Vertices , Edges
۶ , ۱۰
Vertex_1 , Vertex_2
۳۲۰ , ۱۰۰
۱۷۰ , ۲۰۰
۳۲۰ , ۲۵۰
۴۷۰ , ۲۰۰
۲۲۰ , ۴۰۰
۴۲۰ , ۴۰۰
Vertxe_1 —-> Vertex_2 , Weight
۱ —-> 2 , 6
۱ —-> 4 , 5
۱ —-> 3 , 1
۲ —-> 3 , 5
۲ —-> 5 , 3
۳ —-> 5 , 6
۳ —-> 6 , 4
۳ —-> 4 , 5
۴ —-> 5 , 2
۵ —-> 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];
for(int count=0;count<vertices;count++)
V[count].SetVertex(count);
int v1;
int v2;
int weight;
cout<<“\n ** 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 Kruskal’s Algorithm…”;
getch( );
clrscr( );
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;
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_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;
}
|
دیدگاهتان را بنویسید