क्रुस्कल का एल्गोरिदम

इस ट्यूटोरियल में, आप सीखेंगे कि क्रुस्कल का अल्गोरिद्म कैसे बने। इसके अलावा, आप C, C ++, जावा और पायथन में क्रुस्काल के एल्गोरिथ्म के काम करने के उदाहरण पाएंगे।

क्रुस्कल का एल्गोरिथ्म एक न्यूनतम फैले हुए पेड़ का एल्गोरिथ्म है जो एक ग्राफ को इनपुट के रूप में लेता है और उस ग्राफ के किनारों का सबसेट ढूंढता है जो

• एक पेड़ बनाएं जिसमें हर शिखर शामिल हो
• उन सभी पेड़ों के बीच न्यूनतम वजन होता है जो ग्राफ से बन सकते हैं

क्रुस्ल का एल्गोरिदम कैसे काम करता है

यह लालची एल्गोरिदम नामक एल्गोरिदम के एक वर्ग के अंतर्गत आता है जो वैश्विक इष्टतम खोजने की उम्मीद में स्थानीय इष्टतम को ढूंढता है।

हम किनारों से सबसे कम वजन के साथ शुरू करते हैं और अपने लक्ष्य तक पहुंचने तक किनारों को जोड़ते रहते हैं।

क्रुशाल के एल्गोरिथ्म को लागू करने के चरण इस प्रकार हैं:

1. कम वजन से लेकर उच्च तक सभी किनारों को क्रमबद्ध करें
2. सबसे कम वजन के साथ किनारे लें और इसे फैले हुए पेड़ में जोड़ें। यदि किनारे को जोड़कर एक चक्र बनाया गया है, तो इस किनारे को अस्वीकार कर दें।
3. किनारों को तब तक जोड़ते रहें जब तक हम सभी कोने तक न पहुँच जाएँ।

क्रुस्कल के एल्गोरिथ्म का उदाहरण

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

क्रुसकल एलगोरिदम स्यूडोकोड

