پیاده سازی الگوریتم کراسکال Kurscal با سی پلاس

با پلاس

قیمت :   ۶۵۰۰ تومان ( شش هزار و پانصد تومان)

رشته :

کامپیوتر

نوع فایل:

,

توضیحات:


توضیحات :

پیاده سازی الگوریتم کراسکال Kurscal با سی پلاس

در نظریه گراف، الگوریتم کراسکال الگوریتمی برای یافتن یک زیرگراف فراگیر همبند با کمترین وزن در یک گراف وزن‌دار است (در یک گراف وزن دار، به هر یال وزنی نسبت داده شده‌است). همچنین این الگوریتم برای یافتن کوچکترین درخت فراگیر در یک گراف وزن دار استفاده می‌شود.

به عنوان مثال فرض کنید یک شبکه راه آهن که تعدادی شهر را به یکدیگر متصل می‌کند در دست احداث است می‌خواهیم با داشتن هزینه{c_{ij}} مربوط به احداث خط مستقیم بین شهرهای {v_i},{v_j} شبکه را طوری طراحی کنیم که مجموع هزینه‌های ساخت به کمترین مقدار خود برسد. با در نظر گرفتن هر شهر به عنوان یک راس از گراف وزن دار با وزن‌های w({v_i},{v_j})={c_{ij}} مسئله به یافتن یک زیر گراف فراگیر همبند با کمترین وزن در یک گراف منجر می‌شود.

پیاده سازی الگوریتم کراسکال Kurscal با سی پلاس و سورس کامل برنامه


همراه با فایلهای
EXE , CPP

مشاهده تصاویری از محیط فایل اجرایی این

kurscal1

kurscal2

مشاهده بخشهایی از سورس کد این پروژه :

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

دانلود کامل پروژه همراه با فایل سورس کد و فایل اجرایی آن
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه


پذیرش و انجام سفارشات پروژه های شما
شماره تماس پشتیبانی سایت : ۰۹۳۹۲۷۶۱۶۳۰

 

Related posts

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Translate »