স্প্যানিং ট্রি হলো একটি কানেক্টেড এবং আনডাইরেক্টেড গ্রাফের সাবগ্রাফ যা সব ভের্টেক্স কানেক্ট করে। একটি গ্রাফে অনেক স্প্যানিং ট্রি থাকতে পারে। মিনিমাম স্প্যানিং ট্রি (MST) হলো যেটির ওয়েট সবচেয়ে কম বা সমান। MST-এ (V-1)টি এজ থাকে।
কৃষ্কালের অ্যালগরিদম
- সभी এজ ওয়েট অনুযায়ী অ্যাসেন্ডিং অর্ডারে সর্ট করুন
- সবচেয়ে ছোট এজ নিন। সাইকেল না বানালে অন্তর্ভুক্ত করুন
- (V-1)টি এজ হয়ারপর্যন্ত পুনরাবৃত্তি করুন
উদাহরণ
একটি গ্রাফের এজগুলো ওয়েট অনুযায়ী সর্ট করার পর ক্রমানুসারে এজ নির্বাচন করা হয়েছে। সাইকেল বানালে এজ বাদ দেওয়া হয়েছে।
C++ বাস্তবায়ন
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Edge { int src, dest, weight; };
struct Graph { int V, E; Edge* edge; };
Graph* createGraph(int V, int E) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V; graph->E = E;
graph->edge = (Edge*)malloc(sizeof(Edge) * E);
return graph;
}
struct subset { int parent, rank; };
int find(subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(subset subsets[], int x, int y) {
int xroot = find(subsets, x), yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
int myComp(const void* a, const void* b) {
Edge* a1 = (Edge*)a; Edge* b1 = (Edge*)b;
return a1->weight > b1->weight;
}
void KruskalMST(Graph* graph) {
int V = graph->V;
Edge result[V];
int e = 0, i = 0;
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
subset* subsets = (subset*)malloc(V * sizeof(subset));
for (int v = 0; v < V; ++v) {
subsets[v].parent = v; subsets[v].rank = 0;
}
while (e < V - 1 && i < graph->E) {
Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
printf("Following are the edges in the constructed MST\n");
int minimumCost = 0;
for (i = 0; i < e; ++i) {
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
minimumCost += result[i].weight;
}
printf("Minimum Cost Spanning tree : %d", minimumCost);
}
int main() {
int V = 4, E = 5;
Graph* graph = createGraph(V, E);
graph->edge[0] = {0, 1, 10};
graph->edge[1] = {0, 2, 6};
graph->edge[2] = {0, 3, 5};
graph->edge[3] = {1, 3, 15};
graph->edge[4] = {2, 3, 4};
KruskalMST(graph);
return 0;
}
আউটপুট
Following are the edges in the constructed MST 2 -- 3 == 4 0 -- 3 == 5 0 -- 1 == 10 Minimum Cost Spanning tree : 19
উপসংহার
কৃষ্কালের অ্যালগরিদম ব্যবহার করে MST বের করার C++ বাস্তবায়ন দেখানো হয়েছে। এটি লোভী (greedy) পদ্ধতির উদাহরণ।
