ग्राफ डेटा संरचना और Algorithms (उदाहरण)
सारा चेन
डेटा संरचना में ग्राफ क्या है?
ग्राफ एक गैर-रैखिक डेटा संरचना है जिसमें शीर्ष और किनारे होते हैं, जहां शीर्षों में सूचना या डेटा होता है, और किनारे शीर्षों की जोड़ी के बीच एक कड़ी के रूप में काम करते हैं।
इसका उपयोग वास्तविक शब्द समस्याओं को हल करने के लिए किया जाता है जैसे गंतव्य स्थान तक सबसे अच्छा मार्ग ढूँढना और दूरसंचार और सामाजिक नेटवर्क के लिए मार्ग। उपयोगकर्ताओं को ग्राफ़ में एक नोड माना जाता है, और तार उपयोगकर्ताओं को जोड़ने वाले किनारे हैं।
यदि किनारों को E के रूप में और शीर्षों को V के रूप में दर्शाया जाता है, तो ग्राफ G को शीर्षों और किनारों के समूह के रूप में लिखा जा सकता है, जैसे G (V, E)
डेटा संरचना में ग्राफ का उदाहरण
यहाँ ग्राफ डेटा संरचना का एक सरल उदाहरण दिया गया है:
यह एक सरल अनिर्देशित ग्राफ (एक प्रकार का ग्राफ) है। यहाँ शीर्षों का समूह है: {A, B, C,D,E,F}। दो शीर्ष एक किनारा बनाते हैं। उदाहरण के लिए, A और B एक किनारे से जुड़े हुए हैं। हालाँकि, A और F किसी भी किनारे से जुड़े नहीं हैं।
डेटा संरचना में ग्राफ़ शब्दावली
ग्राफ़ डेटा संरचना में प्रयुक्त कुछ महत्वपूर्ण शब्द निम्नलिखित हैं:
| अवधि | विवरण |
|---|---|
| शिखर | सभी डेटा तत्वों को वर्टेक्स या नोड कहा जाता है। ऊपर दी गई छवि में, A, B, C, D और E वर्टेक्स हैं। |
| किनारा (आर्क) | दो नोड्स या वर्टेक्स के बीच कनेक्टिंग लिंक को एज (आर्क) कहा जाता है। इसके दो सिरे होते हैं और इसे (startingVertex, endingVertex) के रूप में दर्शाया जाता है। |
| अनिर्दिष्ट किनारा | यह एक द्विदिशीय किनारा है। |
| निर्देशित किनारा | यह एक दिशात्मक किनारा है। |
| भारित किनारा | एक किनारा जिस पर मूल्य है। |
| डिग्री | ग्राफ में, किसी शीर्ष से जुड़े किनारों की संख्या को डिग्री कहा जाता है। |
| इंडिग्री | एक शीर्ष से जुड़े आने वाले किनारों की कुल संख्या. |
| आउटडिग्री | किसी शीर्ष से जुड़े हुए बहिर्गामी किनारों की कुल संख्या. |
| स्व पाश | किसी किनारे को स्व-लूप कहा जाता है यदि उसके दो अंतबिन्दु एक दूसरे से मिलते हों। |
| समीपता | यदि कोई किनारा जुड़ा हुआ है तो शीर्षों को आसन्न कहा जाता है। |
डेटा संरचना में ग्राफ़ के प्रकार
यहाँ सबसे आम की सूची दी गई है डेटा संरचना में ग्राफ़ के प्रकार:
- निर्देशित ग्राफ
- अनिर्देशित ग्राफ
- भारित ग्राफ़
- द्वि-दिशात्मक ग्राफ
- अनंत ग्राफ
- शून्य ग्राफ
- तुच्छ ग्राफ
- मल्टी ग्राफ
- पूरा ग्राफ
- कनेक्टेड ग्राफ
- चक्रीय ग्राफ
- निर्देशित चक्रीय ग्राफ (DAG)
- चक्र ग्राफ
- द्विदलीय ग्राफ
- यूलर ग्राफ
- हैमिल्टन ग्राफ
ग्राफ डेटा संरचना के अनुप्रयोग
ग्राफ़ के कई उपयोग हैं। ऐसे बहुत से एल्गोरिदम हैं जो ग्राफ़ का बहुत ज़्यादा इस्तेमाल करते हैं। ग्राफ़ के कुछ अनुप्रयोग इस प्रकार हैं:
- गूगल मैप्स दो सड़कों के प्रतिच्छेदन का पता लगाने और दो स्थानों के बीच की दूरी की गणना करने के लिए ग्राफ का उपयोग करता है।
उदाहरण के लिए, डिज्कस्ट्रा, स्रोत और गंतव्य स्थान के बीच न्यूनतम दूरी ज्ञात करने के लिए। - फेसबुक उपयोगकर्ताओं के आपसी मित्रों को खोजने के लिए ग्राफ़ का उपयोग करता है। इसका एल्गोरिदम प्रत्येक उपयोगकर्ता को ग्राफ़ के एक नोड के रूप में मानता है।
- संसाधन आवंटन के लिए, DAG (डायरेक्ट एसाइक्लिक ग्राफ) का उपयोग किया जाता है। यह संसाधनों की निर्भरता की जाँच करता है।
- गूगल सर्च इंजन वेबसाइटों की रैंकिंग बनाने के लिए ग्राफ का उपयोग करता है।
- मैपिंग डिवाइस ग्राफ डेटा संरचना का उपयोग करता है।
- रूटर और टी का प्रोटोकॉल गंतव्य पथ का पथ जानने के लिए ग्राफ का उपयोग करता है।
