graph implementation c using adjacency list
यह ट्यूटोरियल C ++ में ग्राफ़ के कार्यान्वयन का वर्णन करता है। आप विभिन्न प्रकार, प्रतिनिधित्व और ग्राफ़ के अनुप्रयोगों के बारे में भी जानेंगे:
एक ग्राफ एक गैर-रैखिक डेटा संरचना है। एक ग्राफ को नोड्स के एक संग्रह के रूप में परिभाषित किया जा सकता है, जिसे 'वर्टिस' और 'एज' भी कहा जाता है जो दो या अधिक वर्टिकल को जोड़ता है।
एक ग्राफ को एक चक्रीय पेड़ के रूप में भी देखा जा सकता है, जहां कोने में माता-पिता-बच्चे के संबंध नहीं होते हैं, लेकिन उनके बीच एक जटिल संबंध बनाए रखते हैं।
लेफ्ट जॉइन और लेफ्ट ऑउट के बीच अंतर
=> निरपेक्ष सी ++ प्रशिक्षण श्रृंखला के लिए यहां क्लिक करें।
आप क्या सीखेंगे:
क्या C ++ में एक ग्राफ है?
जैसा कि ऊपर कहा गया है, C ++ में एक ग्राफ एक गैर-रेखीय डेटा संरचना है, जिसे वर्टिस और किनारों के संग्रह के रूप में परिभाषित किया गया है।
निम्नलिखित एक ग्राफ डेटा संरचना का एक उदाहरण है।
ऊपर दिया गया एक उदाहरण है ग्राफ जी। ग्राफ जी कोने का एक सेट {ए, बी, सी, डी, ई} और किनारों का एक सेट है {(ए, बी), (बी, सी), (ए, डी) (डी, ई), (ई, सी), (बी, ई), (बी, डी)}।
ग्राफ़ के प्रकार - निर्देशित और अप्रत्यक्ष ग्राफ़
एक ग्राफ जिसमें किनारों का निर्देश नहीं होता है, उसे अप्रत्यक्ष ग्राफ़ कहा जाता है। ऊपर दिखाया गया ग्राफ एक अप्रत्यक्ष ग्राफ है।
एक ग्राफ जिसमें किनारों से जुड़ी दिशाएँ होती हैं, उन्हें निर्देशित ग्राफ़ कहा जाता है।
नीचे दिए गए एक निर्देशित ग्राफ का एक उदाहरण है।
ऊपर दिखाए गए निर्देशित ग्राफ में, किनारे एक आदेशित जोड़ी बनाते हैं जिसमें प्रत्येक किनारे एक शीर्ष से दूसरे शीर्ष पर एक विशिष्ट पथ का प्रतिनिधित्व करता है। जिस मार्ग से मार्ग आरंभ होता है, उसे 'कहा जाता है' प्रारंभिक नोड 'जबकि शिखर जिसमें पथ समाप्त हो जाता है' टर्मिनल नोड ”।
इस प्रकार उपरोक्त ग्राफ में, समुच्चय का सेट {ए, बी, सी, डी, ई} है और किनारों का सेट {ए, बी), (ए, डी), (बी, सी), (बी, ई) है ), (डी, ई) (ई, सी)}।
हम नीचे दी गई ग्राफ़ के संबंध में उपयोग की जाने वाली ग्राफ़ शब्दावली या सामान्य शब्दों पर चर्चा करेंगे।
ग्राफ शब्दावली
- वर्टेक्स: ग्राफ के प्रत्येक नोड को एक शीर्ष कहा जाता है। उपरोक्त ग्राफ में, A, B, C और D ग्राफ के शीर्ष हैं।
- बढ़त: दो कोने के बीच की कड़ी या पथ को किनारे कहा जाता है। यह दो या अधिक कोणों को जोड़ता है। उपरोक्त ग्राफ में विभिन्न किनारों AB, BC, AD और DC हैं।
- आसन्न नोड: एक ग्राफ में, यदि दो नोड्स एक किनारे से जुड़े होते हैं, तो उन्हें आसन्न नोड्स या पड़ोसी कहा जाता है। उपरोक्त ग्राफ में, किनारे एबी द्वारा बी और ए जुड़े हुए हैं। इस प्रकार ए और बी आसन्न नोड्स हैं।
- नोड की डिग्री: किसी विशेष नोड से जुड़े किनारों की संख्या को नोड का डिग्री कहा जाता है। उपरोक्त ग्राफ में, नोड ए की डिग्री 2 है।
- पथ: नोड्स का अनुक्रम जिसे हमें पालन करने की आवश्यकता होती है जब हमें एक ग्राफ में एक शीर्ष से दूसरे तक यात्रा करना होता है जिसे पथ कहा जाता है। हमारे उदाहरण के ग्राफ में, यदि हमें नोड ए से सी तक जाने की आवश्यकता है, तो पथ ए-> बी-> सी होगा।
- बंद रास्ता: यदि प्रारंभिक नोड टर्मिनल नोड के समान है, तो उस पथ को बंद पथ के रूप में कहा जाता है।
- सरल पथ: एक बंद रास्ता जिसमें अन्य सभी नोड्स अलग होते हैं, एक सरल पथ कहा जाता है।
- चक्र: ऐसा मार्ग जिसमें बार-बार किनारे या कोने नहीं होते हैं और पहले और अंतिम कोने को एक चक्र कहा जाता है। उपरोक्त ग्राफ में, A-> B-> C-> D-> A एक चक्र है।
- कनेक्टेड ग्राफ़: एक जुड़ा हुआ ग्राफ वह है जिसमें प्रत्येक कोने के बीच एक मार्ग होता है। इसका मतलब यह है कि एक भी शीर्ष नहीं है जो अलग हो या एक कनेक्टिंग किनारे के बिना। ऊपर दिखाया गया ग्राफ एक जुड़ा हुआ ग्राफ है।
- पूरा ग्राफ: एक ग्राफ जिसमें प्रत्येक नोड को दूसरे से जोड़ा जाता है उसे पूर्ण ग्राफ़ कहा जाता है। यदि N एक ग्राफ में कुल नोड्स की संख्या है तो पूर्ण ग्राफ़ में N (N-1) / 2 संख्या के किनारे हैं।
- भारित ग्राफ: प्रत्येक किनारे को निर्दिष्ट एक सकारात्मक मान जो इसकी लंबाई को दर्शाता है (एक किनारे से जुड़े कोने के बीच की दूरी) को वजन कहा जाता है। भारित किनारों वाले ग्राफ को भारित ग्राफ कहा जाता है। किनारे e के भार को w (e) द्वारा निरूपित किया जाता है और यह एक किनारे को पार करने की लागत को इंगित करता है।
- Diagraph: डिग्राफ एक ऐसा ग्राफ है जिसमें प्रत्येक किनारे एक विशिष्ट दिशा से जुड़ा होता है और ट्रैवर्सल को निर्दिष्ट दिशा में ही किया जा सकता है।
ग्राफ प्रतिनिधित्व
जिस तरह से ग्राफ डेटा संरचना को मेमोरी में संग्रहीत किया जाता है उसे 'प्रतिनिधित्व' कहा जाता है। ग्राफ को एक अनुक्रमिक प्रतिनिधित्व या एक जुड़े प्रतिनिधित्व के रूप में संग्रहीत किया जा सकता है।
इन दोनों प्रकारों को नीचे वर्णित किया गया है।
अनुक्रमिक प्रतिनिधित्व
ग्राफ़ के अनुक्रमिक प्रतिनिधित्व में, हम आसन्न मैट्रिक्स का उपयोग करते हैं। एक आसन्न मैट्रिक्स आकार n x n का एक मैट्रिक्स है जहां n ग्राफ में कोने की संख्या है।
आसन्न मैट्रिक्स की पंक्तियाँ और स्तंभ एक ग्राफ़ में कोने का प्रतिनिधित्व करते हैं। मैट्रिक्स तत्व 1 पर सेट होता है जब कोने के बीच एक किनारे मौजूद होता है। यदि किनारे मौजूद नहीं है, तो तत्व 0 पर सेट है।
नीचे दिया गया एक उदाहरण ग्राफ है जो इसके आसन्न मैट्रिक्स को दर्शाता है।
हमने उपरोक्त ग्राफ़ के लिए आसन्न मैट्रिक्स देखा है। ध्यान दें कि चूंकि यह एक अप्रत्यक्ष ग्राफ़ है, और हम कह सकते हैं कि बढ़त दोनों दिशाओं में मौजूद है। उदाहरण के लिए, एज एबी मौजूद है, हम यह निष्कर्ष निकाल सकते हैं कि बढ़त बीए भी मौजूद है।
आसन्न मैट्रिक्स में, हम उन आवृत्तियों के इंटरैक्शन देख सकते हैं जो मैट्रिक्स तत्व हैं जो 1 पर सेट होते हैं जब भी किनारे मौजूद होते हैं और जब किनारे अनुपस्थित होते हैं तो 0।
अब एक निर्देशित ग्राफ के आसन्न मैट्रिक्स को देखते हैं।
जैसा कि ऊपर दिखाया गया है, आसन्न मैट्रिक्स में प्रतिच्छेदन तत्व 1 होगा और केवल अगर एक किनारे से दूसरे तक निर्देशित एक किनारे है।
उपरोक्त ग्राफ में, हम ए से दो छोर हैं ए। ए। एज को वर्टेक्स बी में समाप्त किया गया है, जबकि दूसरा एक वर्टिकल सी में समाप्त हो गया है। इस प्रकार आसन्न मैट्रिक्स में ए और बी का चौराहा 1 ए और सी के चौराहे के रूप में सेट है।
अगला, हम भारित ग्राफ के लिए अनुक्रमिक प्रतिनिधित्व देखेंगे।
नीचे दिए गए भारित ग्राफ और इसके संबंधित आसन्न मैट्रिक्स है।
हम देख सकते हैं कि भारित ग्राफ का अनुक्रमिक प्रतिनिधित्व अन्य प्रकार के ग्राफ से अलग है। यहां, आसन्न मैट्रिक्स में गैर-शून्य मान को किनारे के वास्तविक वजन से बदल दिया जाता है।
किनारे एबी का वजन = 4 है, इस प्रकार आसन्न मैट्रिक्स में, हम ए और बी के अंतर को 4 से सेट करते हैं। इसी तरह, अन्य सभी गैर-शून्य मानों को उनके संबंधित वजन में बदल दिया जाता है।
आसन्न सूची को लागू करने और पालन करने में आसान है। ट्रैवर्सल यानि यह जांचने के लिए कि क्या एक किनारे से दूसरे तक जाने में O (1) का समय लगता है और एक किनारे को हटाने में O (1) भी लगता है।
चाहे ग्राफ विरल हो (कम किनारों वाला) या घना, यह हमेशा अधिक मात्रा में स्थान लेता है।
लिंक किया हुआ प्रतिनिधि
हम ग्राफ़ के लिंक किए गए प्रतिनिधित्व के लिए आसन्न सूची का उपयोग करते हैं। आसन्न सूची प्रतिनिधित्व ग्राफ के प्रत्येक नोड और नोड्स के लिए एक लिंक रखता है जो इस नोड से सटे हैं। जब हम सभी आसन्न नोड्स को पीछे छोड़ते हैं, तो हम सूची के अंत में नल के लिए अगला पॉइंटर सेट करते हैं।
आइए पहले हम एक अप्रत्यक्ष ग्राफ और उसके आसन्न सूची पर विचार करें।
जैसा कि ऊपर दिखाया गया है, हमारे पास प्रत्येक नोड के लिए एक लिंक की गई सूची (आसन्न सूची) है। शीर्ष A से, हमारे पास कोने B, C और D हैं, इस प्रकार ये नोड्स संबंधित आसन्न सूची में नोड A से जुड़े हैं।
अगला, हम निर्देशित ग्राफ के लिए एक आसन्न सूची बनाते हैं।
उपर्युक्त-निर्देशित ग्राफ में, हम देखते हैं कि वर्टिक्स ई से कोई किनारा नहीं निकलता है। इसलिए वर्टेक्स ई के लिए आसन्न सूची खाली है।
अब हम भारित ग्राफ के लिए आसन्न सूची का निर्माण करते हैं।
भारित ग्राफ़ के लिए, हम किनारे के वजन को दर्शाने के लिए आसन्न सूची नोड में एक अतिरिक्त फ़ील्ड जोड़ते हैं जैसा कि ऊपर दिखाया गया है।
आसन्न सूची में शीर्ष जोड़ना आसान है। यह लिंक किए गए सूची के कार्यान्वयन के कारण भी स्थान बचाता है। जब हमें यह पता लगाने की आवश्यकता होती है कि क्या एक शीर्ष से दूसरे के बीच एक किनारे है, तो ऑपरेशन कुशल नहीं है।
रेखांकन के लिए मूल संचालन
निम्नलिखित बुनियादी ऑपरेशन हैं जो हम ग्राफ डेटा संरचना पर प्रदर्शन कर सकते हैं:
- एक शीर्ष जोड़ें: ग्राफ़ में वर्टेक्स जोड़ता है।
- बढ़त जोड़ें: एक ग्राफ के दो कोने के बीच एक बढ़त जोड़ता है।
- ग्राफ कोने प्रदर्शित करें: एक ग्राफ के कोने प्रदर्शित करें।
सी + + ग्राफ कार्यान्वयन आसन्न सूची का उपयोग करना
अब हम आसन्न सूची का उपयोग करके एक सरल ग्राफ प्रदर्शित करने के लिए C ++ कार्यान्वयन प्रस्तुत करते हैं।
यहां हम एक भारित निर्देशित ग्राफ़ के लिए आसन्न सूची प्रदर्शित करने जा रहे हैं। हमने आसन्न सूची और ग्राफ के किनारों को पकड़ने के लिए दो संरचनाओं का उपयोग किया है। आसन्न सूची को (start_vertex, end_vertex, वजन) के रूप में प्रदर्शित किया जाता है।
C ++ प्रोग्राम इस प्रकार है:
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i आउटपुट:
आउटपुट:
ग्राफ आसन्न सूची
(start_vertex, end_vertex, वजन):
लोड बैलेंसिंग राउटर दो इंटरनेट कनेक्शन
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
रेखांकन के अनुप्रयोग
आइए ग्राफ़ के कुछ अनुप्रयोगों पर चर्चा करते हैं।
- कंप्यूटर विज्ञान में ग्राफ़ का उपयोग बड़े पैमाने पर नेटवर्क ग्राफ़, या अर्थ ग्राफ़, या यहाँ तक कि गणना के प्रवाह को चित्रित करने के लिए किया जाता है।
- ग्राफ़ को व्यापक रूप से कंपाइलरों में संसाधनों के आवंटन को प्रक्रियाओं को चित्रित करने या डेटा प्रवाह विश्लेषण आदि को इंगित करने के लिए उपयोग किया जाता है।
- कुछ विशेष संकलक में डेटाबेस भाषाओं में क्वेरी ऑप्टिमाइज़ेशन के लिए ग्राफ़ का भी उपयोग किया जाता है।
- सोशल नेटवर्किंग साइटों में, लोगों के नेटवर्क को चित्रित करने के लिए रेखांकन मुख्य संरचनाएं हैं।
- परिवहन प्रणाली विशेषकर सड़क नेटवर्क के निर्माण के लिए बड़े पैमाने पर रेखांकन का उपयोग किया जाता है। एक लोकप्रिय उदाहरण Google मानचित्र है जो दुनिया भर में दिशाओं को इंगित करने के लिए बड़े पैमाने पर ग्राफ़ का उपयोग करता है।
निष्कर्ष
एक ग्राफ एक लोकप्रिय और बड़े पैमाने पर उपयोग की जाने वाली डेटा संरचना है जिसमें कंप्यूटर विज्ञान के क्षेत्र में अन्य क्षेत्रों के अलावा कई अनुप्रयोग हैं। रेखांकन दो और अधिक कोने को जोड़ने वाले कोने और किनारों से मिलकर बनता है।
एक ग्राफ को निर्देशित या अप्रत्यक्ष किया जा सकता है। हम आसन्न मैट्रिक्स का उपयोग करके ग्राफ़ का प्रतिनिधित्व कर सकते हैं जो एक रैखिक प्रतिनिधित्व के साथ-साथ आसन्न लिंक्ड सूची का उपयोग कर रहा है। हमने इस ट्यूटोरियल में ग्राफ के कार्यान्वयन पर भी चर्चा की।
=> पूर्ण सी ++ ट्यूटोरियल सूची देखने के लिए यहां देखें।
अनुशंसित पाठ
- पायथन एडवांस्ड लिस्ट ट्यूटोरियल (सूची क्रमबद्ध, रिवर्स, इंडेक्स, कॉपी, जॉइन, सम)
- पायथन सूची - तत्वों को बनाएं, एक्सेस, स्लाइस, जोड़ें या हटाएं
- सामान्य वायरलेस रूटर ब्रांडों के लिए डिफ़ॉल्ट राउटर आईपी पता सूची
- 12 सर्वश्रेष्ठ लाइन ग्राफ निर्माता उपकरण तेजस्वी रेखा रेखांकन बनाने के लिए (2021 RANKINGS)
- डिफ़ॉल्ट रूटर लॉगिन पासवर्ड शीर्ष रूटर मॉडल (2021 सूची) के लिए
- सी + + में चित्र संरचना के साथ लिंक्ड सूची डेटा संरचना
- चित्रण के साथ C ++ में परिपत्र लिंक्ड सूची डेटा संरचना
- संदेह के साथ सी ++ में संदिग्ध रूप से सूचीबद्ध डेटा संरचना
