تبليغات
تبلیغات در دانشجو کلوب محک :: موسسه خيريه حمايت از کودکان مبتلا به سرطان ::
جستجوگر انجمن.براي جستجوي مطالب دانشجو کلوپ مي توانيد استفاده کنيد 
برای بروز رسانی تاپیک کلیک کنید
 
امتیاز موضوع:
  • 1 رأی - میانگین امتیازات: 5
  • 1
  • 2
  • 3
  • 4
  • 5

الگوریتم کروسکال به زبان ++c

نویسنده پیام
  • navid
    آفلاین
  • مدیر بازنشسته
    **
  • ارسال‌ها: 1,344
  • تاریخ عضویت: مرداد ۱۳۹۰
  • اعتبار: 85
  • تحصیلات:لیسانس
  • علایق:برنامه نویسی
  • محل سکونت:Istanbul, Turkey
  • سپاس ها 1152
    سپاس شده 3031 بار در 1139 ارسال
  • امتیاز کاربر: 27,279$
  • حالت من:حالت من
ارسال: #1
الگوریتم کروسکال به زبان ++c

کد:
#define N 100  
#define M 10000
#include<iostream>
#include <stdlib.h>
using namespace std;
// UNION FIND DATA STRUCURE STARTS
struct data{
int name;
int size;
struct data *home;
};
typedef struct data mydata;
 
class makeunionfind
{
public :
 mydata S[N];
public:
makeunionfind(int n)
{
    for(int i=0;i<n;i++)
    {
       S[i].name=i+1;
       S[i].size=0;
       
       S[i].home=&S[i];
    }
    
}    
    
void myunion(int a, int b)
{
     int sizea,sizeb;
     sizea=S[a-1].home->size;
     sizeb=S[b-1].home->size;
    if(sizea>sizeb)
    {
       (S[b-1].home)->home=S[a-1].home;
       S[a-1].size=sizea+sizeb;
       
    }
    else
    {
        (S[a-1].home)->home=S[b-1].home;
        S[b-1].size=sizea+sizeb;
        
    }
    
}
int myfind(int a)
{
    mydata *temp,*temp2,*stoppoint;
    int result;
    temp2=&S[a-1];
    temp=S[a-1].home;
    while(temp2!=temp)
    {                        
          temp2=temp;
          temp=(*temp2).home;              
    }
    result=temp2->name;
     stoppoint=temp2;
       temp2=&S[a-1];
   //path compression
     do{
           temp=temp2->home;       
           (*temp2).home=stoppoint;
           temp2=temp;         
     }while(temp2!=stoppoint);   
     return result;                                     
}
};
//UNION FIND DATA STRUCURE ends
//Krushkal Algo starts
struct node{
int name;
};
typedef struct node mynode;
class edge
{
    public :
    mynode *start,*end;
    double cost;
    edge()
    {
        start=NULL;
        end=NULL;
        cost=0;
    } 
};
struct edges{
	edge e;
};
int compare(const void *a,const void *b )
{
	edge *a1,*b1;
	a1=(edge*)a;
	b1=(edge*)b;
    if(a1->cost<b1->cost)
    return -1;
    else if (a1->cost>b1->cost)
    return 1;
    else
    return 0;
    
}
void *kruskal(edge *e,int n,int m,int *size,edge *ans)
{
    makeunionfind list(n);
    int (*comp)(const void *a,const void *b );
	int k=0;
    comp=compare;
    qsort((void*)e,m,sizeof(e[0]),comp);
    for(int i=0;i<m;i++)
    {
        int s,f;
        s=(e[i].start)->name;
        f=(e[i].end)->name;
        
        if(list.myfind(s)==list.myfind(f))
        {
            continue;
        }
        else
        {
          list.myunion(s,f);
          ans[k]=e[i];
          k++;      
        }
    
    }
    *size=k;
    return ans;    

}

