अनुशंसित, 2024

संपादक की पसंद

ट्री और ग्राफ में अंतर

ट्री और ग्राफ गैर-रेखीय डेटा संरचना की श्रेणी में आते हैं जहां पेड़ एक पदानुक्रमित संरचना में नोड्स के बीच संबंध का प्रतिनिधित्व करने का एक बहुत ही उपयोगी तरीका प्रदान करता है और ग्राफ एक नेटवर्क मॉडल का अनुसरण करता है। पेड़ और ग्राफ को इस तथ्य से विभेदित किया जाता है कि एक पेड़ की संरचना को जुड़ा होना चाहिए और कभी भी लूप नहीं हो सकता है जबकि ग्राफ में इस तरह के प्रतिबंध नहीं हैं।

एक गैर-रैखिक डेटा संरचना में उन तत्वों का एक संग्रह होता है जो एक विमान पर वितरित किए जाते हैं, जिसका अर्थ है कि तत्वों के बीच ऐसा कोई क्रम नहीं है क्योंकि यह एक रैखिक डेटा संरचना में मौजूद है।

तुलना चार्ट

तुलना के लिए आधारपेड़ग्राफ़
पथदो कोने के बीच केवल एक।एक से अधिक पथ की अनुमति है।
रूट नोडयह एक रूट नोड है।ग्राफ में रूट नोड नहीं है।
लूप्सकोई लूप की अनुमति नहीं है।ग्राफ में लूप हो सकते हैं।
जटिलताकम जटिलतुलनात्मक रूप से अधिक जटिल
ट्रैवर्सल तकनीकप्री-ऑर्डर, इन-ऑर्डर और पोस्ट-ऑर्डर।चौड़ाई-पहली खोज और गहराई-पहली खोज।
किनारों की संख्याएन -1 (जहां n नोड्स की संख्या है)परिभाषित नहीं
मॉडल प्रकारश्रेणीबद्धनेटवर्क

वृक्ष की परिभाषा

एक पेड़ आमतौर पर नोड्स के रूप में कहा जाने वाला डेटा आइटम का एक सीमित संग्रह है। जैसा कि ऊपर उल्लेख किया गया है कि एक पेड़ एक गैर-रैखिक डेटा संरचना है जो सॉर्ट किए गए क्रम में डेटा आइटम की व्यवस्था करता है। इसका उपयोग विभिन्न डेटा तत्वों के बीच एक पदानुक्रमित संरचना दिखाने के लिए किया जाता है और डेटा को उन शाखाओं में व्यवस्थित करता है जो जानकारी से संबंधित हैं। एक पेड़ में एक नए किनारे को जोड़ने से लूप या सर्किट का निर्माण होता है।

कई प्रकार के पेड़ हैं जैसे कि एक बाइनरी ट्री, बाइनरी सर्च ट्री, एवीएल ट्री, थ्रेडेड बाइनरी ट्री, बी-ट्री, आदि। डेटा कम्प्रेशन, फाइल स्टोरेज, अंकगणित की अभिव्यक्ति में हेरफेर और गेम ट्री, पेड़ के कुछ अनुप्रयोग हैं। डेटा संरचना।

पेड़ के गुण:

  • पेड़ की जड़ के रूप में जाना जाता है पेड़ के शीर्ष पर नामित नोड है।
  • शेष डेटा आइटम को उप-विभाजन में विभाजित किया जाता है जो उप-प्रकार के रूप में संदर्भित होता है।
  • पेड़ का नीचे की ओर ऊंचाई में विस्तार किया गया है।
  • एक पेड़ जुड़ा होना चाहिए जिसका अर्थ है कि एक रूट से दूसरे सभी नोड्स के लिए एक रास्ता होना चाहिए।
  • इसमें कोई लूप नहीं होता है।
  • एक पेड़ में n-1 किनारे होते हैं।

पेड़ों से जुड़े विभिन्न शब्द हैं जैसे टर्मिनल नोड, किनारे, स्तर, डिग्री, गहराई, जंगल, आदि। उन शर्तों में से कुछ नीचे वर्णित हैं।

  • एज - एक लाइन जो दो नोड्स को जोड़ती है।
  • स्तर - एक पेड़ को इस तरह से स्तरों में विभाजित किया जाता है कि रूट नोड स्तर 0. पर है। फिर, इसके तत्काल बच्चे 1 स्तर पर हैं, और इसके तत्काल बच्चे स्तर 2 पर हैं और इसलिए टर्मिनल या लीफ नोड तक।
  • डिग्री - किसी दिए गए पेड़ में एक नोड के उपप्रकारों की संख्या है।
  • गहराई - यह किसी दिए गए पेड़ में किसी भी नोड का अधिकतम स्तर है और इसे ऊंचाई के रूप में भी जाना जाता है।
  • टर्मिनल नोड - उच्चतम स्तर नोड टर्मिनल नोड है जबकि टर्मिनल और रूट नोड को छोड़कर अन्य नोड को गैर-टर्मिनल नोड के रूप में जाना जाता है।

ग्राफ की परिभाषा

