دانلود سورس الگوریتم کراسکال در سی پلاس پلاس
در این قسمت تیم کدگیت فایل دانلود سورس الگوریتم کراسکال در سی پلاس پلاس را آماده کرده است. برای اجرای پروژه، کافیست فایل دانلود شده را به پروژه خود اضافه و آن را اجرا کنید. پیشنهاد میشود قبل از دانلود، آموزشهای ابتدایی سی پلاس پلاس را بخوانید.
الگوریتم کراسکال
در نظریه گراف، الگوریتم کراسکال الگوریتمی برای یافتن یک زیرگراف فراگیر همبند با کمترین وزن در یک گراف وزندار است (در یک گراف وزن دار، به هر یال وزنی نسبت داده شدهاست). همچنین این الگوریتم برای یافتن کوچکترین درخت فراگیر در یک گراف وزن دار استفاده میشود(ویکیپدیا).
یک نمونه خروجی برنامه به صورت زیر میباشد:
Following are the edges in the constructed MST
2 -- 3 and weight == 4
0 -- 3 and weight == 5
0 -- 1 and weight == 10
قسمتی از کد برنامه به صورت زیر میباشد:
void KruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge result[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
// Step 1: Sort all the edges in non-decreasing order of their weight
// If we are not allowed to change the given graph, we can create a copy of
// array of edges
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
// Allocate memory for creating V ssubsets
struct subset *subsets = (struct subset*) malloc(V * sizeof(struct subset));
// Create V subsets with single elements
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Number of edges to be taken is equal to V-1
while (e < V - 1) {
// Step 2: Pick the smallest edge. And increment the index
// for next iteration
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge does't cause cycle, include it
// in result and increment the index of result for next edge
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}
// print the contents of result[] to display the built MST
printf("Following are the edges in the constructed MST\n");
for (i = 0; i < e; ++i)
printf("%d -- %d and weight == %d\n", result[i].src, result[i].dest,
result[i].weight);
return;
}
در این برنامه از گراف زیر به عنوان ورودی استفاده شده است:
دانلود سورس کد
زبان برنامهنویسی: سی پلاس پلاس
نوع فایل: Rar
حجم فایل: 3 کیلوبایت
Download “دانلود سورس کد الگوریتم کراسکال در سی پلاس پلاس”
Kruskal-Algorithm-Code-in-Cpp-www.CodeGate.ir_.rar – 266 بار دانلود شده است – 2,02 کیلوبایت پسورد: www.codegate.ir