Breadth-First Search

Intuition

Watch the graph below: each ring lights up together before the next ring begins — the queue keeps discovery and visiting order in lockstep, so nothing farther away ever jumps the line.

Tushuncha (Intuition)

Quyidagi grafga qarang: keyingi halqa boshlanishidan oldin har bir halqa birgalikda yonadi — queue topilish va ko'rish tartibini bir xil saqlaydi, shuning uchun uzoqroqdagi hech narsa navbatni buzolmaydi.

How It Works

Create an empty queue and a visited set. Add the start node to both — it's discovered before the loop even begins.
While the queue isn't empty, pop the node at the front of the queue (not the back — that's what keeps this breadth-first instead of depth-first) and call it node.
Look at every neighbor of node in the graph.
For each neighbor that is not already in visited: mark it visited and push it onto the back of the queue.
Marking a node visited the moment it's discovered — not when it's popped — is what stops the same node from being queued twice by two different neighbors.
Go back to step 2. Because neighbors are always added after everything already waiting, every node one ring away gets processed before any node two rings away.
Stop when the queue empties. Every node reachable from start has now been visited, each one discovered in order of its distance (in edges) from start.

Qanday Ishlaydi

Bo'sh queue va visited to'plamini yarating. start node'ni ikkalasiga ham qo'shing — u loop boshlanmasdan oldinoq "topilgan" hisoblanadi.
Queue bo'sh emas ekan, queue'ning old qismidan node'ni oling (orqasidan emas — aynan shu narsa depth-first emas, breadth-first bo'lishini ta'minlaydi) va uni node deb ataymiz.
Grafdagi nodening har bir qo'shnisiga qarang.
Hali visitedda bo'lmagan har bir qo'shni uchun: uni visited deb belgilang va queue'ning orqasiga qo'shing.
Node'ni topilgan zahoti — navbatdan olinganda emas — visited deb belgilash, xuddi shu node ikkita turli qo'shni tomonidan ikki marta navbatga qo'shilib qolishining oldini oladi.
2-qadamga qayting. Qo'shnilar har doim allaqachon kutayotganlardan keyin qo'shilgani uchun, bir halqa uzoqdagi har bir node ikki halqa uzoqdagi node'dan oldin qayta ishlanadi.
Queue bo'shaganda to'xtang. startdan yetib boriladigan har bir node endi ko'rilgan, har biri startdan (qirralar bo'yicha) masofasi tartibida topilgan.

Complexity

Time: O(V + E), where V is the number of nodes (vertices) and E is the number of edges. Every node is enqueued and dequeued at most once, thanks to the visited check — that's O(V) of queue work. And across the whole traversal, every edge gets examined at most once (twice for an undirected graph, once from each endpoint) while scanning neighbor lists — that's O(E). Add the two together and you get O(V + E): the algorithm does a bounded, constant amount of work per node and per edge, never revisiting either.

Space: O(V). In the worst case — a "bushy" graph like a star, where one node connects to almost everything — the queue and the visited set can each hold nearly every node at once. On a grid of R rows and C columns, this becomes O(R · C), since every cell is a node.

Murakkablik

Vaqt: O(V + E), bu yerda V — node'lar (vertex'lar) soni, E — qirralar soni. visited tekshiruvi tufayli har bir node ko'pi bilan bir marta navbatga qo'shiladi va olinadi — bu O(V) queue ishi. Butun traversal davomida esa, qo'shnilar ro'yxatini skanerlash paytida har bir qirra ko'pi bilan bir marta ko'riladi (yo'naltirilmagan grafda ikki marta — har bir uchidan bir marta) — bu O(E). Ikkalasini qo'shsangiz O(V + E) hosil bo'ladi: algoritm har bir node va har bir qirra uchun cheklangan, doimiy ish bajaradi, ikkalasini ham hech qachon qayta ko'rmaydi.

Xotira: O(V). Eng yomon holatda — yulduz (star) kabi "shoxlagan" grafda, bitta node deyarli hamma narsaga ulangan bo'lsa — queue va visited to'plami har biri deyarli barcha node'larni bir vaqtda saqlashi mumkin. R qator va C ustunli grid'da esa bu O(R · C) ga aylanadi, chunki har bir katak bitta node hisoblanadi.

Common Mistakes

Forgetting the visited set entirely, or checking it only when a node is popped instead of when it's pushed. Fix: mark a node visited the instant it's added to the queue — otherwise the same node can be queued by multiple neighbors before any of them is processed, wasting work and, in a graph with a cycle, looping forever.
Reaching for a stack (or plain recursion) instead of a queue. Fix: BFS's entire "ring by ring" guarantee comes from first-in-first-out order — swap in a stack and you silently get depth-first search instead, which explores one branch all the way down before returning to siblings.
Popping from the wrong end of a Python list, e.g. list.pop(0), to simulate a queue. Fix: use collections.deque and popleft() — removing from the front of a plain list is O(n) per call, silently turning an O(V + E) algorithm into something much slower.
Forgetting that a graph can be disconnected, so a single BFS from one start node won't reach every node in the graph. Fix: if you need every node visited (not just those reachable from one start), loop over all nodes and start a fresh BFS from any node not yet in visited.

Ko'p Uchraydigan Xatolar

visited to'plamini umuman unutish, yoki uni node navbatga qo'shilganda emas, navbatdan olinganda tekshirish. Yechim: node navbatga qo'shilgan zahoti uni visited deb belgilang — aks holda bitta node hali hech biri qayta ishlanmasdan turib bir nechta qo'shni tomonidan navbatga qo'shilib qolishi mumkin, bu ishni behuda sarflaydi va cycle bor grafda cheksiz loop'ga olib keladi.
Queue o'rniga stack (yoki oddiy rekursiya) ishlatish. Yechim: BFS'ning butun "halqa-halqa" kafolati first-in-first-out tartibidan keladi — stack qo'ysangiz, sezmasdan depth-first search olasiz, u esa qaytishdan oldin bitta shoxni oxirigacha kuzatib boradi.
Queue'ni simulyatsiya qilish uchun Python list'ning noto'g'ri uchidan olish, masalan list.pop(0). Yechim: collections.deque va popleft() dan foydalaning — oddiy list'ning boshidan olib tashlash har chaqiriqda O(n) turadi, bu esa O(V + E) algoritmni sezmasdan ancha sekinroq narsaga aylantiradi.
Graf bog'lanmagan (disconnected) bo'lishi mumkinligini unutish — shuning uchun bitta start node'dan yagona BFS grafdagi barcha node'larga yetib bormaydi. Yechim: agar barcha node'lar ko'rilishi kerak bo'lsa (nafaqat bitta start'dan yetib boriladiganlar), barcha node'lar bo'ylab loop qiling va hali visitedda bo'lmagan har bir node'dan yangi BFS boshlang.

