Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में क्रुस्कल का न्यूनतम स्पैनिंग ट्री एल्गोरिदम - लालची एल्गोरिदम


एक स्पैनिंग ट्री एक लिंक्ड और अनडायरेक्टेड ग्राफ का सबग्राफ है जो सभी वर्टेक्स को जोड़ता है। एक ग्राफ में कई स्पैनिंग ट्री हो सकते हैं। प्रत्येक ग्राफ पर न्यूनतम स्पैनिंग ट्री (MST) का वजन अन्य सभी स्पैनिंग ट्री के समान या कम होता है। स्पैनिंग ट्री के किनारों को वजन दिए जाते हैं और योग प्रत्येक किनारे को दिए गए वजन का योग होता है। जैसा कि V ग्राफ में वर्टेक्स की संख्या है, न्यूनतम स्पैनिंग ट्री में (V - 1) किनारे होते हैं, जहां V किनारों की संख्या है।

क्रुस्कल के एल्गोरिदम का उपयोग करके न्यूनतम स्पैनिंग ट्री ढूंढना

  • सभी किनारों को वजन के गैर-अवरोही क्रम में व्यवस्थित किया जाना चाहिए।

  • सबसे छोटा किनारा चुनें। यदि चक्र नहीं बनता है तो इस किनारे को शामिल किया जाता है।

  • चरण 2 को तब तक किया जाना चाहिए जब तक स्पैनिंग ट्री में (V-1) किनारे न हो जाएं।

इस परिदृश्य में, हमें लालची विधि का उपयोग करने के लिए कहा गया है। लालची विकल्प सबसे कम वजन वाले किनारे का चयन करना है। एक उदाहरण के रूप में: इस ग्राफ के लिए न्यूनतम स्पैनिंग ट्री है (9-1)= 8 किनारे।

C++ में क्रुस्कल का न्यूनतम स्पैनिंग ट्री एल्गोरिदम - लालची एल्गोरिदम

सॉर्टिंग के बाद: वजन  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++ कोड का उपयोग करके इस समस्या को हल किया जाए। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। यह क्रुस्कल की अवधारणा द्वारा मॉडल किया गया था। यह प्रोग्राम दिए गए ग्राफ में सबसे छोटा स्पैनिंग ट्री ढूंढता है। हमें उम्मीद है कि आपको यह ट्यूटोरियल उपयोगी लगा।

  1. C++ में बाइनरी ट्री की न्यूनतम गहराई C++ में बाइनरी ट्री की न्यूनतम गहराई

    समस्या विवरण मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उस ट्री की न्यूनतम गहराई ज्ञात करनी है। जैसा कि हम जानते हैं, न्यूनतम गहराई रूट नोड से निकटतम लीफ नोड तक के सबसे छोटे पथ पर नोड्स की संख्या है। उदाहरण यदि इनपुट ट्री है: तो आउटपुट होगा 2 हल करने का दृष्टिकोण इस समस्या को हल करने के लिए निम

  1. C++ में पूर्ण ग्राफ से अधिकतम संभव एज-डिसजॉइंट स्पैनिंग ट्री C++ में पूर्ण ग्राफ से अधिकतम संभव एज-डिसजॉइंट स्पैनिंग ट्री

    मान लीजिए हमारे पास एक पूर्ण ग्राफ है; हमें एज-डिसजॉइंट स्पैनिंग ट्री की संख्या गिननी है। एज-डिसजॉइंट स्पैनिंग ट्री वे स्पैनिंग ट्री हैं, जहां सेट में कोई दो ट्री एक एज साझा नहीं करते। मान लीजिए N (शीर्षों की संख्या) 4 है, तो आउटपुट 2 होगा। 4 शीर्षों का उपयोग करके पूर्ण ग्राफ नीचे जैसा है -दो एज-डिस

  1. डेटा स्ट्रक्चर में न्यूनतम स्पैनिंग ट्री डेटा स्ट्रक्चर में न्यूनतम स्पैनिंग ट्री

    एक स्पैनिंग ट्री एक अनडायरेक्टेड ग्राफ का एक सबसेट है जिसमें सभी वर्टेक्स न्यूनतम संख्या में एज द्वारा जुड़े होते हैं।यदि ग्राफ में सभी वर्टेक्स जुड़े हुए हैं, तो कम से कम एक स्पैनिंग ट्री मौजूद होती है। एक ग्राफ में एक से अधिक स्पैनिंग ट्री मौजूद हो सकती हैं।न्यूनतम स्पैनिंग ट्रीएक न्यूनतम स्पैनिंग