ग्राफ एक गणितीय गैर-रेखीय डेटा संरचना भी है जो विभिन्न प्रकार की भौतिक संरचना का प्रतिनिधित्व कर सकता है। इसमें कोने (या नोड्स) का एक समूह होता है और किनारों का सेट होता है जो दो कोने को जोड़ता है। ग्राफ पर कार्यक्षेत्रों को बिंदु या मंडलियों के रूप में दर्शाया जाता है और किनारों को चाप या रेखाखंडों के रूप में दिखाया जाता है। एक किनारे को E (v, w) द्वारा दर्शाया गया है, जहाँ v और w शीर्ष रेखाओं के जोड़े हैं। सर्किट या कनेक्टेड ग्राफ से एक किनारे को हटाने से एक सबग्राफ बनता है जो एक पेड़ है।

रेखांकन को विभिन्न श्रेणियों में वर्गीकृत किया जाता है जैसे कि निर्देशित, गैर-निर्देशित, जुड़ा हुआ, गैर-जुड़ा हुआ, सरल और बहु-ग्राफ़। कंप्यूटर नेटवर्क, ट्रांसपोर्टेशन सिस्टम, सोशल नेटवर्क ग्राफ, इलेक्ट्रिकल सर्किट और प्रोजेक्ट प्लानिंग, ग्राफ डेटा स्ट्रक्चर के कुछ एप्लिकेशन हैं। यह PERT (कार्यक्रम मूल्यांकन और समीक्षा तकनीक) और CPM (महत्वपूर्ण पथ विधि) के रूप में नामित प्रबंधन तकनीक में भी कार्यरत है जिसमें ग्राफ संरचना का विश्लेषण किया जाता है।

एक ग्राफ के गुण:

  • एक ग्राफ में एक शीर्ष किनारों का उपयोग करके किसी भी अन्य कोने से जुड़ा जा सकता है।
  • एक किनारे को अप्रत्यक्ष या निर्देशित किया जा सकता है।
  • एक किनारे का वजन किया जा सकता है।

ग्राफ में भी हम विभिन्न पदों का उपयोग करते हैं जैसे कि आसन्न कोने, पथ, चक्र, डिग्री, जुड़ा हुआ ग्राफ, पूरा ग्राफ, भारित ग्राफ, आदि। आइए इन कुछ शब्दों को समझें।

  • समीपस्थ कोने - एक कगार शीर्ष क के समीप ख है अगर एक धार (ए, बी) या (बी, ए) है।
  • पथ - एक यादृच्छिक शीर्ष w से एक पथ कोने का एक आसन्न अनुक्रम है।
  • साइकिल - यह एक ऐसा मार्ग है जहाँ पहला और अंतिम कोने समान हैं।
  • डिग्री - यह एक शीर्ष पर कई किनारों की घटना है।
  • कनेक्टेड ग्राफ - यदि किसी यादृच्छिक वर्टेक्स से किसी अन्य वर्टेक्स तक का रास्ता मौजूद है, तो उस ग्राफ को कनेक्टेड ग्राफ के रूप में जाना जाता है।

पेड़ और ग्राफ के बीच महत्वपूर्ण अंतर

  1. एक पेड़ में किन्हीं दो सिरों के बीच केवल एक ही पथ मौजूद होता है जबकि एक ग्राफ में नोड्स के बीच अप्रत्यक्ष और द्विदिश पथ हो सकते हैं।
  2. पेड़ में, एक मूल नोड होता है, और प्रत्येक बच्चे के पास केवल एक माता-पिता हो सकते हैं। जैसा कि, एक ग्राफ में, रूट नोड की कोई अवधारणा नहीं है।
  3. एक पेड़ में लूप और सेल्फ-लूप नहीं हो सकते हैं जबकि ग्राफ में लूप और सेल्फ-लूप हो सकते हैं।
  4. रेखांकन अधिक जटिल हैं क्योंकि इसमें लूप और स्व-लूप हो सकते हैं। इसके विपरीत, ग्राफ के मुकाबले पेड़ सरल होते हैं।
  5. पूर्व-आदेश, इन-ऑर्डर और पोस्ट-ऑर्डर तकनीकों का उपयोग करके पेड़ का पता लगाया जाता है। दूसरी ओर, ग्राफ ट्रैवर्सल के लिए, हम बीएफएस (चौड़ाई पहले खोज) और डीएफएस (गहराई पहले खोज) का उपयोग करते हैं।
  6. एक पेड़ में एन -1 किनारे हो सकते हैं। इसके विपरीत, ग्राफ में, किनारों की कोई पूर्वनिर्धारित संख्या नहीं होती है, और यह ग्राफ पर निर्भर करता है।
  7. एक पेड़ में एक पदानुक्रमित संरचना होती है जबकि ग्राफ में एक नेटवर्क मॉडल होता है।

निष्कर्ष

ग्राफ और ट्री गैर-रैखिक डेटा संरचना है जिसका उपयोग विभिन्न जटिल समस्याओं को हल करने के लिए किया जाता है। ग्राफ एक कोने और किनारों का एक समूह होता है, जहाँ एक किनारे को जोड़े के जोड़े से जोड़ा जाता है, जबकि एक पेड़ को न्यूनतम जुड़ा हुआ ग्राफ़ माना जाता है, जिसे कनेक्ट होना चाहिए और लूप से मुक्त होना चाहिए।

Top