When to Use It

You need the shortest path (fewest edges, or fewest steps) in a graph where every edge has the same cost — BFS guarantees the first time you reach a node is via a shortest path, because it explores strictly in order of distance.
You need a level-order or "distance from source" traversal — e.g. printing a tree level by level, or labeling every cell in a grid with its distance from a starting point.
The problem is really a grid in disguise — cells are nodes, adjacency (usually up/down/left/right) is edges — and you're asked for the minimum number of steps, minutes, or moves to spread from one or more starting cells to the rest.
Skip it when you don't need shortest paths and just need to know if a path exists at all, or when the search naturally goes "as deep as possible first" (e.g. exhausting all combinations, backtracking) — depth-first search (with a stack or recursion) usually fits those better and uses less memory.

Qachon Ishlatish Kerak

Har bir qirra bir xil narxda bo'lgan grafda eng qisqa yo'l (eng kam qirra, yoki eng kam qadam) kerak bo'lganda — BFS node'ga birinchi marta yetib borilgan payt aynan eng qisqa yo'l orqali ekanini kafolatlaydi, chunki u qat'iy masofa tartibida qidiradi.
Sizga level-order yoki "manbadan masofa" traversal kerak bo'lsa — masalan, daraxtni qavat-qavat chop etish, yoki grid'dagi har bir katakni boshlanish nuqtasidan masofasi bilan belgilash.
Masala aslida yashiringan grid — kataklar node'lar, qo'shnilik (odatda yuqori/past/chap/o'ng) esa qirralar — va sizdan bir yoki bir nechta boshlang'ich katakdan qolgan qismga tarqalish uchun minimal qadamlar, daqiqalar yoki harakatlar sonini so'rashadi.
Eng qisqa yo'l kerak bo'lmasa va faqat yo'l umuman mavjudmi-yo'qmi bilishingiz kerak bo'lsa, yoki qidiruv tabiiy ravishda "iloji boricha chuqurroq birinchi" ketishi kerak bo'lsa (masalan, barcha kombinatsiyalarni sanab chiqish, backtracking) — undan saqlaning. Bunday holatlarda depth-first search (stack yoki rekursiya bilan) odatda yaxshiroq mos keladi va kamroq xotira ishlatadi.

LeetCode Practice

994. Rotting Oranges ↗

Restated: given a grid where each cell is 0 (empty), 1 (a fresh orange), or 2 (a rotten orange), every minute any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten too. Return the minimum number of minutes until no cell has a fresh orange left — or -1 if that's impossible.

See the grid as a graph. This looks nothing like the node-and-edge diagrams above, but it's the same shape underneath: every cell is a node, and each cell has up to four edges — to its up, down, left, and right neighbors. "Adjacent" in the grid is exactly "connected by an edge" in a graph.
Spot the "ring" language hiding in the problem. "Every minute, adjacent fresh oranges rot" is just "ring by ring" with a different name — minute 1 is ring one (direct neighbors of rotten oranges), minute 2 is ring two, and so on. That's BFS's exact shape, so the number of minutes needed is exactly the number of BFS rings.
Handle multiple starting points at once. A normal BFS starts from one node; here, every rotten orange is already "ring zero" simultaneously. Fix: instead of enqueueing a single start, scan the whole grid first and enqueue every rotten cell's coordinates before the BFS loop begins — this is called multi-source BFS, and it works exactly like single-source BFS because a queue with several starting items still expands strictly ring by ring.
Track "fresh oranges remaining" instead of a distance array. You don't need to store how far each cell is from a rotten orange — you only need the final minute count and whether every fresh orange got reached. Count fresh oranges up front, decrement the count every time BFS rots one, and process the grid level by level (one whole queue's worth of oranges at a time) so you can increment a minute counter once per level instead of once per orange.
Decide the final answer and the impossible case. The minute counter, once BFS finishes, is exactly the answer for a fully-rotted grid — but if fresh oranges remain after the queue empties (some fresh cell was unreachable, e.g. boxed in by empty cells with no rotten neighbor), no amount of waiting rots it, so return -1 instead.

from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # Multi-source BFS: every rotten orange starts in the queue
    # together, all counted as minute 0 (ring zero).
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right

    # Process one full ring (one minute) at a time.
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):  # everyone currently in the queue is this minute's ring
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2   # this fresh orange rots now
                    fresh -= 1
                    queue.append((nr, nc))  # it will rot its own neighbors next minute

    return minutes if fresh == 0 else -1  # -1: some fresh orange was never reachable

LeetCode Amaliyoti