Python एल्गोरिदम

Python में Breadth-First Search (BFS)

Graph को level by level traverse करें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में 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)➕ उसे अगले घेरे में जोड़िए
पास वाले nodes पहले, queue के साथ।
एक वाक्य में

Breadth-first search (BFS) शुरुआती node से graph को level-दर-level देखता है, queue इस्तेमाल करके, इसलिए यह बिना weight वाले graph में सबसे छोटे रास्ते ढूँढता है।

मुख्य बातें

  1. queue उन nodes को रखता है जो खोजे जाने का इंतज़ार कर रहे हैं, सबसे पुराना पहले।
  2. visited पहले मिल चुके nodes दर्ज करता है, ताकि कोई दो बार न जुड़े और cycles हमेशा न घूमें।
  3. node = queue.popleft() अगला node लेता है; उसके unvisited पड़ोसी queue के पीछे जुड़ते हैं।
  4. 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 देखने के लिए चलाएँ या अगला चरण दबाएँ।

उदाहरण कोड

कोड चलाएँ →
main.py
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)
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

['A', 'B', 'C', 'D', 'E']

यह कैसे काम करता है

visited set repeated traversal रोकता है: समय O(V+E) और memory O(V) है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

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)

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

अगला: Python में Depth-First Search (DFS) →

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज