🐴 🌼 🚭 सबसे छोटे के लिए मायने रखता है: डीएफएस ☝🏻 😜 👨‍💻

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

समस्या का बयान

यह "कच्चे" भूलभुलैया पर काम करने के लिए असुविधाजनक है (कम से कम ग्राफ़ का परिचय प्रिय होगा), इसलिए हम इसे विभाजन से जुड़े "कमरों" में विभाजित करेंगे। लगभग दाईं ओर की आकृति में दिखाया गया है।

अब कार्य ने यह रूप ले लिया है: कई कमरे हैं, आप उनमें से कुछ के बीच में जा सकते हैं। कमरा ए से कमरे बी तक का रास्ता खोजना आवश्यक है।
ग्राफ सिद्धांत में, "कमरे" को कोने कहा जाता है; उनके बीच के "बदलाव" को किनारे कहा जाता है। कमरा A प्रारंभिक शिखर है, कमरा B अंत है।
चित्र में दाईं ओर का ग्राफ ग्राफ सिद्धांत में कुछ हद तक सामान्य रूप में फिर से लिखा जा सकता है:

यहां, अंडाकार कोने (या कमरे) हैं, लाइनें किनारों (या उनके बीच संक्रमण) हैं। वर्टेक्स 1 प्रारंभिक है, वर्टेक्स 12 अंतिम है।

और हम इस समस्या को कैसे हल करेंगे?

पहली चीज जो मैं करना चाहता हूं वह है एक संपूर्ण खोज लिखना: समय के प्रत्येक क्षण में हम कुछ चरम पर हैं, और हम इसे सभी पड़ोसियों के पास जाते हैं:

क्रूर बल

यह माना जाता है कि ग्राफ वेक्टर में संग्रहीत है <वेक्टर <int> किनारों सरणी, किनारों के साथ [v] जिसमें सभी कोने की संख्या होती है जिसमें v से एक किनारे होता है। यह भी माना जाता है कि अंतिम चर संख्या वैश्विक चर खत्म में संग्रहीत है।

void travel(int v) { if (v == finish) // ,   { cout << "Hooray! The path was found!\n"; return; } for (int i = 0; i < (int)edges[v].size(); ++i) //    { travel(edges[v][i]); //    } }

काश, यह कोड पहले से ही तीन सिरों के ग्राफ पर काम नहीं करता है, जिसमें प्रत्येक शीर्ष किनारों से जुड़ा हुआ है - जब शीर्ष 1 से शुरू होता है, तो हम शीर्ष 2 पर जाते हैं, इसे शीर्ष से 1 तक, फिर से वर्टेक्स 2, ... और कुछ बिंदु पर, एक स्टैक ओवरफ्लो के कारण प्रोग्राम बस दुर्घटनाग्रस्त हो जाता है।

क्या करें?

समाधान जो तुरंत दिमाग में आता है, उसके प्रवेश द्वार पर प्रत्येक शीर्ष को चिह्नित करना है, और पहले से ही चिह्नित कोने में कभी नहीं जाना है - यह गहराई से चलना है:

डीएफएस

 void DFS(int v) { if (mark[v] != 0) //     ,      { return; } mark[v] = 1; // ,     if (v == finish) // ,   { cout << "Hooray! The path was found!\n"; return; } for (int i = 0; i < (int)edges[v].size(); ++i) //    { DFS(edges[v][i]); //    } }

और तो क्या?

हां, कार्यक्रम किसी तरह चला गया, लेकिन यह कैसे निर्धारित किया जाए?
हम प्रत्येक शीर्ष के लिए याद करेंगे, जहां हम एक विशेष सरणी में पहले से आए थे।

डीएफएस

 void DFS(int v, int from) { if (mark[v] != 0) //     ,      { return; } mark[v] = 1; // ,     prior[v] = from; // ,   if (v == finish) // ,   { cout << "Hooray! The path was found!\n"; return; } for (int i = 0; i < (int)edges[v].size(); ++i) //    { DFS(edges[v][i], v); //    } }

तब मार्ग बहाल करने का कार्य तुच्छ होगा:

get_path

 vector<int> get_path() { vector<int> ans; for (int v = finish; v != start; v = prior[v]) //        { ans.push_back(v); //   } ans.push_back(start); reverse(ans.begin(), ans.end()); //   return ans; }

यह काम क्यों करता है?

एल्गोरिथ्म हमेशा शीर्ष पर एक रास्ता खोजेगा, अगर यह मौजूद है। सबूत:
एक मनमाना ग्राफ़ G के लिए:
बेस। एल्गोरिथ्म 1 से अधिक वर्टेक्स से रास्तों को सही तरीके से ढूंढता है (प्रारंभिक शीर्ष से उसके लिए पथ समान है)।
अनुमान: एल्गोरिथम प्रारंभिक एक से k - 1 से अधिक नहीं की दूरी पर स्थित सभी चोटियों का दौरा करता है।
चरण: प्रारंभिक एक से दूरी k पर स्थित किसी भी शीर्ष v पर विचार करें। जाहिर है, यह एक किनारे से जुड़ा हुआ है जो प्रारंभिक एक से k - 1 की दूरी पर स्थित कुछ शीर्ष पर है - चलो इसे w कहते हैं। तो, हम शीर्ष पर जाएंगे जब वर्टेक्स डब्ल्यू देखते हैं।

एल्गोरिथ्म को कितने संसाधनों की आवश्यकता होती है?

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

गैर-पुनरावर्ती डीएफएस

किसी भी पुनरावर्ती एल्गोरिथ्म को गैर-पुनरावर्ती रूप में फिर से लिखा जा सकता है। यहाँ DFS के लिए कोड है:

डीएफएस

 void DFS() { stack<int> s; s.push(start); while (!s.empty()) { int v = s.top(); s.pop(); for (int i = 0; i < edges[v].size(); ++i) { if (mark[edges[v][i]] == 0) { s.push(edges[v][i]); mark[edges[v][i]] = 1; } } } }

आगे क्या है?

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

सबसे छोटे के लिए मायने रखता है: डीएफएस

समस्या का बयान

और हम इस समस्या को कैसे हल करेंगे?

क्या करें?

और तो क्या?

यह काम क्यों करता है?

एल्गोरिथ्म को कितने संसाधनों की आवश्यकता होती है?

गैर-पुनरावर्ती डीएफएस

आगे क्या है?

More articles: