PDA

View Full Version : الگوریتم های پریم ، کروسکال و دیکسترا به زبان c#



loknatesabz
پنج شنبه 10 آذر 1390, 17:38 عصر
سلام
من میخوام الگوریتم های پریم ، کروسکال و دیکسترا رو به زبان c# بنویسم لطفاً هرکسی که بلده منو راهنمایی کنه. ممنون میشم.

j_naroogha@yahoo.com
پنج شنبه 10 آذر 1390, 17:48 عصر
سلام
در کتاب طراحی الگوریتم نپیولیتن به صورت شبه کد نوشته شده. میتونی ازش گمگ بگیری.
اما باید گره هات رو به صورت یه ماتریس وزنی دربیاری (گره هات به یه آرایه دو بعدی تبدیل میشه.)

loknatesabz
جمعه 11 آذر 1390, 09:34 صبح
مرسی j_naroogha@yahoo.com . متاسفانه من کتابی رو که گفتی ندارم. نمی دونم باید چی کار کنم چون برای پس فردا میخوامشون؟ هرکسی برنامه رو داره لطفا برام آپ کنه. ممنونتونم

مرتضی تقدمی
جمعه 11 آذر 1390, 10:05 صبح
سلام
ببین این کمکت می کنه.
کروسکال :


#include <stdio.h>
#include <conio.h>
#include <iostream.h>

int kruskal_mst(int set[],struct krus edge[],int n,int m);
void sort(struct krus ed[],int m);

struct krus{
int v1;
int v2;
int weight;
};
int g=0;

void main()
{
clrscr();
int n,m;

cout<<"Input Num Vertex : ";
cin>>n;
int set[10];
for (int i=0;i<n;i++)
set[i]=i;

cout<<"Input Num Yal : ";
cin>>m;
struct krus edge[20];

for (i=0;i<m;i++)
{
cout<<"Num V1 : "; cin>>edge[i].v1;
cout<<"Num V2 : "; cin>>edge[i].v2;
cout<<"Weight : "; cin>>edge[i].weight;
}
sort(edge,m);

for (i=0;i<m;i++)
cout<<"("<<edge[i].v1<<","<<edge[i].v2<<") => W :"<<edge[i].weight<<"\n";

cout<<"Weight Is : "<<kruskal_mst(set,edge,n,m);
getch();
}
//***********************************************
void sort(struct krus ed[],int m)
{
struct krus temp;
for (int i=0;i<m;i++)
for (int j=i+1;j<m;j++)
if (ed[j].weight<ed[i].weight)
{
temp=ed[i];
ed[i]=ed[j];
ed[j]=temp;
}
}
//**************************************************
int kruskal_mst(int set[],struct krus edge[],int n,int m)
{
int fe=0;
int p=0;
struct krus e;
while (fe<n-1 && g<m)
{
e=edge[g++];
if (set[e.v1] != set[e.v2])
{
p+=e.weight;
int k=set[e.v1];
for (int i=0;i<n;i++)
if (set[i]==k)
set[i]=set[e.v2];
fe++;
}
}
if(fe==n-1) return p;
else
return -1;
}

مرتضی تقدمی
جمعه 11 آذر 1390, 10:06 صبح
این هم پریم :


#include <stdio.h>
#include <conio.h>
#include <iostream.h>

int perim (int set[],struct krus edge[],int n,int m);
void sort(struct krus ed[],int m);

struct krus{
int v1;
int v2;
int weight;
};

void main()
{
clrscr();
int n,m;

cout<<"Input Num Vertex : ";
cin>>n;
int set[10];
for (int i=0;i<n;i++)
set[i]=i;

cout<<"Input Num Yal : ";
cin>>m;
struct krus edge[20];

for (i=0;i<m;i++)
{
cout<<" Num V1 : "; cin>>edge[i].v1;
cout<<" Num V2 : "; cin>>edge[i].v2;
cout<<" Weight : "; cin>>edge[i].weight;
gotoxy(wherex()+30,wherey()-2);
cout<<"("<<edge[i].v1<<","<<edge[i].v2<<") => W :"<<edge[i].weight<<"\n";
gotoxy(1,wherey()+2);
}
cout<<"\nWeight Is : "<<perim(set,edge,n,m);
getch();
}
//***********************************************
int perim(int set[],struct krus edge[],int n,int m)
{
int fe=0;
int p=0;
struct krus e;
while (fe<n-1)
{
//********************************
int y=0;
e.weight=0;
for (int i=0;i<m;i++)
if ((set[edge[i].v1]==0 && set[edge[i].v2]!=0) || (set[edge[i].v2]==0 && set[edge[i].v1]!=0))
{
if(y==0)
{
e=edge[i];
y++;
}
else
if (e.weight>edge[i].weight)
e=edge[i];
}
//**********************************
if (y!=0)
{
p+=e.weight;
cout<<"("<<e.v1<<","<<e.v2<<") => W :"<<e.weight<<"\t";
set[e.v1]=0;
set[e.v2]=0;
fe++;
}
else
break;
}
return p;

}

loknatesabz
جمعه 11 آذر 1390, 10:48 صبح
سلام
متشکرم مرتضی تقدمی از لطفت.این دو تا رو اتفاقا همین چند ساعت پیش قبل از اینکه تاپیک بذارم دانلود کردم سی پلاس پلاسه؛ دارم به سی شارپ تبدیلش میکنم یه کم کار میبره. بازم ازت ممنونم
دیگه نیاز به گفتن نیست اما اگه کسی سی شارپ برنامه ها رو داره لطفا بذاره...

kimiaie
جمعه 01 دی 1391, 23:55 عصر
ممنون
خیلی عالی بود