Module: गहराई से खोजें। डीएफएस


Problem

1/12

डीएफएस: शुरुआत (सी++)

Theory Click to read/hide

डीएफएस <कोड>डीएफएस
डेप्थ फ़र्स्ट सर्च (DFS) ग्राफ़ पर मुख्य एल्गोरिदम में से एक है। एल्गोरिदम O(N + M) में चलता है।
 
एल्गोरिदम
शुरू करने के लिए हम ऊपर से शुरू करते हैं, इस चोटी के बच्चों पर विचार करते हैं, और अगर हमने कभी प्रवेश नहीं किया है, तो हम उनसे DFS शुरू करते हैं।


Problem

एक ऐसी प्रक्रिया लिखें void dfs (int v) जो स्टार्ट वर्टेक्स S से एक अप्रत्यक्ष ग्राफ की गहराई को ट्रेस करता है और वर्टेक्स से शुरू होने वाले ट्रैवर्सल ऑर्डर में सभी वर्टिकल को आउटपुट करता है। S एक पंक्ति में एक रिक्ति द्वारा अलग किया गया।

पहली पंक्ति में तीन संख्याएँ हैं N  - ग्राफ़ में शीर्षों की संख्या, M - किनारों की संख्या, S - प्रारंभ शिखर। निम्नलिखित M पंक्तियों में, 2 चर Ui और Vi आपूर्ति की जाती हैं , ग्राफ किनारों का विवरण। इनपुट में सभी संख्याएं 1000 से अधिक नहीं हैं।

 DFS द्वारा ट्रैवर्सल के क्रम में सभी शीर्षों को आउटपुट करें।

उपरोक्त प्रोग्राम में, g[i][j] का अर्थ है कि i और j के शीर्षों के बीच एक किनारा है, और सरणी उपयोग किया गया हम चिन्हित करते हैं कि क्या हम इस चोटी पर गए हैं।