ग्राफ एक नॉन-लीनियर डेटा संरचना है। यह नोड्स का उपयोग करके डेटा का प्रतिनिधित्व करता है, और किनारों का उपयोग करके उनके संबंध। एक ग्राफ G के दो भाग होते हैं। वर्टेक्स, और एज। वर्टेक्स को सेट V द्वारा दर्शाया जाता है, और एज को सेट E के रूप में दर्शाया जाता है। इसलिए ग्राफ नोटेशन G(V,E) है। आइए एक उदाहरण देखें ताकि विचार मिल सके।
इस ग्राफ में, पांच वर्टेक्स और पांच एज हैं। एज डायरेक्टेड हैं। उदाहरण के लिए, यदि हम वर्टेक्स B और D को जोड़ने वाले एज को चुनते हैं, तो स्रोत वर्टेक्स B है और गंतव्य D है। इसलिए हम B से D जा सकते हैं लेकिन D से B नहीं जा सकते।
ग्राफ नॉन-लीनियर हैं, और इनकी कोई नियमित संरचना नहीं है। मेमोरी में ग्राफ को प्रतिनिधित्व करने के लिए, कुछ अलग स्टाइल हैं। ये स्टाइल हैं -
- एडजेसेंसी मैट्रिक्स प्रतिनिधित्व
- एज लिस्ट प्रतिनिधित्व
- एडजेसेंसी लिस्ट प्रतिनिधित्व
एडजेसेंसी मैट्रिक्स प्रतिनिधित्व
हम एडजेसेंसी मैट्रिक्स का उपयोग करके ग्राफ को प्रतिनिधित्व कर सकते हैं। दिया गया मैट्रिक्स एक एडजेसेंसी मैट्रिक्स है। यह एक बाइनरी, वर्ग मैट्रिक्स है और iवीं पंक्ति से jवें कॉलम तक, यदि एक एज है, तो उस स्थान को 1 के रूप में चिह्नित किया जाता है। जब हम एडजेसेंसी मैट्रिक्स का उपयोग करके अनडायरेक्टेड ग्राफ को प्रतिनिधित्व करने का प्रयास करेंगे, तो मैट्रिक्स सिमेट्रिक होगा।
एज लिस्ट प्रतिनिधित्व
ग्राफ को एक-आयामी ऐरे का उपयोग करके भी प्रतिनिधित्व किया जा सकता है। इसे एज लिस्ट कहा जाता है। इस प्रतिनिधित्व में पांच एज मौजूद हैं, प्रत्येक एज के लिए पहला तत्व स्रोत है और दूसरा गंतव्य है। अनडायरेक्टेड ग्राफ प्रतिनिधित्व के लिए एज लिस्ट में तत्वों की संख्या दोगुनी हो जाएगी।
एडजेसेंसी लिस्ट प्रतिनिधित्व
यह ग्राफ प्रतिनिधित्व का एक और प्रकार है। इसे एडजेसेंसी लिस्ट कहा जाता है। यह प्रतिनिधित्व लिंक्ड लिस्ट पर आधारित है। इस दृष्टिकोण में, प्रत्येक नोड नोड्स की एक सूची रखता है, जो उस वर्टेक्स के साथ सीधे जुड़े हुए हैं। सूची के अंत में, प्रत्येक नोड नल मानों से जुड़ा होता है ताकि यह बताया जा सके कि यह उस सूची का अंतिम नोड है।
