Unweighted Paths की Shortest दूरी के लिए BFS
source से layer-by-layer दूरी निकालें
Unweighted Paths की Shortest दूरी के लिए BFS, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
BFS क्या करता है
BFS ग्राफ को वृत्ताकार परतों में खोजता है: पहले आरंभिक नोड, फिर उससे एक कदम दूर के सभी नोड, फिर दो कदम दूर के नोड और इसी तरह आगे। 🌊
वृत्ताकार परतों का अर्थ सबसे छोटा मार्ग क्यों है
BFS अगली परत पर जाने से पहले वर्तमान परत पूरी करता है, इसलिए किसी नोड तक पहली बार पहुँचना वहाँ तक का सबसे छोटा भाररहित मार्ग होता है।
कतार इसका इंजन है
BFS एक कतार का उपयोग करता है: जो पहले आए, वह पहले बाहर जाए। नए पड़ोसियों को पीछे जोड़ें और फिर आगे वाले को संसाधित करें।
from collections import deque
q = deque([start])देखे गए नोडों का लेखा रखें
देखा गया चिह्न रखें, ताकि आप एक ही नोड को कतार में दो बार न डालें। इससे BFS तेज़ और सीमित रहता है।
visited = [False] * (n + 1)
visited[start] = Trueदूरी संग्रहित करें
दूरी सरणी हर नोड की परत रखती है। आरंभिक नोड की दूरी 0 रखें; हर पड़ोसी की दूरी उसके मूल नोड से एक अधिक होती है।
dist = [-1] * (n + 1)
dist[start] = 0सामने वाले को pop करें
हर चरण में कतार के सामने वाले नोड को pop करें। वह अब तक संसाधित न किया गया सबसे निकटतम नोड है, इसलिए उसे अभी संभालें।
u = q.popleft()पड़ोसियों का विस्तार करें
u के हर ऐसे पड़ोसी के लिए जो अभी देखा नहीं गया है, उसे चिह्नित करें, उसकी दूरी निर्धारित करें और उसे कतार के पीछे डालें।
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)पूरा लूप
जब तक कतार खाली न हो, pop करते रहें और विस्तार करते रहें। कतार खाली होने पर आप हर पहुँच योग्य नोड पर जा चुके होंगे।
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)कतार में डालते समय चिह्नित करें
नोड को pop करने पर नहीं, बल्कि कतार में डालते ही देखा गया चिह्न लगाएँ। देर से चिह्नित करने पर एक ही नोड कई बार कतार में आ सकता है।
अप्राप्य नोड -1 ही रहता है
BFS के बाद भी जिस नोड की दूरी -1 हो, वह आपके आरंभिक नोड से बस अप्राप्य है। यह परिणाम भी महत्वपूर्ण है।
BFS रैखिक है
BFS हर नोड और एज को एक बार देखता है, इसलिए इसकी समय-जटिलता O(n + m) है। इससे प्रतियोगिताओं की अधिकांश समय-सीमाएँ आसानी से पूरी हो जाती हैं।
त्वरित जाँच
साधारण BFS सबसे छोटे मार्ग क्यों देता है?
पुनरावलोकन
आप कतार और दूरी सरणी के साथ BFS चलाते हैं: कतार में डालते समय चिह्नित करते हैं, पड़ोसियों का विस्तार करते हैं और समाप्त होने पर सबसे छोटी दूरियाँ पढ़ते हैं। 🎉
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “Unweighted Paths की Shortest दूरी के लिए BFS” पाठ निःशुल्क है?
हाँ—“Unweighted Paths की Shortest दूरी के लिए BFS” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Unweighted Paths की Shortest दूरी के लिए BFS” में मैं क्या सीखूँगा?
source से layer-by-layer दूरी निकालें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।
“Unweighted Paths की Shortest दूरी के लिए BFS” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Input से Adjacency Lists
- Unweighted Paths की Shortest दूरी के लिए BFS
- DFS, Recursion और Iterative Stacks
- Connected Components और Flood Fill