💔 👨🏼‍🏫 🤬 सबसे छोटे के लिए मायने रखता है: बीएफएस 👩🏾‍🏭 🈸 📐

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

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

ग्राफ़ के एक शीर्ष से दूसरे तक एक पथ खोजने के लिए आवश्यक है, और किनारों की संख्या में पथ न्यूनतम होना चाहिए।

एल्गोरिथम विवरण

मैं सहज रूप से मूल एक से दूरी बढ़ाने के क्रम में ग्राफ के कोने पर विचार करना चाहता हूं - जैसा कि आंकड़े में दिखाया गया है।
हम सभी सिरों को तीन सेटों में विभाजित करते हैं:

पूरी तरह से संसाधित कोने (शुरू में सेट खाली है, यह उस काले रंग में दर्शाया गया है)
वह दूरी जिसके लिए दूरी ज्ञात है (शुरू में सेट में केवल एक शीर्ष है - प्रारंभिक एक, आकृति में ग्रे में संकेत दिया गया है)
वे लक्षण जिनके बारे में कुछ भी पता नहीं है (आरंभ में - प्रारंभिक एक को छोड़कर सभी कोने आंकड़े में सफेद रंग में दर्शाए गए हैं)

जाहिर है, जैसे ही सभी कोने काले होते हैं, एल्गोरिथ्म पूरा हो जाता है। हम कतार में सभी ग्रे कोने को संग्रहीत करेंगे और निम्नलिखित संपत्ति बनाए रखेंगे: कतार में सभी ग्रे कोने की दूरी जिस क्रम में वे झूठ बोलते हैं वह नीरस रूप से कम नहीं होती है।
हमें कतार से पहला शीर्ष प्राप्त होता है (हम इसे v द्वारा दर्शाते हैं)। अपने प्रत्येक पड़ोसी w के लिए, दो विकल्पों में से एक संभव है:

w एक ब्लैक या ग्रे टॉप है। इस मामले में, हमें कोई नई जानकारी प्राप्त नहीं होती है।
w सफेद चोटी है। फिर उससे दूरी d (w) = d (v) + 1. है और जब से हम दूरी जानते हैं, w एक ग्रे चोटी बन जाता है

कम से कम एक ग्रे वर्टेक्स होने तक दोहराएं।

कार्यान्वयन

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

BFS

void BFS() { queue<int> q; // :      q.push(start); d[start] = 0; mark[start] = 1; //   -     while (!q.empty()) { //     int v = q.front(); q.pop(); //      for (int i = 0; i < (int)edges[v].size(); ++i) { //    if (mark[edges[v][i]] == 0) { //    d[edges[v][i]] = d[v] + 1; //     mark[edges[v][i]] = 1; q.push(edges[v][i]); } } } }

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

प्रारंभिक एक से उपलब्ध किसी भी शीर्ष v पर विचार करें। पी [0] = प्रारंभ करें, पी [1], ..., पी [के] = v प्रारंभिक शीर्ष से शीर्ष तक सबसे छोटा मार्ग है। तब एल्गोरिथ्म के संचालन के परिणामस्वरूप मूल्य d [v] = k प्राप्त होता है।
सबूत:

d [v] ≤ के
- आधार: वर्टेक्स पी [0] = प्रारंभ एल्गोरिथ्म द्वारा दौरा किया गया है, और डी [पी [0]] = 0
- अनुमान: वर्टेक्स p [i - 1] एल्गोरिथ्म द्वारा दौरा किया गया है, और d [p [i]] ver i
- चरण: जब शीर्ष p [i - 1] (या शायद पहले) पर विचार करते हैं, तो हम किनारे पर विचार करेंगे जो कि शीर्ष p [i] के लिए होगा। इस प्रकार, d [p [i]] [i
d [v] ≥ के
मान लीजिए कि d [v] <k शीर्ष v पर विचार करें; वर्टेक्स, जब माना जाता है, वर्टेक्स वी को ग्रे रंग दिया गया था (हम इसे डब्ल्यू द्वारा दर्शाते हैं); वर्टेक्स, जब जांच की गई, तो वर्टेक्स डब्ल्यू को ग्रे रंग में चित्रित किया गया था; ... शीर्ष प्रारंभ प्रारंभ। इस क्रम में प्रत्येक दो पड़ोसी कोने एल्गोरिदम के निर्माण के अनुसार एक किनारे से जुड़े हुए हैं। इस प्रकार, हमने शीर्ष से शुरू होने वाले मार्ग को कश्मीर की तुलना में छोटी लंबाई के v से शुरू किया - एक विरोधाभास, इसलिए, d [v] path k

एल्गोरिथ्म की जटिलता

प्रत्येक किनारे और प्रत्येक शीर्ष के लिए, एल्गोरिथ्म निरंतर क्रियाएं करता है, इसलिए, समय जटिलता O (V + E) है।
कतार में एक साथ संग्रहीत शीर्षकों की अधिकतम संख्या V है, अर्थात, उपयोग की जाने वाली मेमोरी की अधिकतम मात्रा O (V) है।

एक निष्कर्ष के बजाय

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