एक फैले हुए पेड़ एक जुड़ा हुआ और अप्रत्यक्ष ग्राफ सबग्राफ है जो सभी शीर्षकों को जोड़ता है। कई फैले हुए पेड़ एक ग्राफ में मौजूद हो सकते हैं। प्रत्येक ग्राफ पर न्यूनतम फैले हुए पेड़ (MST) का वजन अन्य सभी फैले हुए पेड़ों की तुलना में समान या कम होता है। वजन फैले हुए पेड़ों के किनारों को सौंपा गया है और योग प्रत्येक किनारे को सौंपा गया वजन है। चूँकि V ग्राफ़ में शीर्षों की संख्या है, न्यूनतम फैले हुए पेड़ के किनारे (V-1) हैं, जहाँ V किनारों की संख्या है।
क्रुस्कल के एल्गोरिथम का उपयोग करके न्यूनतम फैले हुए पेड़ ढूँढना
-
सभी किनारों को भार के अवरोही क्रम में व्यवस्थित किया जाना चाहिए।
-
सबसे छोटा किनारा चुनें। यदि चक्र नहीं बनता है तो इस किनारे को शामिल किया जाता है।
-
चरण 2 तब तक किया जाना चाहिए जब तक फैले हुए पेड़ में (V-1) किनारे न हों।
इस परिदृश्य में, हमें लालची पद्धति का उपयोग करने के लिए कहा जाता है। लालची विकल्प कम से कम वजन वाले किनारे का चयन करना है। उदाहरण के तौर पर:इस ग्राफ़ के लिए न्यूनतम फैले हुए पेड़ (9-1)=8 किनारे हैं।
After sorting: Weight 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++ कोड का उपयोग कैसे करें। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। यह क्रुस्कल की अवधारणा द्वारा तैयार किया गया था। यह प्रोग्राम किसी दिए गए ग्राफ़ में सबसे छोटा फैले हुए पेड़ को ढूंढता है। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।