कर्स्कल का (मिनिमम स्पैनिंग ट्री) MST एल्गोरिदम

एक कनेक्टेड ग्राफ G(V,E) है और हर एज के लिए वजन या लागत दी गई है। कर्स्कल का एल्गोरिदम ग्राफ और लागत का उपयोग करके मिनिमम स्पैनिंग ट्री ढूंढेगा।

यह मर्ज ट्री दृष्टिकोण है। प्रारंभ में अलग-अलग ट्री हैं, यह एल्गोरिदम उन्हें उन एज को लेकर मर्ज करेगा जिनकी लागत न्यूनतम है, और एक सिंगल ट्री बनाएगा।

इस समस्या में, सभी एज सूचीबद्ध हैं, और उनकी लागत के आधार पर सॉर्ट किए गए हैं। सूची से, न्यूनतम लागत वाले एज निकाले जाते हैं और ट्री में जोड़े जाते हैं, और हर बार जांच की जाती है कि क्या एज साइकिल बना रहा है या नहीं, यदि यह साइकिल बनाता है तो सूची से एज को हटा दें और अगले एज के लिए जाएं।

• इस एल्गोरिदम की टाइम कॉम्प्लेक्सिटी O(E log E) या O(E log V) है, जहां E एज की संख्या है, और V वर्टेक्स की संख्या है।

इनपुट - एडजेसेंसी मैट्रिक्स

0 1 3 4 ∞ 5 ∞
1 0 ∞ 7 2 ∞ ∞
3 ∞ 0 ∞ 8 ∞ ∞
4 7 ∞ 0 ∞ ∞ ∞
∞ 2 8 ∞ 0 2 4
5 ∞ ∞ ∞ 2 0 3
∞ ∞ ∞ ∞ 4 3 0

आउटपुट -

Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15

एल्गोरिदम

kruskal(g: Graph, t: Tree)

इनपुट − दिया गया ग्राफ g, और एक खाली ट्री t

आउटपुट − चुने गए एज के साथ ट्री t

Begin
    ग्राफ g में प्रत्येक वर्टेक्स के लिए सेट बनाएं
    वर्टेक्स u के प्रत्येक सेट के लिए do
        u को vertexSet[u] में जोड़ें
    done
    एज लिस्ट को सॉर्ट करें।
    count := 0
    while count <= V - 1 do //क्योंकि ट्री में V - 1 एज होने चाहिए
        ed := edgeList[count] //एज लिस्ट से एक एज लें
        यदि ed के शुरुआती वर्टेक्स और अंतिम वर्टेक्स एक ही सेट में हैं तो
            vertexSet[स्टार्ट] और vertexSet[एंड] को मर्ज करें
            ed को ट्री t में जोड़ें
        count := count + 1
    done
End

उदाहरण (C++)

#include 
#define V 7
#define INF 999
using namespace std;
//ग्राफ का कॉस्ट मैट्रिक्स
int costMat[V][V] = {
    {0, 1, 3, 4, INF, 5, INF},
    {1, 0, INF, 7, 2, INF, INF},
    {3, INF, 0, INF, 8, INF, INF},
    {4, 7, INF, 0, INF, INF, INF},
    {INF, 2, 8, INF, 0, 2, 4},
    {5, INF, INF, INF, 2, 0, 3},
    {INF, INF, INF, INF, 4, 3, 0}
};
typedef struct{
    int u, v, cost;
}edge;
void swapping(edge &e1, edge &e2){
    edge temp;
    temp = e1;
    e1 = e2;
    e2 = temp;
}
class Tree{
    int n;
    edge edges[V-1]; //एक ट्री में वर्टेक्स-1 एज होते हैं
    public:
    Tree(){
        n = 0;
    }
    void addEdge(edge e){
        edges[n] = e; //ट्री में एज e जोड़ें
        n++;
    }
    void printEdges(){ //एज, लागत और कुल लागत प्रिंट करें
        int tCost = 0;
        for(int i = 0; i < n; i++){
            cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
            cout << " And Cost: " << edges[i].cost << endl;
            tCost += edges[i].cost;
        }
        cout << "Total Cost: " << tCost << endl;
    }
};
class VSet{
    int n;
    int set[V]; //एक सेट अधिकतम V वर्टेक्स रख सकता है
    public:
    VSet(){
        n = -1;
    }
    void addVertex(int vert){
        set[++n] = vert; //सेट में वर्टेक्स जोड़ें
    }
    int deleteVertex(){
        return set[n--];
    }
    friend int findVertex(VSet *vertSetArr, int vert);
    friend void merge(VSet &set1, VSet &set2);
};
void merge(VSet &set1, VSet &set2){
    //दो वर्टेक्स सेट को एक साथ मर्ज करें
    while(set2.n >= 0)
        set1.addVertex(set2.deleteVertex());
}
int findVertex(VSet *vertSetArr, int vert){
    //विभिन्न वर्टेक्स सेट में वर्टेक्स खोजें
    for(int i = 0; i < V; i++)
        for(int j = 0; j <= vertSetArr[i].n; j++)
            if(vert == vertSetArr[i].set[j])
                return i; //नोड i-वें वर्टेक्स सेट में मिला
}
int findEdge(edge *edgeList){
    //ग्राफ के कॉस्ट मैट्रिक्स से एज ढूंढें और edgeList में स्टोर करें
    int count = -1, i, j;
    for(i = 0; i < V; i++)
        for(j = 0; j < i; j++)
            if(costMat[i][j] != INF){
                count++;
                //पोजीशन 'count' के लिए एज लिस्ट भरें
                edgeList[count].u = i; edgeList[count].v = j;
                edgeList[count].cost = costMat[i][j];
            }
    return count+1;
}
void sortEdge(edge *edgeList, int n){
    //ग्राफ के एज को लागत के आरोही क्रम में सॉर्ट करें
    int flag = 1, i, j;
    for(i = 0; i < (n-1) && flag; i++){ //मॉडिफाइड बबल सॉर्ट उपयोग किया गया
        flag = 0;
        for(j = 0; j < (n-i-1); j++)
            if(edgeList[j].cost > edgeList[j+1].cost){
                swapping(edgeList[j], edgeList[j+1]);
                flag = 1;
            }
    }
}
void kruskal(Tree &tr){
    int ecount, maxEdge = V*(V-1)/2; //ग्राफ में अधिकतम n(n-1)/2 एज हो सकते हैं
    edge edgeList[maxEdge], ed;
    int uloc, vloc;
    VSet VSetArray[V];
    ecount = findEdge(edgeList);
    for(int i = 0; i < V; i++)
        VSetArray[i].addVertex(i); //प्रत्येक सेट में एक तत्व है
    sortEdge(edgeList, ecount); //ग्राफ में ecount संख्या में एज
    int count = 0;
    while(count <= V-1){
        ed = edgeList[count];
        uloc = findVertex(VSetArray, ed.u);
        vloc = findVertex(VSetArray, ed.v);
        if(uloc != vloc){ //चेक करें कि सोर्स और डेस्ट एक ही सेट में हैं या नहीं
            merge(VSetArray[uloc], VSetArray[vloc]);
            tr.addEdge(ed);
        }
        count++;
    }
}
int main(){
    Tree tr;
    kruskal(tr);
    tr.printEdges();
}

आउटपुट

Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15