डेटा स्ट्रक्चर्स और एल्गोरिदम · ग्राफ़्स

ग्राफ़ ट्रैवर्सल (BFS और DFS)

हर पहुँच योग्य वर्टेक्स को या तो लेवल दर लेवल (BFS) या पहले गहराई में जाकर (DFS) विज़िट करना।

ग्राफ़ ट्रैवर्सल (BFS और DFS) पर लेसन शुरू करें

पहले सीखें

• ग्राफ़ रिप्रेजेंटेशन: किसी ग्राफ़ के वर्टिसेज़ और एज को एडजेसेंसी मैट्रिक्स या एडजेसेंसी लिस्ट के तौर पर स्टोर करना।
• स्टैक और क्यू: दो सीमित-एक्सेस क्रम, लास्ट-इन-फ़र्स्ट-आउट और फ़र्स्ट-इन-फ़र्स्ट-आउट।

आगे

• टोपोलॉजिकल सॉर्ट: एक डायरेक्टेड एसाइक्लिक ग्राफ़ के वर्टिसेज़ को इस तरह क्रमबद्ध करना कि हर एज आगे की ओर इशारा करे।
• डाइक्स्ट्रा एल्गोरिदम: जब कोई एज वेट नेगेटिव न हो, तब एक वर्टेक्स से बाकी सबतक सबसे सस्ता रास्ता ढूंढना।
• बेलमैन-फ़ोर्ड एल्गोरिदम: सबसे छोटे रास्ते ढूंढना जो तब भी काम करता है जब कुछ एज वेट नेगेटिव हों, बस स्पीड की कीमत पर।

संबंधित टॉपिक्स

• टोपोलॉजिकल सॉर्ट: एक डायरेक्टेड एसाइक्लिक ग्राफ़ के वर्टिसेज़ को इस तरह क्रमबद्ध करना कि हर एज आगे की ओर इशारा करे।
• बैकट्रैकिंग: एक विकल्प आज़माना, रिकर्स करना, और अगर वह कहीं नहीं ले जाता तो उसे पलटना, ताकि सभी संभावनाएं देखी जा सकें।