कोई न्यूनतम फैले हुए पेड़ का एल्गोरिथ्म यह जांचने के इर्द-गिर्द घूमता है कि क्या किनारे लगाने से लूप बनता है या नहीं।

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

 KRUSKAL(G): A = ∅ For each vertex v ∈ G.V: MAKE-SET(v) For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v): if FIND-SET(u) ≠ FIND-SET(v): A = A ∪ ((u, v)) UNION(u, v) return A

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

 # Kruskal's algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices self.graph = () def add_edge(self, u, v, w): self.graph.append((u, v, w)) # Search function def find(self, parent, i): if parent(i) == i: return i return self.find(parent, parent(i)) def apply_union(self, parent, rank, x, y): xroot = self.find(parent, x) yroot = self.find(parent, y) if rank(xroot) rank(yroot): parent(yroot) = xroot else: parent(yroot) = xroot rank(xroot) += 1 # Applying Kruskal algorithm def kruskal_algo(self): result = () i, e = 0, 0 self.graph = sorted(self.graph, key=lambda item: item(2)) parent = () rank = () for node in range(self.V): parent.append(node) rank.append(0) while e < self.V - 1: u, v, w = self.graph(i) i = i + 1 x = self.find(parent, u) y = self.find(parent, v) if x != y: e = e + 1 result.append((u, v, w)) self.apply_union(parent, rank, x, y) for u, v, weight in result: print("%d - %d: %d" % (u, v, weight)) g = Graph(6) g.add_edge(0, 1, 4) g.add_edge(0, 2, 4) g.add_edge(1, 2, 2) g.add_edge(1, 0, 4) g.add_edge(2, 0, 4) g.add_edge(2, 1, 2) g.add_edge(2, 3, 3) g.add_edge(2, 5, 2) g.add_edge(2, 4, 4) g.add_edge(3, 2, 3) g.add_edge(3, 4, 3) g.add_edge(4, 2, 4) g.add_edge(4, 3, 3) g.add_edge(5, 2, 2) g.add_edge(5, 4, 3) g.kruskal_algo()

 // Kruskal's algorithm in Java import java.util.*; class Graph ( class Edge implements Comparable ( int src, dest, weight; public int compareTo(Edge compareEdge) ( return this.weight - compareEdge.weight; ) ); // Union class subset ( int parent, rank; ); int vertices, edges; Edge edge(); // Graph creation Graph(int v, int e) ( vertices = v; edges = e; edge = new Edge(edges); for (int i = 0; i < e; ++i) edge(i) = new Edge(); ) int find(subset subsets(), int i) ( if (subsets(i).parent != i) subsets(i).parent = find(subsets, subsets(i).parent); return subsets(i).parent; ) void Union(subset subsets(), int x, int y) ( int xroot = find(subsets, x); int yroot = find(subsets, y); if (subsets(xroot).rank subsets(yroot).rank) subsets(yroot).parent = xroot; else ( subsets(yroot).parent = xroot; subsets(xroot).rank++; ) ) // Applying Krushkal Algorithm void KruskalAlgo() ( Edge result() = new Edge(vertices); int e = 0; int i = 0; for (i = 0; i < vertices; ++i) result(i) = new Edge(); // Sorting the edges Arrays.sort(edge); subset subsets() = new subset(vertices); for (i = 0; i < vertices; ++i) subsets(i) = new subset(); for (int v = 0; v < vertices; ++v) ( subsets(v).parent = v; subsets(v).rank = 0; ) i = 0; while (e < vertices - 1) ( Edge next_edge = new Edge(); next_edge = 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); ) ) for (i = 0; i < e; ++i) System.out.println(result(i).src + " - " + result(i).dest + ": " + result(i).weight); ) public static void main(String() args) ( int vertices = 6; // Number of vertices int edges = 8; // Number of edges Graph G = new Graph(vertices, edges); G.edge(0).src = 0; G.edge(0).dest = 1; G.edge(0).weight = 4; G.edge(1).src = 0; G.edge(1).dest = 2; G.edge(1).weight = 4; G.edge(2).src = 1; G.edge(2).dest = 2; G.edge(2).weight = 2; G.edge(3).src = 2; G.edge(3).dest = 3; G.edge(3).weight = 3; G.edge(4).src = 2; G.edge(4).dest = 5; G.edge(4).weight = 2; G.edge(5).src = 2; G.edge(5).dest = 4; G.edge(5).weight = 4; G.edge(6).src = 3; G.edge(6).dest = 4; G.edge(6).weight = 3; G.edge(7).src = 5; G.edge(7).dest = 4; G.edge(7).weight = 3; G.KruskalAlgo(); ) )

 // Kruskal's algorithm in C #include #define MAX 30 typedef struct edge ( int u, v, w; ) edge; typedef struct edge_list ( edge data(MAX); int n; ) edge_list; edge_list elist; int Graph(MAX)(MAX), n; edge_list spanlist; void kruskalAlgo(); int find(int belongs(), int vertexno); void applyUnion(int belongs(), int c1, int c2); void sort(); void print(); // Applying Krushkal Algo void kruskalAlgo() ( int belongs(MAX), i, j, cno1, cno2; elist.n = 0; for (i = 1; i < n; i++) for (j = 0; j < i; j++) ( if (Graph(i)(j) != 0) ( elist.data(elist.n).u = i; elist.data(elist.n).v = j; elist.data(elist.n).w = Graph(i)(j); elist.n++; ) ) sort(); for (i = 0; i < n; i++) belongs(i) = i; spanlist.n = 0; for (i = 0; i < elist.n; i++) ( cno1 = find(belongs, elist.data(i).u); cno2 = find(belongs, elist.data(i).v); if (cno1 != cno2) ( spanlist.data(spanlist.n) = elist.data(i); spanlist.n = spanlist.n + 1; applyUnion(belongs, cno1, cno2); ) ) ) int find(int belongs(), int vertexno) ( return (belongs(vertexno)); ) void applyUnion(int belongs(), int c1, int c2) ( int i; for (i = 0; i < n; i++) if (belongs(i) == c2) belongs(i) = c1; ) // Sorting algo void sort() ( int i, j; edge temp; for (i = 1; i < elist.n; i++) for (j = 0; j elist.data(j + 1).w) ( temp = elist.data(j); elist.data(j) = elist.data(j + 1); elist.data(j + 1) = temp; ) ) // Printing the result void print() ( int i, cost = 0; for (i = 0; i < spanlist.n; i++) ( printf("%d - %d : %d", spanlist.data(i).u, spanlist.data(i).v, spanlist.data(i).w); cost = cost + spanlist.data(i).w; ) printf("Spanning tree cost: %d", cost); ) int main() ( int i, j, total_cost; n = 6; Graph(0)(0) = 0; Graph(0)(1) = 4; Graph(0)(2) = 4; Graph(0)(3) = 0; Graph(0)(4) = 0; Graph(0)(5) = 0; Graph(0)(6) = 0; Graph(1)(0) = 4; Graph(1)(1) = 0; Graph(1)(2) = 2; Graph(1)(3) = 0; Graph(1)(4) = 0; Graph(1)(5) = 0; Graph(1)(6) = 0; Graph(2)(0) = 4; Graph(2)(1) = 2; Graph(2)(2) = 0; Graph(2)(3) = 3; Graph(2)(4) = 4; Graph(2)(5) = 0; Graph(2)(6) = 0; Graph(3)(0) = 0; Graph(3)(1) = 0; Graph(3)(2) = 3; Graph(3)(3) = 0; Graph(3)(4) = 3; Graph(3)(5) = 0; Graph(3)(6) = 0; Graph(4)(0) = 0; Graph(4)(1) = 0; Graph(4)(2) = 4; Graph(4)(3) = 3; Graph(4)(4) = 0; Graph(4)(5) = 0; Graph(4)(6) = 0; Graph(5)(0) = 0; Graph(5)(1) = 0; Graph(5)(2) = 2; Graph(5)(3) = 0; Graph(5)(4) = 3; Graph(5)(5) = 0; Graph(5)(6) = 0; kruskalAlgo(); print(); )

 // Kruskal's algorithm in C++ #include #include #include using namespace std; #define edge pair class Graph ( private: vector 
 G; // graph vector 
 T; // mst int *parent; int V; // number of vertices/nodes in graph public: Graph(int V); void AddWeightedEdge(int u, int v, int w); int find_set(int i); void union_set(int u, int v); void kruskal(); void print(); ); Graph::Graph(int V) ( parent = new int(V); //i 0 1 2 3 4 5 //parent(i) 0 1 2 3 4 5 for (int i = 0; i < V; i++) parent(i) = i; G.clear(); T.clear(); ) void Graph::AddWeightedEdge(int u, int v, int w) ( G.push_back(make_pair(w, edge(u, v))); ) int Graph::find_set(int i) ( // If i is the parent of itself if (i == parent(i)) return i; else // Else if i is not the parent of itself // Then i is not the representative of his set, // so we recursively call Find on its parent return find_set(parent(i)); ) void Graph::union_set(int u, int v) ( parent(u) = parent(v); ) void Graph::kruskal() ( int i, uRep, vRep; sort(G.begin(), G.end()); // increasing weight for (i = 0; i < G.size(); i++) ( uRep = find_set(G(i).second.first); vRep = find_set(G(i).second.second); if (uRep != vRep) ( T.push_back(G(i)); // add to tree union_set(uRep, vRep); ) ) ) void Graph::print() ( cout << "Edge :" << " Weight" << endl; for (int i = 0; i < T.size(); i++) ( cout << T(i).second.first << " - " << T(i).second.second << " : " << T(i).first; cout << endl; ) ) int main() ( Graph g(6); g.AddWeightedEdge(0, 1, 4); g.AddWeightedEdge(0, 2, 4); g.AddWeightedEdge(1, 2, 2); g.AddWeightedEdge(1, 0, 4); g.AddWeightedEdge(2, 0, 4); g.AddWeightedEdge(2, 1, 2); g.AddWeightedEdge(2, 3, 3); g.AddWeightedEdge(2, 5, 2); g.AddWeightedEdge(2, 4, 4); g.AddWeightedEdge(3, 2, 3); g.AddWeightedEdge(3, 4, 3); g.AddWeightedEdge(4, 2, 4); g.AddWeightedEdge(4, 3, 3); g.AddWeightedEdge(5, 2, 2); g.AddWeightedEdge(5, 4, 3); g.kruskal(); g.print(); return 0; )  

क्रुस्कल बनाम प्राइम का एल्गोरिथम

प्राइम का एल्गोरिथ्म एक और लोकप्रिय न्यूनतम फैले हुए पेड़ का एल्गोरिथ्म है जो एक ग्राफ़ के एमएसटी को खोजने के लिए एक अलग तर्क का उपयोग करता है। एक किनारे से शुरू करने के बजाय, प्राइम का एल्गोरिथ्म एक शीर्ष से शुरू होता है और सबसे कम वजन वाले किनारों को जोड़ता रहता है जो पेड़ में नहीं होते हैं, जब तक कि सभी कोने कवर नहीं किए जाते हैं।

क्रुसकल की एल्गोरिथ्म जटिलता

क्रुस्कल के एल्गोरिथ्म की समय जटिलता है: ओ (ई लॉग ई)।

Kruskal के एल्गोरिथ्म अनुप्रयोग

• विद्युत तारों को लेआउट करने के लिए
• कंप्यूटर नेटवर्क (LAN कनेक्शन) में