Breadth-First Search

शुरुआत के चारों ओर छल्ले

BFS पहले 1 edge दूर सभी nodes, फिर 2 edge दूर सभी, इत्यादि देखता है। Queue यह क्रम लागू करती है और visited set पुनःयात्रा रोकता है। किसी node तक पहली बार पहुँचना सबसे छोटे पथ (edge में) से होता है। O(V + E)।

सबसे छोटी पथ लंबाई

हर पड़ोसी को पहली बार enqueue करते समय दूरी ट्रैक करें।

from collections import deque
def shortest(g, start, goal):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, d = q.popleft()
        if node == goal:
            return d
        for nb in g[node]:
            if nb not in seen:
                seen.add(nb)
                q.append((nb, d + 1))
    return -1

यह कहाँ फिट है

भूलभुलैया/grid में सबसे छोटा पथ, "न्यूनतम चरण...", tree का level-order traversal, word ladder, और flood fill। यदि edge पर weight हो, Dijkstra पर जाएँ।