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

C++ में STL का उपयोग करके क्रुस्कल का न्यूनतम स्पैनिंग ट्री (Kruskal's Minimum Spanning Tree using STL in C++)


इस ट्यूटोरियल में, हम C++ में STL का उपयोग करके क्रुस्कल के न्यूनतम स्पैनिंग ट्री को समझने के लिए एक प्रोग्राम पर चर्चा करेंगे।

इसके लिए, हमें एक कनेक्टेड, अनडायरेक्टेड और वेटेड ग्राफ प्रदान किया जाएगा। हमारा कार्य दिए गए ग्राफ के लिए न्यूनतम स्पैनिंग ट्री की गणना करना है।

उदाहरण

#include<bits/stdc++.h> 
using namespace std; 

typedef pair<int, int> iPair; 

// ग्राफ के लिए संरचना 
struct Graph{ 
    int V, E; 
    vector<pair<int, iPair>> edges; 
    
    Graph(int V, int E){ 
        this->V = V; 
        this->E = E; 
    } 
    
    void addEdge(int u, int v, int w){ 
        edges.push_back({w, {u, v}}); 
    } 
    
    int kruskalMST(); 
}; 

struct DisjointSets{ 
    int *parent, *rnk; 
    int n; 
    
    DisjointSets(int n){ 
        this->n = n; 
        parent = new int[n+1]; 
        rnk = new int[n+1]; 
        for (int i = 0; i <= n; i++){ 
            rnk[i] = 0; 
            parent[i] = i; 
        } 
    } 
    
    int find(int u){ 
        if (u != parent[u]) 
            parent[u] = find(parent[u]); 
        return parent[u]; 
    } 
    
    void merge(int x, int y){ 
        x = find(x), y = find(y); 
        if (rnk[x] > rnk[y]) 
            parent[y] = x; 
        else 
            parent[x] = y; 
        if (rnk[x] == rnk[y]) 
            rnk[y]++; 
    } 
}; 

int Graph::kruskalMST(){ 
    int mst_wt = 0; 
    sort(edges.begin(), edges.end()); 
    DisjointSets ds(V); 
    
    for(auto it = edges.begin(); it != edges.end(); it++){ 
        int u = it->second.first; 
        int v = it->second.second; 
        int set_u = ds.find(u); 
        int set_v = ds.find(v); 
        
        if (set_u != set_v){ 
            cout << u << " - " << v << endl; 
            mst_wt += it->first; 
            ds.merge(set_u, set_v); 
        } 
    } 
    return mst_wt; 
} 

int main(){ 
    int V = 9, E = 14; 
    Graph g(V, E); 
    g.addEdge(0, 1, 4); 
    g.addEdge(0, 7, 8); 
    g.addEdge(1, 2, 8); 
    g.addEdge(1, 7, 11); 
    g.addEdge(2, 3, 7); 
    g.addEdge(2, 8, 2); 
    g.addEdge(2, 5, 4); 
    g.addEdge(3, 4, 9); 
    g.addEdge(3, 5, 14); 
    g.addEdge(4, 5, 10); 
    g.addEdge(5, 6, 2); 
    g.addEdge(6, 7, 1); 
    g.addEdge(6, 8, 6); 
    g.addEdge(7, 8, 7); 
    
    cout << "Edges of MST are \n"; 
    int mst_wt = g.kruskalMST(); 
    cout << "\nWeight of MST is " << mst_wt; 
    return 0; 
}

आउटपुट

Edges of MST are 6 - 7 2 - 8 5 - 6 0 - 1 2 - 5 2 - 3 0 - 7 3 - 4 Weight of MST is 37
  1. C++ में बाइनरी ट्री की न्यूनतम गहराई C++ में बाइनरी ट्री की न्यूनतम गहराई

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

  1. C++ में ट्री नोड्स डिलीट करें C++ में ट्री नोड्स डिलीट करें

    मान लीजिए हमारे पास एक ट्री है, यह ट्री नोड 0 पर रूटेड है, यह निम्नानुसार दिया गया है -नोड्स की संख्या nodes हैi-वें नोड का मान value[i] हैi-वें नोड का पैरेंट parent[i] हैहमें हर उस सबट्री को हटाना है जिसके नोड्स के मानों का योग 0 है, ऐसा करने के बाद ट्री में शेष नोड्स की संख्या लौटाएं। यदि ट्री इस

  1. C++ में ट्री डायमीटर C++ में ट्री डायमीटर

    मान लीजिए हमारे पास एक अनडायरेक्टेड ट्री है; हमें इसका डायमीटर ढूंढना है - उस ट्री में सबसे लंबे पथ में एज की संख्या उस ट्री का डायमीटर है। यहां ट्री को एज लिस्ट के रूप में दिया गया है जहां edges[i] = [u, v] नोड्स u और v के बीच एक बायडायरेक्शनल एज है। प्रत्येक नोड के लेबल सेट {0, 1, ..., edges.lengt