डेटा संरचना में ग्राफ़ के प्रकार उदाहरणों के साथ
ग्राफ एक गैर-रैखिक डेटा संरचना है जिसमें कोने और किनारे होते हैं। कोने में सूचना या डेटा होता है, और किनारे कोने की जोड़ी के बीच एक कड़ी के रूप में काम करते हैं।
नोड्स और किनारों की स्थिति के आधार पर ग्राफ़ कई प्रकार के हो सकते हैं। यहाँ ग्राफ़ के कुछ महत्वपूर्ण प्रकार दिए गए हैं:
निर्देशित ग्राफ
निर्देशित ग्राफ के किनारों पर तीर होते हैं जो दिशा दर्शाते हैं। तीर यह निर्धारित करता है कि किनारा कहाँ इंगित किया गया है या कहाँ समाप्त होता है।
यहाँ निर्देशित ग्राफ का एक उदाहरण दिया गया है।
- हम नोड A से D तक जा सकते हैं।
- हालाँकि, हम नोड D से नोड A तक नहीं जा सकते क्योंकि किनारा A से D की ओर इंगित करता है।
- चूंकि ग्राफ में भार नहीं है, इसलिए शीर्ष A से D तक यात्रा करने में उतना ही खर्च आएगा जितना D से F तक यात्रा करने में।
अनिर्देशित ग्राफ
अनिर्देशित ग्राफ में बिना किसी संकेत के किनारे होते हैं। इसका मतलब है कि हम दो शीर्षों के बीच विपरीत दिशा में यात्रा कर सकते हैं।
यहाँ अनिर्देशित ग्राफ का एक सरल उदाहरण दिया गया है।
उपरोक्त ग्राफ में,
- हम A से B तक जा सकते हैं
- हम B से A तक भी जा सकते हैं
- किनारों में कोई दिशा नहीं होती.
यह एक अनिर्देशित ग्राफ का उदाहरण है जिसमें शीर्षों और किनारों की संख्या सीमित होती है तथा कोई भार नहीं होता।
भारित ग्राफ़
जिस ग्राफ में किनारों पर भार या लागत होती है उसे भारित ग्राफ कहते हैं। संख्यात्मक मान आम तौर पर एक शीर्ष से दूसरे शीर्ष पर जाने वाली लागत को दर्शाता है। निर्देशित और अप्रत्यक्ष दोनों ग्राफ के किनारों पर भार हो सकते हैं।
यहाँ भारित ग्राफ (निर्देशित) का एक उदाहरण दिया गया है।
- A से B तक जाने पर एक किनारा है, तथा भार 5 है, जिसका अर्थ है कि A से B तक जाने पर हमें 5 का खर्च आएगा।
- A, B की ओर एक बिंदु बनाता है, लेकिन इस ग्राफ में, B का A पर कोई सीधा किनारा नहीं है। इसलिए, हम B से A तक नहीं जा सकते।
- हालाँकि, अगर हम A से F तक जाना चाहते हैं, तो कई रास्ते हैं। रास्ते हैं ADF, ABF। ADF की कीमत (10+11) या 21 होगी।
- यहां, पथ ABF की लागत (5+15) या 20 होगी। यहां हम पथ में प्रत्येक किनारे का भार जोड़ रहे हैं।
यहाँ भार सहित अनिर्देशित ग्राफ का एक उदाहरण दिया गया है:
यहाँ, किनारे पर भार तो है लेकिन दिशा नहीं है। इसका मतलब है कि शीर्ष A से D तक जाने में 10 का खर्च आएगा और इसके विपरीत।
द्वि-दिशात्मक ग्राफ
द्वि-दिशात्मक और अनिर्देशित ग्राफ़ में एक सामान्य गुण होता है। वह है
- सामान्यतः, अनिर्देशित ग्राफ में दो शीर्षों के बीच एक किनारा हो सकता है।
उदाहरण के लिए:
- यहां, A से D या D से A तक जाने पर 10 का खर्च आएगा।
- द्वि-दिशात्मक ग्राफ में, दो शीर्षों के बीच दो किनारे हो सकते हैं।
यहाँ एक उदाहरण दिया गया है:
A से D तक जाने में हमें 17 का खर्च आएगा, लेकिन D से A तक जाने में हमें 12 का खर्च आएगा। इसलिए, यदि यह एक अनिर्देशित ग्राफ है तो हम दो अलग-अलग भार निर्दिष्ट नहीं कर सकते।
अनंत ग्राफ
ग्राफ में अनंत संख्या में किनारे और नोड्स होंगे। यदि कोई ग्राफ अनंत है और यह एक जुड़ा हुआ ग्राफ भी है, तो इसमें अनंत संख्या में किनारे भी होंगे। यहाँ, विस्तारित किनारों का मतलब है कि किनारों के माध्यम से इन नोड्स से अधिक किनारे जुड़े हो सकते हैं।
यहाँ अनंत ग्राफ का एक उदाहरण दिया गया है:
शून्य ग्राफ
शून्य ग्राफ में केवल नोड या कोने होते हैं, लेकिन कोई किनारा नहीं होता। यदि ग्राफ G = (V, E) दिया गया है, जहाँ V कोने हैं और E किनारे हैं, तो यह शून्य होगा यदि किनारों की संख्या E शून्य है।
यहाँ शून्य ग्राफ का एक उदाहरण दिया गया है:
तुच्छ ग्राफ
एक ग्राफ डेटा संरचना को तुच्छ माना जाता है यदि इसमें केवल एक शीर्ष या नोड मौजूद हो तथा कोई किनारा न हो।
यहाँ ट्रिवियल ग्राफ का एक उदाहरण दिया गया है:
मल्टी ग्राफ
किसी ग्राफ को मल्टीग्राफ तब कहा जाता है जब दो शीर्षों के बीच कई किनारे मौजूद हों, या शीर्ष पर एक लूप हो। ग्राफ डेटा स्ट्रक्चर में "लूप" शब्द का अर्थ है एक ही नोड या शीर्ष की ओर इशारा करने वाला किनारा। मल्टीग्राफ निर्देशित या अनिर्देशित हो सकता है।
मल्टी ग्राफ का एक उदाहरण यहां दिया गया है:
B से A तक दो किनारे हैं। इसके अलावा, शीर्ष E में एक स्व-लूप है। उपरोक्त ग्राफ एक निर्देशित ग्राफ है जिसमें किनारों पर कोई भार नहीं है।
पूरा ग्राफ
एक ग्राफ पूर्ण तब होता है जब प्रत्येक शीर्ष में अन्य सभी शीर्षों के साथ निर्देशित या अनिर्देशित किनारे हों।
मान लीजिए कि कुल शीर्षों की संख्या V है और प्रत्येक शीर्ष में ठीक V-1 किनारे हैं। तब, इस ग्राफ को पूर्ण ग्राफ कहा जाएगा। इस प्रकार के ग्राफ में, प्रत्येक शीर्ष किनारों के माध्यम से अन्य सभी शीर्षों से जुड़ा होता है।
यहां पांच शीर्षों वाले पूर्ण ग्राफ का एक उदाहरण दिया गया है:
आप चित्र में देख सकते हैं कि नोड्स की कुल संख्या पांच है, तथा सभी नोड्स में ठीक चार किनारे हैं।
कनेक्टेड ग्राफ
यदि हम किसी नोड या शीर्ष से शुरू करते हैं और आरंभिक नोड से सभी नोड्स की यात्रा करते हैं तो ग्राफ को कनेक्टेड ग्राफ कहा जाता है। इसके लिए, नोड्स या शीर्षों की प्रत्येक जोड़ी के बीच कम से कम एक किनारा होना चाहिए।
कनेक्टेड ग्राफ का एक उदाहरण यहां दिया गया है:
उपरोक्त "पूर्ण ग्राफ उदाहरण" ग्राफ का कुछ स्पष्टीकरण यहां दिया गया है:
- यह मानते हुए कि C और F के बीच कोई किनारा नहीं है, हम A से G तक यात्रा नहीं कर सकते। हालाँकि, C से F तक का किनारा हमें किसी भी नोड से किसी भी नोड तक यात्रा करने में सक्षम बनाता है।
- एक पूर्ण ग्राफ एक कनेक्टेड ग्राफ होता है क्योंकि हम दिए गए ग्राफ में एक नोड से किसी अन्य नोड पर जा सकते हैं।
चक्रीय ग्राफ
किसी ग्राफ को चक्रीय तब कहा जाता है जब ग्राफ में एक या एक से अधिक चक्र मौजूद हों।
यहाँ चक्रीय ग्राफ का एक उदाहरण दिया गया है:
यहाँ, शीर्ष A, B और C एक चक्र बनाते हैं।
एक ग्राफ के अन्दर अनेक चक्र हो सकते हैं।
निर्देशित चक्रीय ग्राफ (DAG)
यदि ग्राफ के अंदर कोई चक्र नहीं है तो ग्राफ को निर्देशित अचक्रीय ग्राफ या DAG कहा जाता है। DAG महत्वपूर्ण है जब ग्राफ के अंदर कोई चक्र नहीं है। टोपोलॉजिकल सॉर्ट या निष्पादन क्रम ढूँढना। DAG शेड्यूलिंग सिस्टम बनाने या संसाधनों की निर्भरता को स्कैन करने आदि के लिए भी महत्वपूर्ण है। हालाँकि, ऊपर दिए गए ग्राफ़ में कोई चक्र नहीं है।
यहाँ निर्देशित अचक्रीय ग्राफ (DAG) का एक सरल उदाहरण दिया गया है:
चक्र ग्राफ
साइकिल ग्राफ चक्रीय ग्राफ जैसा नहीं है। साइकिल ग्राफ में, प्रत्येक नोड में ठीक दो किनारे जुड़े होंगे, जिसका अर्थ है कि प्रत्येक नोड में ठीक दो डिग्री होंगे।
यहाँ चक्र ग्राफ का एक उदाहरण दिया गया है:
द्विदलीय ग्राफ
इस प्रकार के रेखाचित्र ये विशेष प्रकार के ग्राफ हैं जहां शीर्षों को दो सेटों को सौंपा जाता है।
द्विदलीय ग्राफ को निम्नलिखित नियम का पालन करना चाहिए:
- शीर्षों के दो सेट अलग-अलग होने चाहिए, अर्थात सभी शीर्षों को दो समूहों या सेटों में विभाजित किया जाना चाहिए।
- समान सेट शीर्षों को कोई किनारा नहीं बनाना चाहिए।
यूलर ग्राफ
ग्राफ डेटा संरचनाओं को यूलर ग्राफ माना जाता है यदि सभी शीर्षों की डिग्री सम संख्या वाली हो। शीर्षों की डिग्री शब्द का अर्थ है किसी विशेष शीर्ष की ओर इंगित करने वाले या उससे बाहर की ओर इंगित करने वाले किनारों की संख्या।
यहाँ यूलर ग्राफ का एक उदाहरण दिया गया है:
सभी शीर्षों की डिग्री सम है। शीर्ष A, D, E, और H की डिग्री दो है। यहाँ, नोड C की डिग्री चार है, जो सम है।
हैमिल्टन ग्राफ
हैमिल्टन ग्राफ एक कनेक्ट ग्राफ है, जहाँ आप एक ही नोड पर दोबारा आए बिना या एक ही किनारे का उपयोग किए बिना किसी दिए गए शीर्ष से सभी शीर्षों पर जा सकते हैं। इस तरह के कनेक्टेड ग्राफ को "हैमिल्टन ग्राफ" के रूप में जाना जाता है। जिस पथ पर आप यह सत्यापित करने के लिए जाते हैं कि दिया गया ग्राफ हैमिल्टन ग्राफ है या नहीं, उसे हैमिल्टनियन पथ के रूप में जाना जाता है।
हैमिल्टन का एक सरल ग्राफ उदाहरण यहां दिया गया है:
इस छवि में, हम ऊपर दिए गए ग्राफ़ में किसी भी नोड से सभी शीर्षों पर जा सकते हैं। पथों में से एक हो सकता है एडीसीएचबीईहैमिल्टन चक्र को खोजना भी संभव है। हैमिल्टन चक्र एक ही शीर्ष पर शुरू और समाप्त होता है। इसलिए, हैमिल्टन चक्र होगा एडीसीएचबीईए.