ग्राफ डेटा संरचना और Algorithms (उदाहरण)

डेटा संरचना में ग्राफ क्या है?

ग्राफ एक गैर-रेखीय डेटा संरचना है जिसमें शीर्ष और किनारे होते हैं, जहां शीर्षों में जानकारी या डेटा होता है, और किनारे शीर्षों के एक जोड़े के बीच एक कड़ी के रूप में काम करते हैं।

इसका उपयोग गंतव्य स्थान तक पहुंचने का सर्वोत्तम मार्ग खोजने और दूरसंचार एवं सामाजिक नेटवर्क के लिए मार्ग निर्धारित करने जैसी वास्तविक दुनिया की समस्याओं को हल करने के लिए किया जाता है। ग्राफ में उपयोगकर्ताओं को नोड माना जाता है, और तारों को उपयोगकर्ताओं को जोड़ने वाले किनारे (एज) के रूप में दर्शाया जाता है।

यदि किनारों को E के रूप में और शीर्षों को V के रूप में दर्शाया जाता है, तो ग्राफ G को शीर्षों और किनारों के समूह के रूप में लिखा जा सकता है, जैसे जी (वी, ई).

डेटा संरचना में ग्राफ का उदाहरण

ग्राफ डेटा संरचना का एक सरल उदाहरण यहां दिया गया है:

यह एक सरल अप्रत्यक्ष ग्राफ है (एक प्रकार का ग्राफ)। यहाँ शीर्षों का समुच्चय {A, B, C, D, E, F} है। दो शीर्ष मिलकर एक किनारा बनाते हैं। उदाहरण के लिए, A और B एक किनारे से जुड़े हुए हैं। हालांकि, A और F किसी भी किनारे से नहीं जुड़े हुए हैं।

डेटा संरचना में ग्राफ़ शब्दावली

ग्राफ डेटा संरचना में प्रयुक्त कुछ महत्वपूर्ण शब्द निम्नलिखित हैं:

अवधि	विवरण
शिखर	प्रत्येक डेटा तत्व को शीर्ष या नोड कहा जाता है। ऊपर दिए गए चित्र में, A, B, C, D और E शीर्ष हैं।
किनारा (आर्क)	दो नोड्स या शीर्षों को जोड़ने वाली कड़ियों को किनारा (चाप) कहा जाता है। इसके दो सिरे होते हैं और इसे (प्रारंभिक शीर्ष, अंतिम शीर्ष) के रूप में दर्शाया जाता है।
अनिर्दिष्ट किनारा	यह एक द्विदिशीय किनारा है।
निर्देशित किनारा	यह एक दिशात्मक किनारा है।
भारित किनारा	एक किनारा जिस पर कोई मान अंकित हो।
डिग्री	किसी ग्राफ में, किसी शीर्ष से जुड़े किनारों की संख्या को डिग्री कहा जाता है।
इंडिग्री	एक शीर्ष से जुड़े आने वाले किनारों की कुल संख्या.
आउटडिग्री	किसी शीर्ष से जुड़े हुए बहिर्गामी किनारों की कुल संख्या.
स्व पाश	किसी किनारे को स्व-लूप कहा जाता है यदि उसके दो अंतबिन्दु एक दूसरे से मिलते हों।
समीपता	शीर्षों को आसन्न कहा जाता है यदि उनके बीच एक किनारा जुड़ा हो।

डेटा संरचना में ग्राफ़ के प्रकार

यहाँ सबसे आम की सूची दी गई है डेटा संरचना में ग्राफ़ के प्रकार:

• निर्देशित ग्राफ
• अनिर्देशित ग्राफ
• भारित ग्राफ़
• द्वि-दिशात्मक ग्राफ
• अनंत ग्राफ
• शून्य ग्राफ
• तुच्छ ग्राफ
• मल्टी ग्राफ
• पूरा ग्राफ
• कनेक्टेड ग्राफ
• चक्रीय ग्राफ
• निर्देशित चक्रीय ग्राफ (DAG)
• चक्र ग्राफ
• द्विदलीय ग्राफ
• यूलर ग्राफ
• हैमिल्टन ग्राफ

ग्राफ को डेटा संरचना में कैसे दर्शाया जाता है?

ग्राफ को आमतौर पर दो निरूपणों में से किसी एक का उपयोग करके मेमोरी में संग्रहीत किया जाता है। यह चुनाव इस बात को प्रभावित करता है कि ग्राफ कितनी मेमोरी का उपयोग करता है और सामान्य क्रियाएं कितनी तेजी से चलती हैं।

• सहखंडज मैट्रिक्स: एक द्वि-आयामी V × V सरणी, जिसमें सेल [i][j] का मान 1 (या किनारे का भार) होता है यदि शीर्ष i और शीर्ष j के बीच कोई किनारा मौजूद हो, अन्यथा 0 होता है। यह O(1) एज लुकअप की अनुमति देता है लेकिन O(V²) स्थान का उपयोग करता है, जिससे यह सघन ग्राफ़ के लिए सर्वोत्तम है।
• आसन्नता सूची: सूचियों का एक ऐरे जिसमें प्रत्येक शीर्ष अपने पड़ोसी शीर्षों की सूची संग्रहीत करता है। यह O(V + E) स्थान का उपयोग करता है और विरल ग्राफ़ के लिए कुशल है, यही कारण है कि अधिकांश वास्तविक दुनिया के ग्राफ़ इसका उपयोग करते हैं।

आप इनके बारे में और अधिक जानकारी प्राप्त कर सकते हैं। ग्राफ का आसन्नता सूची और मैट्रिक्स निरूपण ट्यूटोरियल।

ग्राफ डेटा संरचना के अनुप्रयोग

ग्राफ के कई उपयोग हैं। ग्राफ का उपयोग करने वाले कई एल्गोरिदम हैं। ग्राफ के कुछ अनुप्रयोग इस प्रकार हैं:

• गूगल मैप्स दो सड़कों के प्रतिच्छेदन बिंदु का पता लगाने और दो स्थानों के बीच की दूरी की गणना करने के लिए ग्राफ़ का उपयोग करता है। उदाहरण के लिए, डिज्कस्ट्रास्रोत और गंतव्य स्थान के बीच की सबसे छोटी दूरी ज्ञात करने के लिए।
• फेसबुक उपयोगकर्ताओं के आपसी मित्रों का पता लगाने के लिए ग्राफ़ का उपयोग करता है। इसका एल्गोरिदम प्रत्येक उपयोगकर्ता को ग्राफ़ के एक नोड के रूप में मानता है।
• संसाधन आवंटन के लिए, एक डीएजी (निर्देशित चक्रीय ग्राफ) का उपयोग किया जाता है। यह संसाधनों की निर्भरता की जाँच करता है।
• गूगल सर्च इंजन वेबसाइटों की रैंकिंग बनाने के लिए ग्राफ का उपयोग करता है।
• एक नक्शाping यह उपकरण ग्राफ डेटा संरचना का उपयोग करता है।
• A रूटर और इसका प्रोटोकॉल गंतव्य तक पहुंचने का मार्ग जानने के लिए ग्राफ का उपयोग करता है।

अक्सर पूछे जाने वाले प्रश्न