इस ट्यूटोरियल में, आप सीखेंगे कि ग्राफ़ डेटा संरचना क्या है। इसके अलावा, आप एक ग्राफ का प्रतिनिधित्व करेंगे।
एक ग्राफ़ डेटा संरचना नोड्स का एक संग्रह है जिसमें डेटा होता है और अन्य नोड्स से जुड़ा होता है।
आइए एक उदाहरण के माध्यम से इसे समझने का प्रयास करें। फेसबुक पर, सब कुछ एक नोड है। जिसमें यूजर, फोटो, एल्बम, ईवेंट, ग्रुप, पेज, कमेंट, स्टोरी, वीडियो, लिंक, नोट … कुछ भी जिसमें डेटा हो, नोड है।
हर रिश्ता एक नोड से दूसरे में एक बढ़त है। चाहे आप एक तस्वीर पोस्ट करते हैं, एक समूह में शामिल होते हैं, जैसे एक पृष्ठ, आदि, उस रिश्ते के लिए एक नया किनारा बनाया जाता है।
ग्राफ डेटा संरचना का उदाहरण
फ़ेसबुक के सभी इन नोड्स और किनारों का एक संग्रह है। ऐसा इसलिए है क्योंकि facebook अपने डेटा को संग्रहीत करने के लिए एक ग्राफ़ डेटा संरचना का उपयोग करता है।
अधिक सटीक रूप से, एक ग्राफ एक डेटा संरचना (वी, ई) है जिसमें शामिल हैं
- कोने का एक संग्रह वी
- किनारों का एक संग्रह ई, वर्टिकल जोड़े के रूप में दर्शाया गया (यू, वी)
ऊर्ध्वाधर और किनारों
ग्राफ में,
वी = (0, 1, 2, 3) ई = ((0,1), (0,2), (0,3), (1,2)) जी = (वी, ई)
ग्राफ शब्दावली
- निकटता : एक शीर्ष को दूसरे शीर्ष से सटे हुए कहा जाता है यदि कोई धार है जो उन्हें जोड़ता है। ऊर्ध्वाधर 2 और 3 आसन्न नहीं हैं क्योंकि उनके बीच कोई किनारा नहीं है।
- पथ : किनारों का एक क्रम जो आपको शीर्ष पर से A तक जाने की अनुमति देता है, B को एक पथ कहा जाता है। 0-1, 1-2 और 0-2, वर्टेक्स 0 से वर्टेक्स 2 तक के रास्ते हैं।
- निर्देशित ग्राफ़ : एक ग्राफ़ जिसमें एक किनारे (यू, वी) का मतलब यह नहीं है कि एक किनारे (वी, यू) भी है। इस तरह के ग्राफ में किनारों को किनारे की दिशा दिखाने के लिए तीरों द्वारा दर्शाया गया है।
ग्राफ प्रतिनिधित्व
आमतौर पर रेखांकन को दो तरीकों से दर्शाया जाता है:
1. आसन्न मैट्रिक्स
एक आसन्न मैट्रिक्स V x V कोने का 2 डी सरणी है। प्रत्येक पंक्ति और स्तंभ एक शीर्ष का प्रतिनिधित्व करते हैं।
यदि किसी तत्व a(i)(j)का मूल्य 1 है, तो यह दर्शाता है कि एक धार है जो कि शीर्ष i और वर्टेक्स j को जोड़ती है।
ऊपर दिए गए ग्राफ़ के लिए आसन्न मैट्रिक्स है
ग्राफ आसन्न मैट्रिक्स
चूंकि यह एक अप्रत्यक्ष ग्राफ है, एज (0,2) के लिए, हमें एज (2,0) को भी चिह्नित करना होगा; विकर्ण के बारे में आसन्न मैट्रिक्स सममित बनाना।
एज लुकअप (यह जाँचना कि यदि कोई कगार शीर्ष A और शीर्ष B के बीच मौजूद है) आसन्न मैट्रिक्स प्रतिनिधित्व में बहुत तेज़ है, लेकिन हमें सभी कोने (V x V) के बीच हर संभव लिंक के लिए स्थान आरक्षित करना होगा, इसलिए इसे अधिक स्थान की आवश्यकता है।
2. आसन्न सूची
एक सन्निकटन सूची लिंक्ड सूची की एक सरणी के रूप में एक ग्राफ का प्रतिनिधित्व करती है।
सरणी का सूचकांक एक शीर्ष का प्रतिनिधित्व करता है और इसकी लिंक की गई सूची में प्रत्येक तत्व अन्य शीर्षों का प्रतिनिधित्व करता है जो शीर्ष के साथ एक किनारे बनाते हैं।
पहले उदाहरण में हमने जो ग्राफ बनाया है, उसके लिए आसन्न सूची इस प्रकार है:
आसन्न सूची प्रतिनिधित्व
भंडारण के संदर्भ में एक आसन्न सूची कुशल है क्योंकि हमें केवल किनारों के लिए मूल्यों को संग्रहीत करने की आवश्यकता है। लाखों वर्टिकल वाले ग्राफ के लिए, इसका मतलब बहुत अधिक बचा हुआ स्थान हो सकता है।
ग्राफ संचालन
सबसे आम ग्राफ संचालन हैं:
- जाँच करें कि क्या तत्व ग्राफ में मौजूद है
- ग्राफ ट्रैवर्सल
- तत्वों (वर्टेक्स, किनारों) को ग्राफ में जोड़ें
- एक शीर्ष से दूसरे तक का मार्ग खोजना
