कोडिंग साक्षात्कार की तैयारी · पाठ

Deque के साथ 0-1 BFS

जब weights 0 या 1 हों, तब shortest paths खोजें

पाठ 2, कुल 4 में से13 चरण

Deque के साथ 0-1 BFS, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

एक विशेष प्रकार का ग्राफ़

कुछ ग्राफ़ में किनारों के भार केवल 0 या 1 होते हैं। ऐसे मामलों में आप एक सरल और तेज़ युक्ति से डिज्क्स्ट्रा से बेहतर प्रदर्शन कर सकते हैं।

0-1 BFS से परिचय

0-1 BFS 0/1-भारित ग्राफ़ पर रैखिक समय में सबसे छोटे पथ खोजता है, और इसमें न हीप चाहिए, न log कारक।

उपकरण: एक डेक

हीप के बदले डेक का उपयोग करें—ऐसी कतार जिसमें आगे और पीछे, दोनों ओर से प्रविष्टि डाल और निकाल सकते हैं।

from collections import deque
dq = deque([src])

मूल विचार

0-भार वाला किनारा दूरी को वही रखता है, जबकि 1-भार वाला किनारा उसमें एक जोड़ता है। डेक दोनों समूहों को क्रम में रखता है।

शून्य-भार वाले किनारों के लिए आगे

क्या आप 0-भार वाले किनारे से जा रहे हैं? पड़ोसी को appendleft करें, ताकि उसे अगला संसाधित किया जाए, क्योंकि इससे दूरी में कोई अतिरिक्त लागत नहीं जुड़ती।

dq.appendleft(v)

एक-भार वाले किनारों के लिए पीछे

क्या आप 1-भार वाले किनारे से जा रहे हैं? पड़ोसी को पीछे append करें, क्योंकि वह स्रोत से एक स्तर अधिक दूर है।

dq.append(v)

आगे से निकालें

वर्तमान नोड को हमेशा popleft करें। इससे डेक दूरी के अनुसार क्रमबद्ध रहता है, ठीक वैसे ही जैसे स्तरों में किया गया BFS रहता है।

u = dq.popleft()

भार के साथ दूरी सुधारें

हर किनारे पर दूरी सुधारें: नई दूरी dist[u] और किनारे के भार का योग होती है; फिर उस भार के अनुसार आगे या पीछे डालें।

nd = dist[u] + w
if nd < dist[v]:
    dist[v] = nd

क्रमबद्ध क्यों रहता है

डेक में एक समय पर अधिकतम दो अलग-अलग दूरियाँ रहती हैं। यही अपरिवर्तनीयता बताती है कि आगे और पीछे रखना क्यों काम करता है।

रैखिक गति

हीप न होने के कारण 0-1 BFS की जटिलता O(V + E) होती है, जो उसी ग्राफ़ पर डिज्क्स्ट्रा से स्पष्ट रूप से तेज़ है।

इसे कब अपनाएँ

जब भी चालें मुफ़्त हों या उनकी लागत एक हो, तब इसका उपयोग करें—जैसे ऐसे ग्रिड में जहाँ कुछ कदम अवरुद्ध हों और कुछ खुले।

त्वरित जाँच

आप 0 भार वाले किनारे से किसी पड़ोसी की दूरी सुधारते हैं। वह कहाँ जाएगा?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन: 0-1 BFS

डेक के साथ 0-भार वाले किनारों को आगे और 1-भार वाले किनारों को पीछे डालें। आपको O(V+E) के सरल समय में सबसे छोटे पथ मिल जाते हैं। ⚡

शुरुआत निःशुल्क

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 90
पाठ: 360

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Deque के साथ 0-1 BFS” पाठ निःशुल्क है?

हाँ—“Deque के साथ 0-1 BFS” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Deque के साथ 0-1 BFS” में मैं क्या सीखूँगा?

जब weights 0 या 1 हों, तब shortest paths खोजें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।

“Deque के साथ 0-1 BFS” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