java graph tutorial how implement graph data structure
यह व्यापक जावा ग्राफ ट्यूटोरियल विस्तार से ग्राफ डेटा संरचना को बताता है। इसमें जावा में क्रिएट, इम्प्लीमेंट, रिप्रेजेंटेटिव्स और ट्रावर्स ग्राफ्स शामिल हैं।
एक ग्राफ डेटा संरचना मुख्य रूप से विभिन्न बिंदुओं को जोड़ने वाले नेटवर्क का प्रतिनिधित्व करती है। इन बिंदुओं को कोने के रूप में कहा जाता है और इन कोने को जोड़ने वाले लिंक को 'एज' कहा जाता है। तो एक ग्राफ जी को वर्टिकल V के एक सेट के रूप में परिभाषित किया गया है और किनारों ई जो इन कोने को जोड़ता है।
कंप्यूटर नेटवर्क, सोशल नेटवर्क आदि जैसे विभिन्न नेटवर्कों का प्रतिनिधित्व करने के लिए ग्राफ का उपयोग किया जाता है। सॉफ्टवेयर या आर्किटेक्चर में विभिन्न निर्भरता का प्रतिनिधित्व करने के लिए भी उनका उपयोग किया जा सकता है। ये निर्भरता ग्राफ सॉफ्टवेयर के विश्लेषण में बहुत उपयोगी होते हैं और कई बार इसे डीबग भी करते हैं।
=> यहाँ सभी जावा ट्यूटोरियल की जाँच करें।
आप क्या सीखेंगे:
- जावा ग्राफ डेटा संरचना
- एक ग्राफ बनाने के लिए कैसे?
- जावा में ग्राफ कार्यान्वयन
- जावा ग्राफ लाइब्रेरी
- निष्कर्ष
जावा ग्राफ डेटा संरचना
नीचे दिए गए एक ग्राफ में पांच कोने {ए, बी, सी, डी, ई} और {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}} द्वारा दिए गए किनारे हैं। जैसा कि किनारों पर कोई निर्देश नहीं है, इस ग्राफ़ को 'अप्रत्यक्ष ग्राफ़' के रूप में जाना जाता है।
ऊपर दिखाए गए अप्रत्यक्ष ग्राफ के अलावा, जावा में ग्राफ के कई संस्करण हैं।
आइए इन रूपों पर विस्तार से चर्चा करें।
ग्राफ के विभिन्न प्रकार
निम्नलिखित ग्राफ के कुछ प्रकार हैं।
(1) निर्देशित ग्राफ
एक निर्देशित ग्राफ या डिग्राफ एक ग्राफ डेटा संरचना है जिसमें किनारों की एक विशिष्ट दिशा होती है। वे एक शीर्ष से उत्पन्न होते हैं और दूसरे शीर्ष में परिणत होते हैं।
निम्नलिखित चित्र निर्देशित ग्राफ का उदाहरण दिखाता है।
ऊपर दिए गए आरेख में, वर्टीकल ए से वर्टेक्स बी तक एक किनारे है। लेकिन ध्यान दें कि ए से बी बी से ए के समान नहीं है जैसे कि अप्रत्यक्ष ग्राफ़ में जब तक बी से ए तक निर्दिष्ट कोई बढ़त नहीं होती है।
एक निर्देशित ग्राफ चक्रीय है यदि कम से कम एक पथ है जिसका अपना पहला और अंतिम शीर्ष समान है। उपर्युक्त आरेख में, एक पथ A-> B-> C-> D-> E-> एक निर्देशित चक्र या साइक्लिक ग्राफ बनाता है।
इसके विपरीत, एक निर्देशित चक्रीय ग्राफ एक ग्राफ होता है जिसमें कोई निर्देशित चक्र नहीं होता है यानी ऐसा कोई रास्ता नहीं होता है जो एक चक्र का निर्माण करता हो।
# 2) भारित ग्राफ़
एक भारित ग्राफ में, एक वजनग्राफ के प्रत्येक किनारे के साथ जुड़ा हुआ है। वजन सामान्य रूप से दो कोने के बीच की दूरी को इंगित करता है। निम्न आरेख भारित ग्राफ़ दिखाता है। जैसा कि कोई निर्देश नहीं दिखाया गया है यह अप्रत्यक्ष ग्राफ है।
ध्यान दें कि एक भारित ग्राफ को निर्देशित या अप्रत्यक्ष किया जा सकता है।
एक ग्राफ बनाने के लिए कैसे?
जावा, ग्राफ डेटा संरचना का पूर्ण कार्यान्वयन प्रदान नहीं करता है। हालाँकि, हम जावा में कलेक्शंस का उपयोग करके ग्राफ को प्रोग्रामेटिक रूप से दर्शा सकते हैं। हम वैक्टर जैसे गतिशील सरणियों का उपयोग करके एक ग्राफ भी लागू कर सकते हैं।
आमतौर पर, हम HashMap संग्रह का उपयोग करके जावा में रेखांकन लागू करते हैं। हैशपॉप तत्व कुंजी-मूल्य जोड़े के रूप में हैं। हम एक HashMap में ग्राफ आसन्न सूची का प्रतिनिधित्व कर सकते हैं।
एक ग्राफ बनाने का सबसे आम तरीका आसन्न मैट्रिक्स या आसन्न सूची जैसे रेखांकन के प्रतिनिधित्व में से एक का उपयोग करके है। हम आगे इन अभ्यावेदन पर चर्चा करेंगे और फिर आसन्न सूची का उपयोग करके जावा में ग्राफ को लागू करेंगे जिसके लिए हम ArrayList का उपयोग करेंगे।
जावा में ग्राफ का प्रतिनिधित्व
ग्राफ़ प्रतिनिधित्व का अर्थ है वह दृष्टिकोण या तकनीक जिसका उपयोग करके कंप्यूटर की मेमोरी में ग्राफ़ डेटा संग्रहीत किया जाता है।
हम नीचे दिखाए गए अनुसार रेखांकन के दो मुख्य अभ्यावेदन हैं।
सहखंडज मैट्रिक्स
निकटता मैट्रिक्स रेखांकन का एक रेखीय प्रतिनिधित्व है। यह मैट्रिक्स ग्राफ के कोने और किनारों के मानचित्रण को संग्रहीत करता है। आसन्न मैट्रिक्स में, ग्राफ के कोने पंक्तियों और स्तंभों का प्रतिनिधित्व करते हैं। इसका मतलब है कि यदि ग्राफ़ में एन कोने हैं, तो आसन्न मैट्रिक्स का आकार NxN होगा।
यदि V ग्राफ के वर्टिकल का एक सेट है तो M को इंटरसेक्शन करेंइ जसन्निकटन सूची में = 1 का अर्थ है कि किनारे i और j के बीच एक धार विद्यमान है।
इस अवधारणा को स्पष्ट रूप से समझने के लिए, आइए हम एक अप्रत्यक्ष ग्राफ़ के लिए एक आसन्न मैट्रिक्स तैयार करें।
जैसा कि ऊपर के आरेख से देखा जाता है, हम देखते हैं कि शीर्ष A के लिए, चौराहों AB और AE को 1 पर सेट किया गया है क्योंकि A से B और A से E तक एक धार है। इसी तरह प्रतिच्छेदन BA 1 पर सेट है, क्योंकि यह एक अप्रत्यक्ष है ग्राफ और एबी = बीए। इसी तरह, हमने अन्य सभी चौराहों को निर्धारित किया है जिनके लिए 1 से एक छोर है।
यदि ग्राफ निर्देशित किया जाता है, तो प्रतिच्छेदन एमइ ज1 से केवल तभी सेट किया जाएगा जब वीआई से वीजे तक निर्देशित एक स्पष्ट बढ़त होगी।
यह निम्नलिखित दृष्टांत में दिखाया गया है।
जैसा कि हम ऊपर दिए गए आरेख से देख सकते हैं, ए से बी तक एक छोर है। इसलिए चौराहे AB को 1 पर सेट किया गया है, लेकिन चौराहे BA को 0 पर सेट किया गया है। ऐसा इसलिए है क्योंकि B से A तक निर्देशित कोई धार नहीं है।
कोने पर विचार करें ई और डी। हम देखते हैं कि ई से डी तक के किनारों के साथ-साथ डी से ई भी हैं। इसलिए हमने आसन्न मैट्रिक्स में इन दोनों चौराहों को 1 पर सेट किया है।
अब हम भारित रेखांकन पर चलते हैं। जैसा कि हम भारित ग्राफ के लिए जानते हैं, एक पूर्णांक जिसे वजन के रूप में भी जाना जाता है, प्रत्येक किनारे के साथ जुड़ा हुआ है। हम इस वज़न को उस किनारे के लिए आसन्न मैट्रिक्स में दर्शाते हैं जो मौजूद है। यह वजन तब निर्दिष्ट किया जाता है जब to 1 ’के बजाय एक शीर्ष से दूसरे तक एक किनारे होता है।
यह प्रतिनिधित्व नीचे दिखाया गया है।
आसन्न सूची
एक आसन्न मैट्रिक्स के रूप में एक ग्राफ का प्रतिनिधित्व करने के बजाय जो प्रकृति में अनुक्रमिक है, हम लिंक किए गए प्रतिनिधित्व का भी उपयोग कर सकते हैं। यह जुड़ा हुआ प्रतिनिधित्व आसन्न सूची के रूप में जाना जाता है। एक आसन्न सूची एक लिंक की गई सूची के अलावा कुछ भी नहीं है और सूची में प्रत्येक नोड एक शीर्ष का प्रतिनिधित्व करता है।
दो सिरों के बीच एक किनारे की उपस्थिति एक सूचक द्वारा पहले शीर्ष से दूसरे तक निरूपित की जाती है। यह आसन्न सूची ग्राफ में प्रत्येक शीर्ष के लिए बनी हुई है।
जब हमने किसी विशेष नोड के लिए सभी आसन्न नोड्स का पता लगाया है, तो हम NULL को आसन्न सूची के अंतिम नोड के अगले पॉइंटर क्षेत्र में संग्रहीत करते हैं।
अब हम उपरोक्त ग्राफ़ का उपयोग करेंगे जिसका उपयोग हमने आसन्न सूची को प्रदर्शित करने के लिए आसन्न मैट्रिक्स का प्रतिनिधित्व करने के लिए किया था।
उपरोक्त आंकड़ा अप्रत्यक्ष ग्राफ के लिए आसन्न सूची दिखाता है। हम देखते हैं कि प्रत्येक शीर्ष या नोड की अपनी आसन्न सूची है।
SQL सर्वर 2012 साक्षात्कार अनुभवी के लिए सवाल और जवाब
अप्रत्यक्ष ग्राफ के मामले में, आसन्न सूचियों की कुल लंबाई आमतौर पर किनारों की संख्या से दोगुनी होती है। उपरोक्त ग्राफ में, किनारों की कुल संख्या 6 है और सभी आसन्न सूची की लंबाई का कुल या योग 12 है।
अब निर्देशित ग्राफ के लिए एक आसन्न सूची तैयार करते हैं।
जैसा कि उपरोक्त आकृति से देखा गया है, निर्देशित ग्राफ में ग्राफ की आसन्न सूचियों की कुल लंबाई ग्राफ में किनारों की संख्या के बराबर है। उपरोक्त ग्राफ में, इस ग्राफ = 9 के लिए समीपवर्ती सूचियों की लंबाई 9 किनारों और योग है।
अब हम निम्नलिखित भारित निर्देशित ग्राफ पर विचार करते हैं। ध्यान दें कि भारित ग्राफ के प्रत्येक किनारे का वजन इसके साथ जुड़ा हुआ है। इसलिए जब हम आसन्न सूची के साथ इस ग्राफ का प्रतिनिधित्व करते हैं, तो हमें प्रत्येक सूची नोड में एक नया फ़ील्ड जोड़ना होगा जो किनारे के वजन को दर्शाएगा।
भारित ग्राफ के लिए आसन्न सूची नीचे दी गई है।
उपरोक्त आरेख भारित ग्राफ़ और इसकी आसन्न सूची दिखाता है। ध्यान दें कि आसन्न सूची में एक नया स्थान है जो प्रत्येक नोड के वजन को दर्शाता है।
जावा में ग्राफ कार्यान्वयन
निम्नलिखित कार्यक्रम जावा में एक ग्राफ के कार्यान्वयन को दर्शाता है। यहां हमने ग्राफ का प्रतिनिधित्व करने के लिए आसन्न सूची का उपयोग किया है।
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i आउटपुट:
ग्राफ ट्रैवर्सल जावा
किसी भी डेटा की उपस्थिति के लिए खोज जैसी कोई सार्थक कार्रवाई करने के लिए, हमें ग्राफ़ को इस तरह से आगे बढ़ाना होगा कि प्रत्येक शीर्ष और ग्राफ़ के किनारे को कम से कम एक बार देखा जाए। यह ग्राफ़ एल्गोरिदम का उपयोग करके किया जाता है जो कुछ भी नहीं है लेकिन निर्देशों का एक सेट है जो हमें ग्राफ को आगे बढ़ाने में मदद करता है।
जावा में ग्राफ को पार करने के लिए दो एल्गोरिदम समर्थित हैं ।
- गहराई-पहला ट्रैवर्सल
- चौड़ाई-पहला ट्रैवर्सल
गहराई-पहला ट्रैवर्सल
गहराई-पहली खोज (डीएफएस) एक तकनीक है जिसका उपयोग किसी पेड़ या ग्राफ को पार करने के लिए किया जाता है। डीएफएस तकनीक एक रूट नोड के साथ शुरू होती है और फिर ग्राफ में गहराई तक जाकर रूट नोड के आसन्न नोड्स का पता लगाती है। डीएफएस तकनीक में, नोड्स को गहराई से वार किया जाता है, जब तक कि अधिक बच्चों का पता लगाने के लिए न हो।
एक बार जब हम लीफ नोड (कोई और अधिक बच्चे नोड्स) तक नहीं पहुंचते हैं, डीएफएस पीछे हट जाता है और अन्य नोड्स के साथ शुरू होता है और एक समान तरीके से ट्रैवर्सल को बाहर करता है। DFS तकनीक उन ट्रैड डेटा संरचना का उपयोग करती है, जो ट्रैवर्स किए जा रहे नोड्स को स्टोर करने के लिए हैं।
निम्नलिखित DFS तकनीक के लिए एल्गोरिथ्म है।
कलन विधि
चरण 1: रूट नोड से शुरू करें और इसे स्टैक में डालें
चरण 2: स्टैक से आइटम को पॉप करें और Pop विज़िट की गई सूची में डालें
चरण 3: ’विज़िट किए गए’ (या विज़िट की गई सूची) के रूप में चिह्नित नोड के लिए, इस नोड के आसन्न नोड्स जोड़ें जो अभी तक चिह्नित नहीं हैं, स्टैक पर।
चरण 4: चरण 2 और 3 को तब तक दोहराएं जब तक कि स्टैक खाली न हो जाए।
डीएफएस तकनीक का चित्रण
अब हम ग्राफ़ के उचित उदाहरण का उपयोग करके डीएफएस तकनीक का वर्णन करेंगे।
नीचे दिया गया एक उदाहरण ग्राफ है। हम स्टोर किए गए नोड्स और स्टोर की गई सूची को स्टोर करने के लिए स्टैक बनाए रखते हैं।
हम शुरू करने के लिए ए के साथ शुरू करेंगे, इसे विज़िट के रूप में चिह्नित करेंगे, और इसे विज़िट की गई सूची में जोड़ देंगे। फिर हम ए के सभी आसन्न नोड्स पर विचार करेंगे और इन नोड्स को नीचे दिखाए गए अनुसार स्टैक पर धकेलेंगे।
अगला, हम स्टैक यानी बी से एक नोड पॉप करते हैं और इसे विज़िट के रूप में चिह्नित करते हैं। फिर हम इसे 'विज़िट की' सूची में जोड़ते हैं। यह नीचे दर्शाया गया है।
अब हम बी के आसन्न नोड्स पर विचार करते हैं जो ए और सी हैं। इनमें से ए पहले से ही दौरा किया गया है। इसलिए हम इसकी अनदेखी करते हैं। अगला, हम स्टैक से सी पॉप करते हैं। मार्क सी के रूप में दौरा किया। सी यानी ई के आसन्न नोड को स्टैक में जोड़ा जाता है।
अगला, हम अगले नोड ई को स्टैक से पॉप करते हैं और इसे विज़िट के रूप में चिह्नित करते हैं। नोड ई का निकटवर्ती नोड C है जो पहले से ही देखा गया है। इसलिए हम इसकी अनदेखी करते हैं।
अब केवल नोड डी स्टैक में रहता है। इसलिए हम इसे चिह्नित के रूप में देखते हैं। इसका आसन्न नोड ए है जो पहले से ही दौरा किया गया है। इसलिए हम इसे स्टैक में नहीं जोड़ते हैं।
इस बिंदु पर स्टैक खाली है। इसका मतलब है कि हमने दिए गए ग्राफ के लिए गहराई-पहला ट्रैवर्सल पूरा कर लिया है।
दौरा की गई सूची गहराई-पहली तकनीक का उपयोग करते हुए ट्रैवर्सल का अंतिम अनुक्रम देती है। उपरोक्त ग्राफ के लिए अंतिम DFS अनुक्रम A-> B-> C-> E-> D है।
डीएफएस कार्यान्वयन
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list(); // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i आउटपुट:
डीएफएस के अनुप्रयोग
# 1) एक ग्राफ में एक चक्र का पता लगाएं: डीएफएस एक ग्राफ में एक चक्र का पता लगाने की सुविधा देता है जब हम एक किनारे पर पीछे कर सकते हैं।
# 2) पाथफाइंगिंग: जैसा कि हम पहले ही डीएफएस चित्रण में देख चुके हैं, किसी भी दो कोने को देखते हुए हम इन दो कोने के बीच का रास्ता पा सकते हैं।
# 3) न्यूनतम फैले हुए पेड़ और सबसे छोटा रास्ता: यदि हम गैर-भारित ग्राफ पर डीएफएस तकनीक चलाते हैं, तो यह हमें न्यूनतम फैले हुए पेड़ और छोटे पथ देता है।
# 4) सामयिक छँटाई: सामयिक छँटाई का उपयोग तब किया जाता है जब हमें नौकरियों को शेड्यूल करना होता है। हमारी विभिन्न नौकरियों में निर्भरता है। हम लिंकर्स, इंस्ट्रक्शन शेड्यूलर्स, डेटा सीरियललाइज़ेशन आदि के बीच निर्भरता को हल करने के लिए टोपोलॉजिकल सॉर्टिंग का भी उपयोग कर सकते हैं।
चौड़ाई-पहला ट्रैवर्सल
चौड़ाई-प्रथम (BFS) तकनीक ग्राफ के नोड्स को संग्रहीत करने के लिए एक कतार का उपयोग करती है। डीएफएस तकनीक के विपरीत, बीएफएस में हम ग्राफ चौड़ाई के अनुसार पार करते हैं। इसका मतलब है कि हम ग्राफ के स्तर को पार कर गए हैं। जब हम एक स्तर पर सभी कोने या नोड्स का पता लगाते हैं तो हम अगले स्तर पर आगे बढ़ते हैं।
नीचे दिए गए चौड़ाई-प्रथम ट्रैवर्सल तकनीक के लिए एक एल्गोरिदम है ।
कलन विधि
बीएफएस तकनीक के लिए एल्गोरिदम देखें।
एक ग्राफ G को देखते हुए जिसके लिए हमें BFS तकनीक का प्रदर्शन करना होगा।
- चरण 1: रूट नोड से शुरू करें और इसे कतार में डालें।
- चरण 2: ग्राफ़ में सभी नोड्स के लिए चरण 3 और 4 दोहराएं।
- चरण 3: रूट नोड को कतार से निकालें, और इसे विज़िट की गई सूची में जोड़ें।
- चरण 4: अब रूट नोड के सभी आसन्न नोड्स को कतार में जोड़ें और प्रत्येक नोड के लिए चरण 2 से 4 दोहराएं।
- चरण 6: बाहर जाएं
बीएफएस का चित्रण
आइए नीचे दिखाए गए उदाहरण ग्राफ का उपयोग करके BFS तकनीक का वर्णन करें। ध्यान दें कि हमने 'विज़िट' नाम की एक सूची और एक कतार बनाए रखी है। हम उसी ग्राफ का उपयोग करते हैं जो हमने डीएफएस उदाहरण में स्पष्टता प्रयोजनों के लिए उपयोग किया था।
सबसे पहले, हम रूट यानि नोड ए से शुरू करते हैं और इसे विज़िट की गई सूची में जोड़ते हैं। नोड ए के सभी आसन्न नोड्स यानी बी, सी और डी को कतार में जोड़ा जाता है।
अगला, हम नोड बी को कतार से हटा देते हैं। हम इसे विज़िट की गई सूची में जोड़ते हैं और इसे विज़िट के रूप में चिह्नित करते हैं। अगला, हम कतार में B के समीपवर्ती नोड्स का पता लगाते हैं (C पहले से कतार में है)। एक अन्य आसन्न नोड ए पहले से ही दौरा किया गया है इसलिए हम इसे अनदेखा करते हैं।
अगला, हम नोड सी को कतार से हटाते हैं और इसे विज़िट के रूप में चिह्नित करते हैं। हम सी को विज़िट की गई सूची में जोड़ते हैं और इसके आसन्न नोड ई को कतार में जोड़ा जाता है।
इसके बाद, हम D को कतार से हटाते हैं और इसे विज़िट के रूप में चिह्नित करते हैं। नोड डी का निकटवर्ती नोड ए पहले से ही देखा गया है, इसलिए हम इसे अनदेखा करते हैं।
तो अब केवल नोड ई कतार में है। हम इसे चिह्नित के रूप में चिह्नित करते हैं और इसे विज़िट की गई सूची में जोड़ते हैं। E का निकटवर्ती नोड C है जो पहले से ही देखा गया है। इसलिए इसे नजरअंदाज करें।
इस बिंदु पर, कतार खाली है और देखी गई सूची में अनुक्रम है जिसे हमने BFS ट्रैवर्सल के परिणामस्वरूप प्राप्त किया है। अनुक्रम है, ए-> बी-> सी-> डी-> ई।
बीएफएस कार्यान्वयन
निम्नलिखित जावा प्रोग्राम बीएफएस तकनीक के कार्यान्वयन को दर्शाता है।
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list(); //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i आउटपुट:
बीएफएस ट्रैवर्सल के अनुप्रयोग
# 1) कचरा संग्रह: गारबेज कलेक्शन को कॉपी करने के लिए कचरा संग्रह तकनीक द्वारा उपयोग किए जाने वाले एल्गोरिदम में से एक 'चेनी का एल्गोरिदम' है। यह एल्गोरिथ्म एक चौड़ाई-प्रथम ट्रैवर्सल तकनीक का उपयोग करता है।
# 2) नेटवर्क में प्रसारण: नेटवर्क में एक बिंदु से दूसरे बिंदु पर पैकेट का प्रसारण बीएफएस तकनीक का उपयोग करके किया जाता है।
# 3) जीपीएस नेविगेशन: GPS का उपयोग करते समय हम आसन्न नोड्स को खोजने के लिए BFS तकनीक का उपयोग कर सकते हैं।
# 4) सोशल नेटवर्किंग वेबसाइट: किसी विशेष व्यक्ति के आसपास के लोगों के नेटवर्क का पता लगाने के लिए सोशल नेटवर्किंग वेबसाइटों में BFS तकनीक का भी उपयोग किया जाता है।
# 5) सबसे कम पथ और संयुक्त राष्ट्र के वेटेड ग्राफ में न्यूनतम फैले हुए पेड़: अनविटेड ग्राफ में, बीएफएस तकनीक का उपयोग न्यूनतम फैले हुए पेड़ और नोड्स के बीच सबसे छोटा रास्ता खोजने के लिए किया जा सकता है।
जावा ग्राफ लाइब्रेरी
जावा प्रोग्रामर के लिए अनिवार्य नहीं करता है कि वह प्रोग्राम में ग्राफ़ को हमेशा लागू करे। जावा बहुत सारे तैयार पुस्तकालय प्रदान करता है जिनका उपयोग सीधे कार्यक्रम में रेखांकन का उपयोग करने के लिए किया जा सकता है। इन पुस्तकालयों में ग्राफ और इसकी विभिन्न विशेषताओं का पूर्ण उपयोग करने के लिए आवश्यक सभी ग्राफ एपीआई कार्यक्षमता है।
नीचे दिए गए जावा में कुछ ग्राफ पुस्तकालयों का संक्षिप्त परिचय दिया गया है।
# 1) Google अमरूद: Google अमरुद एक समृद्ध पुस्तकालय प्रदान करता है जो सरल रेखांकन, नेटवर्क, मूल्य ग्राफ आदि सहित ग्राफ और एल्गोरिदम का समर्थन करता है।
# 2) अपाचे कॉमन्स: अपाचे कॉमन्स एक अपाचे परियोजना है जो ग्राफ़ डेटा संरचना घटक और एपीआई प्रदान करती है जिसमें एल्गोरिदम होते हैं जो इस ग्राफ़ डेटा संरचना पर काम करते हैं। ये घटक पुन: प्रयोज्य हैं।
#3) JGraphT: JGraphT व्यापक रूप से उपयोग किए जाने वाले जावा ग्राफ पुस्तकालयों में से एक है। यह ग्राफ डेटा संरचना की कार्यक्षमता प्रदान करता है जिसमें सरल ग्राफ, निर्देशित ग्राफ, भारित ग्राफ आदि के साथ-साथ एल्गोरिदम और एपीआई भी शामिल होते हैं जो ग्राफिकल संरचना पर काम करते हैं।
# 4) SourceForge जंग: जंग 'जावा यूनिवर्सल नेटवर्क / ग्राफ' के लिए है और एक जावा फ्रेमवर्क है। जंग डेटा के विश्लेषण, विज़ुअलाइज़ेशन और मॉडलिंग के लिए एक एक्स्टेंसिबल भाषा प्रदान करता है, जिसे हम ग्राफ के रूप में दर्शाना चाहते हैं।
जंग भी अपघटन, क्लस्टरिंग, अनुकूलन, आदि के लिए विभिन्न एल्गोरिदम और दिनचर्या प्रदान करता है।
बार बार पूछे जाने वाले प्रश्न
Q # 1) जावा में एक ग्राफ क्या है?
उत्तर: एक ग्राफ डेटा संरचना मुख्य रूप से कनेक्टेड डेटा को स्टोर करती है, उदाहरण के लिए, लोगों का एक नेटवर्क या शहरों का एक नेटवर्क। ग्राफ़ डेटा संरचना में आमतौर पर नोड्स या बिंदु होते हैं जिन्हें कोने कहा जाता है। प्रत्येक शीर्ष को किनारों नामक लिंक का उपयोग करके दूसरे शीर्ष से जोड़ा जाता है।
क्यू # 2) रेखांकन के प्रकार क्या हैं?
उत्तर: विभिन्न प्रकार के रेखांकन नीचे सूचीबद्ध हैं।
- लाइन ग्राफ: एक रेखा ग्राफ का उपयोग समय के सापेक्ष किसी विशेष संपत्ति में परिवर्तन की साजिश करने के लिए किया जाता है।
- दंड आरेख: बार रेखांकन विभिन्न शहरों में जनसंख्या जैसे सांख्यिक मूल्यों की तुलना करते हैं, देश भर में साक्षरता प्रतिशत, आदि।
इन मुख्य प्रकारों के अलावा हमारे पास अन्य प्रकार भी हैं जैसे कि चित्रलेख, हिस्टोग्राम, क्षेत्र ग्राफ, स्कैटर प्लॉट, आदि।
Q # 3) कनेक्टेड ग्राफ क्या है?
उत्तर: एक जुड़ा हुआ ग्राफ एक ग्राफ है जिसमें प्रत्येक शीर्ष दूसरे शिखर से जुड़ा होता है। इसलिए जुड़े हुए ग्राफ में, हम हर दूसरे शीर्ष से प्रत्येक शीर्ष पर जा सकते हैं।
विंडोज़ में डाट फाइलें कैसे खोलें
क्यू # 4) ग्राफ़ के अनुप्रयोग क्या हैं?
उत्तर: विभिन्न अनुप्रयोगों में ग्राफ़ का उपयोग किया जाता है। एक जटिल नेटवर्क का प्रतिनिधित्व करने के लिए ग्राफ का उपयोग किया जा सकता है। ग्राफ का उपयोग सोशल नेटवर्किंग अनुप्रयोगों में लोगों के नेटवर्क के साथ-साथ आसन्न लोगों या कनेक्शन खोजने जैसे अनुप्रयोगों के लिए भी किया जाता है।
कंप्यूटर विज्ञान में संगणना के प्रवाह को दर्शाने के लिए रेखांकन का उपयोग किया जाता है।
क्यू # 5) आप एक ग्राफ कैसे स्टोर करते हैं?
उत्तर: मेमोरी में ग्राफ को स्टोर करने के तीन तरीके हैं:
# 1) हम नोड्स या कोने को ऑब्जेक्ट और किनारों के रूप में इंगित कर सकते हैं।
#दो) हम ग्राफ़ को आसन्न मैट्रिक्स के रूप में भी स्टोर कर सकते हैं जिनकी पंक्तियाँ और कॉलम वर्टिस की संख्या के समान हैं। प्रत्येक पंक्ति और स्तंभ का प्रतिच्छेदन किसी किनारे की उपस्थिति या अनुपस्थिति को दर्शाता है। गैर-भारित ग्राफ में, किनारे की उपस्थिति को 1 से दर्शाया जाता है जबकि भारित ग्राफ में इसे किनारे के वजन से बदल दिया जाता है।
# 3) ग्राफ़ को संचय करने के लिए अंतिम दृष्टिकोण ग्राफ़ के कोने या नोड्स के बीच किनारों की एक आसन्न सूची का उपयोग करके है। प्रत्येक नोड या शीर्ष पर इसकी आसन्न सूची है।
निष्कर्ष
इस ट्यूटोरियल में, हमने जावा में ग्राफ़ पर विस्तार से चर्चा की है। हमने विभिन्न प्रकार के रेखांकन, ग्राफ कार्यान्वयन और ट्रैवर्सल तकनीकों का पता लगाया। नोड्स के बीच सबसे छोटा रास्ता खोजने के लिए ग्राफ़ का उपयोग किया जा सकता है।
हमारे आगामी ट्यूटोरियल में, हम सबसे छोटे मार्ग को खोजने के कुछ तरीकों पर चर्चा करके ग्राफ़ का पता लगाना जारी रखेंगे।
=> यहाँ सरल जावा प्रशिक्षण श्रृंखला देखें।
अनुशंसित पाठ
- उदाहरणों के साथ जावा परावर्तन ट्यूटोरियल
- जावा में डिक्स्ट्रा के एल्गोरिथ्म को कैसे लागू करें
- Java SWING Tutorial: कंटेनर, कंपोनेंट्स एंड इवेंट हैंडलिंग
- जावा ट्यूटोरियल फॉर बिगिनर्स: 100+ हैंड्स-ऑन जावा वीडियो ट्यूटोरियल
- जावा में ट्री मैप - जावा ट्रीपैप उदाहरणों के साथ ट्यूटोरियल
- जावा में मॉडिफायर एक्सेस करें - उदाहरणों के साथ ट्यूटोरियल
- स्ट्रिंग स्ट्रिंग बफर और स्ट्रिंग बिल्डर ट्यूटोरियल के साथ जावा स्ट्रिंग
- जावा स्ट्रिंग में () विधि ट्यूटोरियल विथ उदाहरण हैं
