हम प्रसिद्ध खेल सांप और सीढ़ी के बारे में जानते हैं। इस गेम में कुछ कमरे बोर्ड पर मौजूद होते हैं, जिसमें रूम नंबर होता है। कुछ कमरे सीढ़ी या सांप से जुड़े हुए हैं। जब हमें सीढ़ी मिल जाती है, तो हम कुछ कमरों तक चढ़ सकते हैं और बिना क्रम में आगे बढ़े गंतव्य के करीब पहुंच सकते हैं। इसी तरह, जब हमें कोई

टारजन के एल्गोरिथम का उपयोग निर्देशित ग्राफ के दृढ़ता से जुड़े घटकों को खोजने के लिए किया जाता है। इस एल्गोरिथम को लागू करने के लिए इसे केवल एक DFS ट्रैवर्सल की आवश्यकता है। डीएफएस ट्रैवर्सल का उपयोग करके हम जंगल के डीएफएस पेड़ को ढूंढ सकते हैं। DFS ट्री से, दृढ़ता से जुड़े हुए घटक पाए जाते हैं।

निर्देशित चक्रीय ग्राफ के लिए टोपोलॉजिकल छँटाई शीर्षों का रैखिक क्रम है। निर्देशित ग्राफ़ के प्रत्येक किनारे U-V के लिए, शीर्ष u क्रम में vertex v से पहले आएगा। जैसा कि हम जानते हैं कि स्रोत शीर्ष गंतव्य शीर्ष के बाद आएगा, इसलिए हमें पिछले तत्वों को संग्रहीत करने के लिए एक स्टैक का उपयोग करने की

फोर्ड-फुलकर्सन एल्गोरिथम का उपयोग किसी दिए गए ग्राफ में प्रारंभ शीर्ष से सिंक शीर्ष तक अधिकतम प्रवाह का पता लगाने के लिए किया जाता है। इस ग्राफ में हर किनारे की क्षमता है। स्रोत और सिंक नाम के दो शीर्ष दिए गए हैं। स्रोत शीर्ष में सभी बाहरी किनारे हैं, कोई अंदरूनी किनारा नहीं है, और सिंक में सभी अंदर

संक्रमणीय क्लोजर इसे एक ग्राफ के वर्टेक्स यू से वर्टेक्स वी तक पहुंचने के लिए रीचैबिलिटी मैट्रिक्स है। एक ग्राफ दिया गया है, हमें एक शीर्ष v खोजना है जो सभी शीर्ष युग्मों (u, v) के लिए दूसरे शीर्ष u से पहुंचा जा सकता है। अंतिम मैट्रिक्स बूलियन प्रकार है। जब वर्टेक्स u से वर्टेक्स v के लिए मान

एक ग्राफ दिया गया है; हमें जांचना है कि दिया गया ग्राफ स्टार ग्राफ है या नहीं। ग्राफ को पार करते हुए, हमें यह पता लगाना है कि शीर्षों की संख्या एक है, और शीर्षों की संख्या, जिनकी डिग्री n-1 है। (यहाँ n दिए गए ग्राफ़ में शीर्षों की संख्या है)। जब डिग्री 1 वाले शीर्षों की संख्या n-1 है और डिग्री (n-1

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

इस समस्या में अलग-अलग बॉक्स का एक सेट दिया गया है, अलग-अलग बॉक्स के लिए लंबाई, चौड़ाई और चौड़ाई अलग-अलग हो सकती है। हमारा काम इन बक्सों का ढेर ढूंढना है, जिनकी ऊंचाई ज्यादा से ज्यादा हो। हम अपनी इच्छानुसार किसी भी बॉक्स को घुमा सकते हैं। लेकिन बनाए रखने का एक नियम है। कोई एक बॉक्स को दूसरे बॉक्स पर

यह पता लगाने के लिए कि अप्रत्यक्ष ग्राफ में कोई चक्र है या नहीं, हम दिए गए ग्राफ के लिए DFS ट्रैवर्सल का उपयोग करेंगे। प्रत्येक देखे गए शीर्ष v के लिए, जब हमें कोई आसन्न शीर्ष u मिलता है, जैसे कि आप पहले ही जा चुके हैं, और u शीर्ष v का जनक नहीं है। तब एक चक्र का पता लगाया जाता है। हम मान लेंगे क

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

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

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

Fleurys Algorithm का उपयोग दिए गए ग्राफ से यूलर पथ या यूलर सर्किट को प्रदर्शित करने के लिए किया जाता है। इस एल्गोरिथम में, एक किनारे से शुरू होकर, यह पिछले कोने को हटाकर अन्य आसन्न कोने को स्थानांतरित करने का प्रयास करता है। इस ट्रिक का उपयोग करके, प्रत्येक चरण में यूलर पथ या सर्किट को खोजने के लिए

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

एक भारित निर्देशित चक्रीय ग्राफ दिया गया है। एक अन्य स्रोत शीर्ष भी प्रदान किया गया है। अब हमें ग्राफ में आरंभिक नोड से अन्य सभी शीर्षों तक की सबसे लंबी दूरी ज्ञात करनी है। हमें टोपोलॉजिकल सॉर्टिंग तकनीक में नोड्स को सॉर्ट करने की आवश्यकता है, और टोपोलॉजिकल सॉर्ट को स्टैक में संग्रहीत करने के ब

एक ग्राफ को द्विदलीय ग्राफ कहा जाता है, जब उस ग्राफ के शीर्षों को दो स्वतंत्र सेटों में इस तरह विभाजित किया जा सकता है कि ग्राफ का प्रत्येक किनारा या तो पहले सेट से शुरू होता है और समाप्त होता है दूसरा सेट, या दूसरे सेट से शुरू होता है, पहले सेट से जुड़ा होता है, दूसरे शब्दों में, हम कह सकते हैं कि

एक भारित निर्देशित चक्रीय ग्राफ दिया गया है। एक अन्य स्रोत शीर्ष भी प्रदान किया गया है। अब हमें ग्राफ में आरंभिक नोड से अन्य सभी शीर्षों तक की न्यूनतम दूरी ज्ञात करनी है। छोटी दूरी का पता लगाने के लिए, हम नकारात्मक वजन वाले ग्राफ के लिए बेलमैन-फोर्ड जैसे अन्य एल्गोरिदम का उपयोग कर सकते हैं, सकारात्

द्विपक्षीय मिलान एक ग्राफ में किनारों का एक सेट है जिसे इस तरह से चुना जाता है, कि उस सेट में कोई भी दो किनारे एक समापन बिंदु साझा नहीं करेंगे। अधिकतम मिलान किनारों की अधिकतम संख्या से मेल खा रहा है। जब अधिकतम मिलान मिल जाता है, तो हम दूसरा किनारा नहीं जोड़ सकते। यदि अधिकतम मिलान वाले ग्राफ़ में

इस समस्या में, 2D समतल पर n बिंदुओं का एक सेट दिया जाता है। इस समस्या में हमें उन बिंदुओं का युग्म खोजना होता है, जिनकी दूरी न्यूनतम हो। इस समस्या को हल करने के लिए, हमें बिंदुओं को दो हिस्सों में विभाजित करना होगा, उसके बाद दो बिंदुओं के बीच की सबसे छोटी दूरी की गणना पुनरावर्ती तरीके से की जाती है

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