डेटा संरचना में ग्राफ़ के प्रकार उदाहरणों के साथ
सारा चेन
⚡ स्मार्ट सारांश
डेटा संरचना में ग्राफ़, शीर्षों और किनारों के गैर-रैखिक संग्रह होते हैं जिन्हें संरचना के आधार पर निर्देशित, अनिर्देशित, भारित, चक्रीय, अचक्रीय, पूर्ण, संयोजित, द्विपक्षीय, यूलर और हैमिल्टन ग्राफ़ जैसे परिवारों में वर्गीकृत किया जाता है।
ग्राफ एक गैर-रेखीय डेटा संरचना है जिसमें शीर्ष और किनारे होते हैं। शीर्षों में जानकारी या डेटा होता है, और किनारे दो शीर्षों के बीच एक कड़ी के रूप में कार्य करते हैं।
नोड्स और किनारों की स्थिति के आधार पर ग्राफ कई प्रकार के हो सकते हैं। ग्राफ के कुछ महत्वपूर्ण प्रकार इस प्रकार हैं:
निर्देशित ग्राफ
निर्देशित ग्राफ के किनारों पर तीर के निशान होते हैं जो दिशा दर्शाते हैं। तीर का निशान यह निर्धारित करता है कि किनारा कहाँ इंगित करता है या कहाँ समाप्त होता है। निर्देशित ग्राफ का एक उदाहरण यहाँ दिया गया है।
निर्देशित ग्राफ
- हम नोड 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 की घात चार है, जो कि सम है।
हैमिल्टन ग्राफ
हैमिल्टन ग्राफ एक कनेक्टेड ग्राफ होता है, जिसमें किसी दिए गए वर्टेक्स से सभी वर्टेक्स तक बिना उसी नोड पर दोबारा जाए या उसी एज का उपयोग किए पहुंचा जा सकता है। इस प्रकार के कनेक्टेड ग्राफ को "हैमिल्टन ग्राफ" कहा जाता है। यह सत्यापित करने के लिए कि दिया गया ग्राफ हैमिल्टन ग्राफ है या नहीं, जिस पथ का अनुसरण किया जाता है, उसे हैमिल्टनियन पथ कहा जाता है। यहां हैमिल्टन ग्राफ का एक सरल उदाहरण दिया गया है:
इस छवि में, हम ऊपर दिए गए ग्राफ़ में किसी भी नोड से सभी शीर्षों पर जा सकते हैं। पथों में से एक हो सकता है एडीसीएचबीईहैमिल्टन चक्र खोजना भी संभव है। हैमिल्टन चक्र एक ही शीर्ष से शुरू और समाप्त होता है। इसलिए, हैमिल्टन चक्र होगा एडीसीएचबीईए.
