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

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

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

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

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

इनपुट और आउटपुट

इनपुट: एडजेसेंसी मैट्रिक्स  आउटपुट: 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 
  create set for each vertices in graph g 
  for each set of vertex u do 
    add u in the vertexSet[u] 
  done 
  sort the edge list. 
  count := 0 
  while count <= V – 1 do 
    //as tree must have V – 1 edges 
    ed := edgeList[count] //take an edge from edge list 
    if the starting vertex and ending vertex of ed are in same set then 
      merge vertexSet[start] and vertexSet[end] 
      add the ed into tree t 
    count := count +1 
  done 
End

उदाहरण

#include<iostream> #define V 7 #define INF 999 using namespace std; //Cost matrix of the graph 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]; //as a tree has vertex-1 edges public: Tree() { n = 0; } void addEdge(edge e) { edges[n] = e; //add edge e into the tree n++; } void printEdges() { //print edge, cost and total cost int tCost = 0; for(int i = 0; i= 0) set1.addVertex(set2.deleteVertex()); } int findVertex(VSet *vertSetArr, int vert) { //find the vertex in different vertex sets for(int i = 0; i edgeList[j+1].cost) { swapping(edgeList[j], edgeList[j+1]); flag = 1; } } } void kruskal(Tree &tr) { int ecount, maxEdge = V*(V-1)/2; //max n(n-1)/2 edges can have in a graph edge edgeList[maxEdge], ed; int uloc, vloc; VSet VSetArray[V]; ecount = findEdge(edgeList); for(int i = 0; i < V; i++) VSetArray[i].addVertex(i); //each set contains one element sortEdge(edgeList, ecount); //ecount number of edges in the graph int count = 0; while(count <= V-1) { ed = edgeList[count]; uloc = findVertex(VSetArray, ed.u); vloc = findVertex(VSetArray, ed.v); if(uloc != vloc) { //check whether source abd dest is in same set or not 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