int main()
{
    mynode nodes[N];
    edge e[M];
    int n,m; // n is the number of nodes , m is no. of nodes
    cin>>n;
    for(int i=0;i<n;i++){
    nodes[i].name=i+1;
    }
    // temp1 is starting node temp2 is ending node temp3 is cosr
    int temp1,i;   
    cin>>temp1;
    for (i=0;temp1!=0;i++)
    {
        int temp2;
        double temp3;
        cin>>temp2;
        cin>>temp3;
        e[i].start=&nodes[temp1-1];
        e[i].end=&nodes[temp2-1];
        e[i].cost=temp3;
        cin>>temp1;    
    }
    m=i;
      
      edge ans[M];
      int size;
      kruskal(e,n,m,&size,ans);
      
      for(int p=0;p<size;p++)
      {
         cout<<p+1<<")  start "<<(ans[p].start)->name<<"  end "<<(ans[p].end)->name<<endl;
      }
     return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172



مطالب مشابه ...










تن آدمی شریف است به جیب آدمیت و همین لباس زیباست نشان آدمیت !

(آخرین ویرایش در این ارسال: ۲۵-۷-۱۳۹۰ ۰۸:۲۰ عصر، توسط navid.)
۲۵-۷-۱۳۹۰ ۰۸:۱۹ عصر
جستجو یافتن همه ارسال های کاربر اهدا امتیازاهدای امتیاز به کاربر پاسخ پاسخ با نقل قول
 سپاس شده توسط ♔ αϻἰг κнаη ♔ ، senior engineer

برای بروز رسانی تاپیک کلیک کنید


مطالب مشابه ...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  برنامه ای که یک عدد رابه حروف تبدیل می کند به زبان c++ ♔ αϻἰг κнаη ♔ 0 3,065 ۲۲-۱۱-۱۳۹۱ ۰۴:۴۰ عصر
آخرین ارسال: ♔ αϻἰг κнаη ♔
  برنامه ماشین حساب گرافیکی به زبان c++ ♔ αϻἰг κнаη ♔ 0 3,608 ۲۱-۱۱-۱۳۹۱ ۱۱:۱۷ عصر
آخرین ارسال: ♔ αϻἰг κнаη ♔
  برنامه دفتر چه تلفن به زبان c++ ♔ αϻἰг κнаη ♔ 0 473 ۲۱-۱۱-۱۳۹۱ ۱۱:۱۶ عصر
آخرین ارسال: ♔ αϻἰг κнаη ♔
  سورس هایی به زبان ++C -دفتر تلفن aylin 0 289 ۲۰-۱۱-۱۳۹۱ ۰۱:۲۵ صبح
آخرین ارسال: aylin
  الگوریتم 8 وزیر ♔ αϻἰг κнаη ♔ 1 856 ۲۹-۴-۱۳۹۱ ۱۰:۴۹ عصر
آخرین ارسال: _sahar_
  برنامه به زبان ++c navid 1 511 ۱۵-۱-۱۳۹۱ ۰۵:۰۶ عصر
آخرین ارسال: mahdi loveless
  چاپ مختصات اعداد یک ماتریس به زبان ++c navid 0 700 ۲۴-۸-۱۳۹۰ ۱۰:۱۵ عصر
آخرین ارسال: navid
  روش دیگری برای پیمایش maze به زبان ++c navid 0 419 ۲۴-۸-۱۳۹۰ ۰۹:۵۴ عصر
آخرین ارسال: navid
  پیدا کردن مسیر maze به زبان ++c navid 0 1,668 ۲۴-۸-۱۳۹۰ ۰۹:۴۲ عصر
آخرین ارسال: navid
  پیدا کردن پیمایش dfs یک گراف به زبان ++c navid 0 1,908 ۲۴-۸-۱۳۹۰ ۰۹:۳۳ عصر
آخرین ارسال: navid

پرش به انجمن:

کاربرانِ درحال بازدید از این موضوع: 1 مهمان