پياده سازي الگوريتم كروسكال و پرايم

خوب حالا اين الگوريتم کروسکال چي هست ؟

تا اونجا که یادمه مربوط میشد به درخت های باینری BST
فکر کنم پرایم و کروسکال مربوط بود به پیدا کردن زیر درختی از یک گراف وزن دار که مجموع وزن هر راس از یک بیس کمترین باشه!
یال ها هر کدوم وزن دارن!
حتما تو ویکی پیدا میشه!
واسه کدش هم google it !

سلام بچه ها
اینا رو یه نگا بندازین
خودم خیلی وقت پیش نوشتم
پریم:

کد:

---

http://fateme66.persiangig.com/PERIM.CPP

---

کد:

---

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

}

---

کوله پشتی:

کد:

---

http://fateme66.persiangig.com/KNAPSACK.CPP

---

کد:

---

#include <conio.h>
#include <stdio.h>
#include <iostream.h>
void sortbypw(int p[],int w[],int n)
{
 int i,t,j;
 for (i=0;i<=n-1;i++)
  for (j=i+1;j<=n;j++)
    if(((float)p[i]/w[i])<((float)p[j]/w[j]))
      {
        t=p[i];
        p[i]=p[j];
        p[j]=t;
        t=w[i];
        w[i]=w[j];
        w[j]=t;
        }
}

float knapsack(int p[],int w[],int n,int m)
{
sortbypw(p,w,n);
int w1=m;
int i=0;
float pp=0;
while (i<=n && w1>0)
 {
  if (w[i]<w1)
  {
    cout<<" p : "<<p[i];
    w1-=w[i];
    pp+=p[i];
    i++;
  }
  else
  {
    cout<<" p : "<<p[i];
    pp+=w1*((float)p[i]/w[i]);
    w1=0;
  }
 }
 return pp;
}

void main()
{
 int p[100]={6,12,7,18,9,30};
 int w[100]={1,5,3,9,5,20};
 clrscr();
 cout<<"If You Want Input Data Press (Y) Else Press (N) :";
 char ch=getche();
 if (ch=='n')
          cout<<"\n\n Arzesh Knapsack : "<<knapsack(p,w,5,20);
 else
        {
        int n,m;
        cout<<"\nEnter Weight Knapsack : ";
        cin>>m;
        cout<<"Enter Num : ";
        cin>>n;
        for (int i=0;i<n;i++)
        {
          cout<<"Enter Arzesh : ";
          cin>>p[i];
          cout<<"\nEnter Weight : ";
          cin>>w[i];
          gotoxy(20,wherey()-2);
          cout<<" P/W Is : "<<(float)p[i]/w[i];
          gotoxy(1,wherey()+2);
          cout<<".......................................\n";
        }
          cout<<"\n\n Arzesh Knapsack : "<<knapsack(p,w,n-1,m);
        }
 getch();
}

---

کروسکال

کد:

---

http://fateme66.persiangig.com/KRUSKAL.CPP

---

کد:

---

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

---

خانم فاطمه، من یه سوال از حضورشما داشتم.
من این دو تا الگوریتم رو به هم لینک کردم، میشه به من بگید اشگال کار از کجاست؟؟؟!
راستش من میخوام به وسیله ی Switch Case و همچنین یه ساختار Menu این دو تا الگوریتم رو اعمال کنم!
راستش استاد از ما یه پروژه خواسته که توی اوkن:
کاربر یه گراف رو ذخیره میکنه،با فشردن عدد های 1 و 2 پیمایش های عمقی و سطحی و انجام میشه، ضمن اینکه الگوریتم های دایگسترا، پریم، کروسکال هم اعمال میشه.

میشه من رو راهنمایی کنید؟!
کامپایلر از من اشگال نمیگیره، اما میدونم که این برنامه خالی از اشگال نیست.
چون موقع اجرا اشگالات اون به چشم میاد...!
خیلی ممنون میشم.

کد:

---

http://omidlovers.persiangig.com/%2B%2B1111%20-%20Copy.cpp

---

کد:

---

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

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


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

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

}

//***********************************************
int menu();
//***********************************************
void main()
{

  int n,m;

  while (1)
    {
    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;
  }

        clrscr() ;
        switch (menu())
        {

        case 1:

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

        break ;

        case 2:

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

      }//end of switch
    } //end of while
} // end of main
//********************
int menu()
{
    int c;
    cout << "1.Enter number to Kruskal\n";
    cout << "2.Enter number to Prime\n";
    cout << "3.......\n";
    cout << "4.Exit from program\n";
    cout << "Enter your select(1-4):";
    cin >> c;
    return c;
}

---

دوست من الان کامپایلر ندارم
شما بنویس از کدوم خط ها خطا می گیره و چه خطایی تا راهنمایی کنم

سلام . من تست کردم و syntax error نداشتن . ( البته داشتن و اون هم تعريف متغير بود که حل شد ) ولي من دقيقا نمي دونم برنامه قراره چيکار بکنه . اگه يه توضيحي بدين که اين برنامه چيکار مي کنه شايد بتونم ايراد منطقيشو پيدا کنم . الگوريتم پريم مي دونم يعني چي ( تو ساختمان گسسته خونديم :31: ) ولي کروسکال نه . آخه من فکر مي کردم خودش درخت رسم مي کنه . ولي حالا که اجرا کردم ديدم عدد و اينا مي خواد و آخرش هم نفهميدم اون چيزايي که چاپ کرد چي بودن .

سلام ولی تا جایی که من یادمه این برنامه ها خطا نداشته حالا ممکنه تو کپی و پیست یه اشکالاتی پیش اومده باشه
که شما حلش کردین ولی خطای منطقی بعید می دونم
البته لازم به ذکره که من اینا رو 2 سال پیش نوشتم و واقعا الان زیاد یادم نیست...

نقل قول:

---

نوشته شده توسط فاطـمه [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

سلام ولی تا جایی که من یادمه این برنامه ها خطا نداشته حالا ممکنه تو کپی و پیست یه اشکالاتی پیش اومده باشه
که شما حلش کردین ولی خطای منطقی بعید می دونم
البته لازم به ذکره که من اینا رو 2 سال پیش نوشتم و واقعا الان زیاد یادم نیست...

---

سلام ...........
خطا که عرض کردم عدم تعريف متغير بوده . که اون هم مهم نيست . والا من چنين جسارتي نمي کنم که بگم ايراد منطقي داره . :20:

اون دوستمون برنامه خودشونو مي گفتن چرا جواب نميده نه برنامه شما. :46: