एक स्पैनिंग ट्री एक लिंक्ड और अनडायरेक्टेड ग्राफ का सबग्राफ है जो सभी वर्टेक्स को जोड़ता है। एक ग्राफ में कई स्पैनिंग ट्री हो सकते हैं। प्रत्येक ग्राफ पर न्यूनतम स्पैनिंग ट्री (MST) का वजन अन्य सभी स्पैनिंग ट्री के समान या कम होता है। स्पैनिंग ट्री के किनारों को वजन दिए जाते हैं और योग प्रत्येक किनारे को दिए गए वजन का योग होता है। जैसा कि V ग्राफ में वर्टेक्स की संख्या है, न्यूनतम स्पैनिंग ट्री में (V - 1) किनारे होते हैं, जहां V किनारों की संख्या है।
क्रुस्कल के एल्गोरिदम का उपयोग करके न्यूनतम स्पैनिंग ट्री ढूंढना
सभी किनारों को वजन के गैर-अवरोही क्रम में व्यवस्थित किया जाना चाहिए।
सबसे छोटा किनारा चुनें। यदि चक्र नहीं बनता है तो इस किनारे को शामिल किया जाता है।
चरण 2 को तब तक किया जाना चाहिए जब तक स्पैनिंग ट्री में (V-1) किनारे न हो जाएं।
इस परिदृश्य में, हमें लालची विधि का उपयोग करने के लिए कहा गया है। लालची विकल्प सबसे कम वजन वाले किनारे का चयन करना है। एक उदाहरण के रूप में: इस ग्राफ के लिए न्यूनतम स्पैनिंग ट्री है (9-1)= 8 किनारे।

सॉर्टिंग के बाद: वजन Src Dest 21 27 26 22 28 22 22 26 25 24 20 21 24 22 25 26 28 26 27 22 23 27 27 28 28 20 27 28 21 22 29 23 24 30 25 24 31 21 27 34 23 25
अब हमें सॉर्ट के अनुसार सभी किनारों को चुनने की आवश्यकता है।
एज 26-27 -> शामिल क्योंकि कोई चक्र नहीं बनता
एज 28-22 -> शामिल क्योंकि कोई चक्र नहीं बनता
एज 26-25 -> शामिल क्योंकि कोई चक्र नहीं बनता।
एज 20-21 -> शामिल क्योंकि कोई चक्र नहीं बनता
एज 22-25 -> शामिल क्योंकि कोई चक्र नहीं बनता।
एज 28-26 -> चक्र बनने के कारण अस्वीकार
एज 22-23 -> शामिल क्योंकि कोई चक्र नहीं बनता
एज 27-28 -> चक्र बनने के कारण अस्वीकार
एज 20-27 -> शामिल क्योंकि कोई चक्र नहीं बनता
एज 21-22 -> चक्र बनने के कारण अस्वीकार
एज 23-24 -> शामिल क्योंकि कोई चक्र नहीं बनता
चूंकि किनारों की संख्या (V-1) है, इसलिए एल्गोरिदम यहां समाप्त होता है।
उदाहरण
#include <stdio.h> #include <stdlib.h> #include <string.h> struct Edge { int src, dest, weight; }; struct Graph { int V, E; struct Edge* edge; }; struct Graph* createGraph(int V, int E){ struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph))); graph->V = V; graph->E = E; graph->edge = (struct Edge*)malloc(sizeof( struct Edge)*E); return graph; } struct subset { int parent; int rank; }; int find(struct subset subsets[], int i){ if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } void Union(struct subset subsets[], int x, int y){ int xroot = find(subsets, x); int 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){ struct Edge* a1 = (struct Edge*)a; struct Edge* b1 = (struct Edge*)b; return a1->weight > b1->weight; } void KruskalMST(struct Graph* graph){ int V = graph->V; struct Edge result[V]; int e = 0; int i = 0; qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp); struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset)); for (int v = 0; v < V; ++v) { subsets[v].parent = v; subsets[v].rank = 0; } while (e < V - 1 && i < graph->E) { struct 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); return; } int main(){ /* Let us create the following weighted graph 30 0--------1 | \ | 26| 25\ |15 | \ | 22--------23 24 */ int V = 24; int E = 25; struct Graph* graph = createGraph(V, E); graph->edge[0].src = 20; graph->edge[0].dest = 21; graph->edge[0].weight = 30; graph->edge[1].src = 20; graph->edge[1].dest = 22; graph->edge[1].weight = 26; graph->edge[2].src = 20; graph->edge[2].dest = 23; graph->edge[2].weight = 25; graph->edge[3].src = 21; graph->edge[3].dest = 23; graph->edge[3].weight = 35; graph->edge[4].src = 22; graph->edge[4].dest = 23; graph->edge[4].weight = 24; KruskalMST(graph); return 0; }
आउटपुट
Following are the edges in the constructed MST 22 -- 23 == 24 20 -- 23 == 25 20 -- 21 == 30 Minimum Cost Spanning tree : 79
निष्कर्ष
इस ट्यूटोरियल ने दिखाया कि कैसे क्रुस्कल के न्यूनतम स्पैनिंग ट्री एल्गोरिदम-लालची विधि और C++ कोड का उपयोग करके इस समस्या को हल किया जाए। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। यह क्रुस्कल की अवधारणा द्वारा मॉडल किया गया था। यह प्रोग्राम दिए गए ग्राफ में सबसे छोटा स्पैनिंग ट्री ढूंढता है। हमें उम्मीद है कि आपको यह ट्यूटोरियल उपयोगी लगा।