डीएफएस <कोड>डीएफएस
डेप्थ फ़र्स्ट सर्च ( DFS) ग्राफ़ पर मुख्य एल्गोरिदम में से एक है। एल्गोरिदम O(N + M) में चलता है।
एल्गोरिदम
शुरू करने के लिए हम ऊपर से शुरू करते हैं, इस चोटी के बच्चों पर विचार करते हैं, और अगर हमने कभी प्रवेश नहीं किया है, तो हम उनसे DFS शुरू करते हैं।
|
डीएफएस <कोड>डीएफएस
डेप्थ फ़र्स्ट सर्च ( DFS) ग्राफ़ पर मुख्य एल्गोरिदम में से एक है। एल्गोरिदम O(N + M) में चलता है।
एल्गोरिदम
शुरू करने के लिए हम ऊपर से शुरू करते हैं, इस चोटी के बच्चों पर विचार करते हैं, और अगर हमने कभी प्रवेश नहीं किया है, तो हम उनसे DFS शुरू करते हैं।
|
द्विपक्षीय ग्राफ
द्विपक्षीय ग्राफ़ - एक ग्राफ़ जिसके शीर्षों को दो सेटों में विभाजित किया जा सकता है ताकि प्रत्येक किनारा जोड़े को जोड़े विभिन्न सेटों से शिखर।
अक्सर द्विपक्षीय ग्राफ़ के संदर्भ में, रंगों कोने की अवधारणा का उपयोग किया जाता है। किसी ग्राफ़ को दो भागों में विभाजित करना रंग इसके शीर्षों को दो अलग-अलग रंगों से रंगना कहा जाता है। प्रत्येक किनारे को एक अलग रंग के शीर्षों को जोड़ना चाहिए।
<कोड>डीएफएस।
एल्गोरिदम
हम एक मनमाने शीर्ष से पेंटिंग शुरू करते हैं, जिसे हम मनमाने रंग से पेंट करते हैं।
प्रत्येक किनारे से गुजरते समय, अगले शीर्ष को विपरीत रंग में पेंट करें।
यदि, पड़ोसी शीर्षों पर पुनरावृति करते समय, हमें एक ऐसा शीर्ष मिलता है जो पहले से ही उसी रंग में रंगा हुआ है जिस रंग में वर्तमान है, तो ग्राफ़ में एक विषम चक्र है, जिसका अर्थ है कि यह द्विदलीय नहीं है।
|
एल्गोरिदम को इस प्रकार वर्णित किया जा सकता है:
n शीर्षों और m किनारों वाला एक निर्देशित ग्राफ़ दिया गया है। इसके शीर्षों को इस तरह से फिर से क्रमांकित करना आवश्यक है कि प्रत्येक किनारा कम संख्या वाले शीर्ष से उच्च संख्या वाले शीर्ष की ओर जाता है।
दूसरे शब्दों में, ग्राफ के सभी किनारों द्वारा दिए गए क्रम के अनुरूप शीर्षों (सांस्थितिक क्रम) का क्रमचय खोजना आवश्यक है।
हम गहराई-प्रथम खोज (dfs(v)) का उपयोग करेंगे
यदि हम \(dfs(v)\) से बाहर निकलते समय किसी सूची की शुरुआत में अपना शीर्ष जोड़ते हैं, तो अंत में इस सूची में आपको एक टोपोलॉजिकल सॉर्ट मिलता है।
इस प्रकार, वांछित टोपोलॉजिकल सॉर्ट — इसे बाहर निकलने के समय के अवरोही क्रम में क्रमबद्ध किया गया है।
|