minimum spanning tree tutorial
यह C ++ ट्यूटोरियल बताता है कि प्राइम और उसके अनुप्रयोगों में एमएसटी को खोजने के लिए प्राइम और क्रुस्कल के एल्गोरिदम के साथ एक न्यूनतम स्पैनिंग ट्री (MST) क्या है:
एक स्पैनिंग ट्री को एक ग्राफ के सबसेट के रूप में परिभाषित किया जा सकता है, जिसमें न्यूनतम संभव किनारों को कवर करने वाले सभी कोने होते हैं और एक चक्र नहीं होता है। स्पानिंग ट्री को डिस्कनेक्ट नहीं किया जा सकता है।
हर जुड़े और अप्रत्यक्ष ग्राफ में कम से कम एक फैले हुए वृक्ष होते हैं। डिस्कनेक्ट किए गए ग्राफ़ में एक फैले हुए पेड़ नहीं है क्योंकि सभी कोने सम्मिलित करना संभव नहीं है।
=> पूर्ण सी ++ ट्यूटोरियल सूची देखने के लिए यहां देखें।
आप क्या सीखेंगे:
सी ++ में स्पैनिंग ट्री
निम्नलिखित जुड़े ग्राफ पर विचार करें।
जैसा कि ऊपर दिखाया गया है, दिए गए जुड़े ग्राफ के लिए 3 कोने हैं, हमारे पास तीन फैले हुए पेड़ हैं। सामान्य तौर पर, यदि N एक ग्राफ़ में नोड्स की संख्या है, तो एक पूर्ण कनेक्टेड ग्राफ़ में अधिकतम N हैएन-2फैले पेड़ों की संख्या। इस प्रकार उपरोक्त ग्राफ N = 3 में, इसलिए, इसके 3 हैं(3-2)= 3 फैले हुए पेड़।
फैले हुए पेड़ के कुछ गुण नीचे सूचीबद्ध हैं:
- एक जुड़े हुए ग्राफ में एक से अधिक फैले हुए पेड़ हो सकते हैं।
- एक ग्राफ में सभी फैले पेड़ों में नोड्स और किनारों की समान संख्या होती है।
- यदि हम फैले हुए पेड़ से एक किनारे को हटा दें, तो यह बन जाएगा न्यूनतम रूप से जुड़ा हुआ और ग्राफ काट दिया जाएगा।
- दूसरी ओर, फैले हुए पेड़ में एक किनारे जोड़ने से यह बन जाएगा अधिकतम रूप से चक्रीय जिससे एक लूप का निर्माण होता है।
- एक फैले हुए पेड़ में एक लूप या एक चक्र नहीं होता है।
न्यूनतम स्पानिंग ट्री (एमएसटी) क्या है
एक न्यूनतम फैले हुए वृक्ष वह है जिसमें एक जुड़े हुए भारित ग्राफ के अन्य सभी फैले हुए पेड़ों के बीच कम से कम वजन होता है। एक ग्राफ के लिए एक से अधिक न्यूनतम फैले हुए पेड़ हो सकते हैं।
दो सबसे लोकप्रिय एल्गोरिदम हैं जिनका उपयोग ग्राफ़ में न्यूनतम फैले पेड़ को खोजने के लिए किया जाता है।
वे सम्मिलित करते हैं:
- Kruskal का एल्गोरिदम
- प्राइम का एल्गोरिथ्म
आइए इन दोनों एल्गोरिदम पर चर्चा करें!
क्रुस्कल का एल्गोरिदम
क्रुसकल का एल्गोरिदम एक कनेक्टेड ग्राफ़ में एमएसटी को खोजने के लिए एक एल्गोरिथ्म है।
क्रुस्लक के एल्गोरिथ्म में ग्राफ G का एक उपसमूह पाया जाता है जैसे:
- इसमें प्रत्येक शीर्ष के साथ एक वृक्ष बनता है।
- इस ग्राफ से बनने वाले सभी फैले पेड़ों के बीच वज़न का योग न्यूनतम है।
क्रुशाल के एल्गोरिथ्म के लिए चरणों का क्रम इस प्रकार दिया गया है:
- सबसे पहले सबसे कम वजन से सभी किनारों को छाँट लें।
- सबसे कम वजन के साथ किनारे लें और इसे फैले हुए पेड़ में जोड़ें। यदि चक्र बना है, तो किनारे को छोड़ दें।
- चरण 1 की तरह किनारों को जोड़ते रहें जब तक कि सभी लंबों को नहीं माना जाता है।
क्रुस्कल के एल्गोरिथ्म के लिए स्यूडोकोड
नीचे दिए गए क्रूसल के एल्गोरिथ्म के लिए छद्म कोड है
अब हमें क्रुसकल के एल्गोरिथ्म का दृष्टांत देखें।
अब हम किनारे को कम से कम वजन के साथ चुनते हैं जो 2-4 है।
अगला, अगला सबसे छोटा किनारा 2-3 चुनें।
फिर हम सबसे छोटे किनारे के साथ अगला किनारा चुनते हैं और यह एक चक्र नहीं बनाता है अर्थात् 0-3
डेस्क इंटरव्यू के सवालों और जवाबों के तकनीकी मदद करें
अगला कदम सबसे छोटा किनारा चुनना है ताकि यह एक चक्र न बने। यह 0-1 है।
जैसा कि हम देख सकते हैं, हमने सभी छोरों को कवर किया है और हमारे यहां न्यूनतम खर्च के साथ एक फैले हुए पेड़ हैं।
अगला, हम C ++ का उपयोग करके क्रुस्कल के एल्गोरिथ्म को लागू करेंगे।
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int[V]; for (int i = 0; i आउटपुट:
क्रुस्ल के एल्गोरिथम के अनुसार न्यूनतम स्पैनिंग ट्री (MST):
बढ़त: वजन
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
ध्यान दें कि हमने कार्यक्रम में उसी उदाहरण के ग्राफ का उपयोग किया है जैसा कि हमने ऊपर कुर्कल के एल्गोरिथ्म के चित्रण में उपयोग किया है। इस कार्यान्वयन में हम दो वैक्टर का उपयोग करते हैं; एक ग्राफ को स्टोर करने के लिए और दूसरा न्यूनतम फैले हुए पेड़ को स्टोर करने के लिए। हम पुनरावर्ती किनारों को कम से कम भार के साथ ढूंढते हैं और उन्हें तब तक एमएसटी वेक्टर में जोड़ते हैं जब तक कि सभी कोने कवर नहीं हो जाते।
प्राइम का एल्गोरिथम
किसी ग्राफ़ के पेड़ पर न्यूनतम फैले हुए को खोजने के लिए प्राइम का एल्गोरिथ्म अभी तक एक अन्य एल्गोरिदम है। क्रुस्ल के एल्गोरिथ्म के विपरीत जो ग्राफ़ किनारों के साथ शुरू होता है, प्राइम का एल्गोरिथ्म एक शीर्ष के साथ शुरू होता है। हम एक शीर्ष के साथ शुरू करते हैं और कम से कम वजन के साथ किनारों को जोड़ते रहते हैं जब तक कि सभी कोने कवर नहीं हो जाते।
प्राइम एलगोरिदम के लिए चरणों का क्रम इस प्रकार है:
- वर्टेक्स शुरू करने के रूप में एक यादृच्छिक शीर्ष चुनें और न्यूनतम फैले हुए पेड़ को इनिशियलाइज़ करें।
- किनारों को खोजें जो अन्य कोने से जुड़ते हैं। न्यूनतम वजन के साथ किनारे का पता लगाएं और इसे फैले हुए पेड़ में जोड़ें।
- चरण 2 को दोहराएं जब तक कि फैले हुए पेड़ प्राप्त न हो जाए।
प्राइम के एल्गोरिथ्म के लिए स्यूडोकोड
अब हमें Prim के एल्गोरिथ्म के लिए एक चित्रण देखते हैं।
इसके लिए, हम उसी उदाहरण ग्राफ का उपयोग कर रहे हैं जिसका उपयोग हमने क्रुस्ल के एल्गोरिथ्म के चित्रण में किया था।
हमें यादृच्छिक शीर्ष के रूप में नोड 2 का चयन करें।
अगला, हम 2. से कम से कम वजन के साथ किनारे का चयन करते हैं। हम किनारे को 2-4 चुनते हैं।
अगला, हम एक और शीर्ष चुनते हैं जो अभी तक फैले पेड़ में नहीं है। हम किनारे को 2-3 चुनते हैं।
अब हम ऊपर के कोने से कम से कम वजन वाले किनारे का चयन करें। हमारे पास बढ़त 3-0 है जिसका वजन सबसे कम है।
अगला, हम शीर्ष 0. से सबसे कम वजन वाले किनारे का चयन करते हैं। यह बढ़त 0-1 है।
उपरोक्त आंकड़े से, हम देखते हैं कि हमने अब ग्राफ में सभी कोने को कवर किया है और न्यूनतम लागत के साथ एक पूर्ण फैले हुए पेड़ को प्राप्त किया है।
अब हम C ++ में प्राइम के एल्गोरिथ्म को लागू करते हैं।
ध्यान दें कि इस कार्यक्रम में भी, हमने उपरोक्त उदाहरण ग्राफ को इनपुट के रूप में उपयोग किया है, ताकि हम चित्र के साथ कार्यक्रम द्वारा दिए गए आउटपुट की तुलना कर सकें।
कार्यक्रम नीचे दिया गया है:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G[V][V] = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex[V]; // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex[0] = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G[x][y]; cout << endl; mst_vertex[y] = true; num_edge++; } return 0; }
आउटपुट:
प्राइम के एल्गोरिथम के अनुसार न्यूनतम स्पैनिंग ट्री:
बढ़त: वजन
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
स्पानिंग ट्री के अनुप्रयोग
न्यूनतम अवधि वृक्षों के कुछ अनुप्रयोग इस प्रकार हैं:
# 1) संचार नेटवर्क सेटअप: जब हम संचार लिंक का उपयोग करके संचार नेटवर्क स्थापित करना चाहते हैं, तो एक एमएसटी का उपयोग करके दो बिंदुओं के बीच संचार लिंक स्थापित करने की लागत निर्धारित की जाती है।
# 2) क्लस्टर विश्लेषण: इसका उपयोग न्यूनतम फैले हुए पेड़ को खोजने और के -1 सबसे महंगे किनारों को हटाने के द्वारा के-क्लस्टरिंग समस्या को हल करने के लिए किया जा सकता है।
# 3) सड़क / रेल नेटवर्क बिछाना: जब हम शहरों के बीच या भीतर विभिन्न सड़क या रेल नेटवर्क बिछाते हैं, तो परियोजना की लागत बहुत महत्वपूर्ण कारक होती है। हम न्यूनतम फैले पेड़ों का उपयोग करके न्यूनतम लागत के साथ सबसे अच्छा रास्ता पा सकते हैं।
# 4) आवास की योजना बनाना: कई घरों को प्रदान की जाने वाली बिजली, पानी, सीवेज आदि जैसी सुविधाएं भी इष्टतम लागत पर होनी चाहिए और यह एक एमएसटी का उपयोग करके किया जाता है।
# 5) ट्रैवलिंग सेल्समैन समस्या का समाधान: हम ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए एक MST का उपयोग कर सकते हैं जिसके लिए कम से कम एक बार प्रत्येक बिंदु पर जाना होगा।
निष्कर्ष
न्यूनतम फैले पेड़ ग्राफ जी का सबसेट है और इस सबसेट में ग्राफ के सभी कोने हैं और कोने जोड़ने वाले किनारों की कुल लागत न्यूनतम है।
हमने ग्राफ़ से न्यूनतम फैले हुए वृक्ष को खोजने के लिए दो एल्गोरिदम यानी क्रुस्सल और प्राइम्स पर चर्चा की। इस ट्यूटोरियल में यहाँ फैले हुए पेड़ के अनुप्रयोगों को भी समझाया गया था।
=> यहां सर्वश्रेष्ठ C ++ प्रशिक्षण ट्यूटोरियल देखें।
अनुशंसित पाठ
- उदाहरणों के साथ जावा परावर्तन ट्यूटोरियल
- बी ट्री और बी + ट्री डेटा संरचना C ++ में
- उदाहरणों के साथ पायथन डेटटाइम ट्यूटोरियल
- Bugzilla Tutorial: दोष प्रबंधन उपकरण हाथों पर ट्यूटोरियल
- सी + + में बाइनरी ट्री डेटा संरचना
- 20+ MongoDB शुरुआती के लिए ट्यूटोरियल: नि: शुल्क MongoDB कोर्स
- उदाहरण के साथ MongoDB शेयरिंग ट्यूटोरियल
- MongoDB डेटाबेस ट्यूटोरियल बनाएँ