واضح آرشیو وب فارسی:سایت ریسک: شبه کد در مورد الگوریتم kruskal neginetazevared 05 خرداد 1386, 06:35من باید برنامه کراسکال را بنویسم .ولی تابع kruskal را هم بلد نیستم .اگر کسی تابع کراسکال را بلد هست به من کمک کنه؟!!! the_king 23 خرداد 1388, 02:33کد برنامه زیر الگوریتم کراسکال (Kruskal) را به زبان ++C ارائه می کند : #include <stdio.h> #include <conio.h> #include <iostream.h> #define MAX 100 class kruskal { private : struct edge_info { int u, v, weight; } edge[MAX]; int tree[MAX][2], set[MAX]; int n; public : int readedges(); void makeset(); int find(int); void join(int, int); void arrange_edges(int); int spanningtree(int); void display(int); }; int kruskal :: readedges() { int i, j, k, cost; k = 1; cout << " Enter the number of Vertices in the Graph : "; cin >> n; cout << endl; for (i = 1; i <= n; i++) for (j = 1; j < i; j++) { cout << "weight[" << i << "][" << j << "] : "; cin >> cost; if (cost != 999) { edge[k].u = i; edge[k].v = j; edge[k++].weight = cost; } } return (k - 1); } void kruskal :: makeset() { int i; for (i = 1; i <= n; i++) set[i] = i; } int kruskal :: find(int vertex) { return (set[vertex]); } void kruskal :: join(int v1, int v2) { if (v1 < v2) set[v2] = v1; else set[v1] = v2; } void kruskal :: arrange_edges(int k) { int i, j; struct edge_info temp; for (i = 1; i < k; i++) for (j = 1; j <= k - i; j++) if (edge[j].weight > edge[j + 1].weight) { temp = edge[j]; edge[j] = edge[j + 1]; edge[j + 1] = temp; } } int kruskal :: spanningtree(int k) { int i, t, sum; arrange_edges(k); t = 1; sum = 0; for (i=1;i<=k;i++) cout << edge[i].u << edge[i].v << " " << edge[i].weight << endl; getch(); for (i = 1; i <= k; i++) if (find (edge[i].u) != find (edge[i].v)) { tree[t][1] = edge[i].u; tree[t][2] = edge[i].v; sum += edge[i].weight; join (edge[t].u, edge[t].v); t++; } return sum; } void kruskal :: display(int cost) { int i; cout << " The Edges of the Minimum Spanning Tree are "; for (i = 1; i < n; i++) cout << tree[i][1] << " - " << tree[i][2] << endl; cout << " The Cost of the Minimum Spanning Tree is : " << cost; } int main() { int ecount, totalcost; kruskal k; ecount = k.readedges(); k.makeset(); totalcost = k.spanningtree(ecount); k.display(totalcost); return 0; } کد برنامه بصورت zip شده ضمیمه این پست می باشد.
این صفحه را در گوگل محبوب کنید
[ارسال شده از: سایت ریسک]
[مشاهده در: www.ri3k.eu]
[تعداد بازديد از اين مطلب: 1986]