Python में Breadth-First Search (BFS)
Graph को level by level traverse करें।
में Breadth-First Search (BFS) क्या है?
समस्या क्या है
सोशल नेटवर्क में एक व्यक्ति से दूसरे तक, या भूलभुलैया के एक खाने से बाहर निकलने तक कितने स्टेप लगते हैं? Breadth-first search दूरी के घेरों में खोजता है, इसलिए वह किसी node तक पहली बार सबसे छोटे रास्ते से ही पहुँचता है।
ऐसे समझें
Breadth-first search तालाब की लहरों जैसा है। शुरुआत की जगह पत्थर गिराइए, लहर पहले एक स्टेप दूर की हर चीज़ तक पहुँचती है, फिर दो स्टेप दूर, और ऐसे ही आगे। पास की सब चीज़ों तक पहुँचने से पहले कोई दूर की चीज़ नहीं छुई जाती।
queue = deque(["A"])🪨 A पर पत्थर गिराइएnode = queue.popleft()🌊 दूरी के क्रम में अगला node लीजिएif neighbor not in visited:🔎 अभी तक नहीं पहुँचे?queue.append(neighbor)➕ उसे अगले घेरे में जोड़िएBreadth-first search (BFS) शुरुआती node से graph को level-दर-level देखता है, queue इस्तेमाल करके, इसलिए यह बिना weight वाले graph में सबसे छोटे रास्ते ढूँढता है।
मुख्य बातें
queueउन nodes को रखता है जो खोजे जाने का इंतज़ार कर रहे हैं, सबसे पुराना पहले।visitedपहले मिल चुके nodes दर्ज करता है, ताकि कोई दो बार न जुड़े और cycles हमेशा न घूमें।node = queue.popleft()अगला node लेता है; उसके unvisited पड़ोसी queue के पीछे जुड़ते हैं।orderपहले A दिखाता है, फिर उसके पड़ोसी B और C, फिर एक level आगे D और E।
इसका उपयोग कब करें?
- बिना weight वाले graph, grid और भूलभुलैया में सबसे छोटे रास्ते।
- सोशल नेटवर्क में degrees of separation।
- Web crawler और शुरुआती जगह से पहुँचने लायक सब कुछ ढूँढना।
कब ज़रूरत नहीं
- Edges की अलग-अलग लागत है, जैसे सड़क की दूरी: Dijkstra का एल्गोरिदम इस्तेमाल कीजिए।
- आपको दूसरों से पहले एक रास्ता पूरा खोजना है, जैसे backtracking के लिए: depth-first search इस्तेमाल कीजिए।
Python में Breadth-First Search (BFS) Visualizer
O(V+E)हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)
अपेक्षित आउटपुट
['A', 'B', 'C', 'D', 'E']
यह कैसे काम करता है
visited set repeated traversal रोकता है: समय O(V+E) और memory O(V) है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
Nodes को बहुत देर से visited मार्क करना
अगर node सिर्फ़ queue से निकालते समय मार्क हो, तो वह कई बार जुड़ सकता है।
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. मध्यम
- Tree Diameter A tree is a connected undirected graph with no cycles. मध्यम
- Count Islands Count groups of connected land cells in a grid. मध्यम