Commit to one path and follow it as far as it goes. Only when you hit a dead end do you back up to the last fork and try the next branch. A stack remembers where to return — the exact opposite discipline to BFS's queue.
← Back to the Field GuideBitta yo'lni tanlab, uni oxirigacha kuzating. Faqat boshi berk ko'chaga duch kelganingizda oxirgi ayrilishga qaytib, keyingi shoxni sinaysiz. Stack qayerga qaytishni eslab qoladi — bu BFS'ning queue'siga tamoman qarama-qarshi tartib.
← Qo'llanmaga qaytishWatch the graph below: each dive commits to one neighbor and follows it as deep as it goes before backing up — a completely different order from BFS's rings, using the exact same graph.
Quyidagi grafga qarang: har bir sho'ng'ish bitta qo'shniga bog'lanadi va orqaga qaytishdan oldin uni iloji boricha chuqur kuzatadi — bir xil grafda, lekin BFS'ning halqalaridan mutlaqo boshqa tartibda.
start node onto it. Create an empty visited set — unlike BFS, nothing gets marked visited yet.node.node is already in visited, skip it and go back to step 2 — it was pushed more than once before ever being explored, and there's no reason to explore it twice.node visited right now, at the moment it's popped (not when it was pushed). This is the "commit" moment: node is officially explored.node and push every one that is not yet in visited onto the top of the stack.start has now been visited.start node'ni unga qo'shing. Bo'sh visited to'plamini yarating — BFS'dan farqli o'laroq, hali hech narsa visited deb belgilanmagan.node deb ataymiz.node allaqachon visitedda bo'lsa, uni o'tkazib yuboring va 2-qadamga qayting — u hali hech qachon ko'rilmasdan turib bir necha marta stack'ga qo'shilgan, uni ikki marta ko'rishning hojati yo'q.nodeni aynan hozir, stack'dan olingan paytda (qo'shilgan paytda emas) visited deb belgilang. Bu — "bog'lanish" lahzasi: node rasman ko'rilgan hisoblanadi.nodening har bir qo'shnisiga qarang va hali visitedda bo'lmagan har birini stack'ning tepasiga qo'shing.startdan yetib boriladigan har bir node endi ko'rilgan.Time: O(V + E), where V is the number of nodes and E is the number of edges. Step 3's visited check guarantees each node is explored — marked visited and has its neighbors scanned — exactly once, which is O(V) of exploration work. A node can still be pushed onto the stack more than once before that happens (once for every edge into it from an already-explored neighbor — exactly what step 3 exists to filter out), but since each push only ever happens while scanning one specific edge during a node's single exploration step, the total number of pushes (and therefore pops) across the whole run is bounded by the number of edges, O(E). Add the exploration work and the stack bookkeeping together and the whole traversal still comes out to O(V + E). On a grid of rows rows and cols columns, every cell is a node and each has at most four edges to its neighbors, so this becomes O(rows · cols) — every cell is visited a constant number of times, no matter how the land is shaped.
Space: O(V) in general — the stack (or, written recursively, the call stack) and the visited tracking can, in the worst case, hold nearly every node at once, for example if the graph is one long unbranching path. On a grid, that worst case is a single island shaped like a snake winding through every cell: since the recursive solution below has no separate visited set and instead marks a cell visited by writing directly into the grid, its only real memory cost is the recursion depth — a snake-shaped island forces the recursive calls to stack up O(rows · cols) deep before the last cell is reached and the calls finally start unwinding.
Vaqt: O(V + E), bu yerda V — node'lar soni, E — qirralar soni. 3-qadamdagi visited tekshiruvi har bir node aynan bir marta ko'rilishini (visited deb belgilanib, qo'shnilari skanerlanishini) kafolatlaydi — bu O(V) ko'rish ishi. Node bu sodir bo'lishidan oldin baribir bir necha marta stack'ga qo'shilishi mumkin (allaqachon ko'rilgan har bir qo'shnisidan keladigan har bir qirra uchun bittadan — bu aynan 3-qadam filtrlab tashlaydigan holat), lekin har bir qo'shish bitta node'ning yagona ko'rish qadami paytida faqat bitta qirrani skanerlash chog'ida sodir bo'lgani uchun, butun ish davomidagi jami qo'shishlar (demak, olishlar ham) soni qirralar soniga — O(E)ga — chegaralangan. Ko'rish ishi va stack hisob-kitobini qo'shsangiz, butun traversal baribir O(V + E) bo'lib chiqadi. rows qator va cols ustunli grid'da har bir katak — node, va har birining qo'shnilariga ko'pi bilan to'rtta qirrasi bor, shuning uchun bu O(rows · cols)ga aylanadi — quruqlik qanday shaklda bo'lishidan qat'i nazar, har bir katak doimiy sondagi marta ko'riladi.
Xotira: umuman O(V) — stack (yoki rekursiv yozilganda, call stack) va visited kuzatuvi, eng yomon holatda, deyarli barcha node'larni bir vaqtda saqlashi mumkin, masalan graf bitta uzun, shoxlanmagan yo'l bo'lsa. Grid'da bu eng yomon holat — butun grid bo'ylab ilon kabi buralib ketgan yagona orol: quyidagi rekursiv yechim alohida visited to'plamiga ega emasligi va buning o'rniga katakni grid'ning o'ziga yozib visited deb belgilagani uchun, uning yagona haqiqiy xotira xarajati — rekursiya chuqurligi — ilon shaklidagi orol rekursiv chaqiruvlarni oxirgi katakka yetib, chaqiruvlar nihoyat qaytishni boshlagunga qadar O(rows · cols) chuqurlikda uyib boradi.
grid[r][c] to '0' as the very first thing inside the recursive step, before recursing into any neighbor — otherwise a neighbor's own call still sees the original cell as land and calls straight back into it, and the two calls bounce back and forth until Python's recursion limit is hit.r and c are still inside [0, rows) and [0, cols) before grid[r][c] is read at all — a negative index like grid[-1][c] doesn't crash in Python, it silently wraps around and reads the last row instead, corrupting the island count with no error message at all.'1' — that's what finds every separate island, not just the first one.rows · cols calls deep — comfortably past Python's default recursion limit (~1000) long before a 300×300 grid finishes sinking. Swap in the explicit stack from "How It Works" instead of recursion if the grid can get that large.grid[r][c]ni '0'ga rekursiv qadam ichida eng birinchi ish sifatida, har qanday qo'shniga rekursiya qilishdan oldin o'zgartiring — aks holda qo'shnining o'z chaqiruvi hali ham asl katakni quruqlik deb ko'radi va to'g'ridan-to'g'ri unga qaytadan chaqiradi, va ikkala chaqiruv Python'ning rekursiya chegarasiga yetguncha orqa-oldinga sakrab yuradi.r va c hali ham [0, rows) va [0, cols) ichida ekanligini grid[r][c] umuman o'qilishidan oldin tasdiqlashi kerak — Python'da grid[-1][c] kabi manfiy indeks xato bermaydi, u sezmasdan chetlanib oxirgi qatorni o'qiydi, hech qanday xato xabarisiz orollar sonini buzadi.'1' bo'lgan katakka duch kelgan har safar yangi DFS ishga tushirib (va sonni oshirib) borsagina to'g'ri chiqadi — aynan shu narsa faqat birinchisini emas, har bir alohida orolni topadi.rows · cols chaqiruv chuqurlikda rekursiya qiladi — bu 300×300 grid cho'kib bo'lishidan ancha oldin Python'ning standart rekursiya chegarasidan (~1000) oshib ketadi. Grid shunchalik katta bo'lishi mumkin bo'lsa, rekursiya o'rniga "Qanday Ishlaydi"dagi explicit stack'ni ishlating.Restated: given an m x n grid where each cell is '1' (land) or '0' (water), an island is a group of land cells connected 4-directionally (up, down, left, right). Return the number of islands.
visited set, is to flip it from '1' to '0' right there in the grid, "sinking" it. A single combined guard clause — out of bounds, or not land — stops the recursion at both the edges of the grid and the edges of the island, with no extra bookkeeping.'1' turns up, that's a brand-new island: increment the count once, then let the sinking DFS flush the rest of that island down to '0's before the scan moves on, so none of its cells get counted a second time later.def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def sink(r, c):
# bounds check comes first -- "or" short-circuits, so grid[r][c]
# is never read for an out-of-bounds (r, c)
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited by sinking this cell BEFORE recursing
sink(r - 1, c)
sink(r + 1, c)
sink(r, c - 1)
sink(r, c + 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1': # unvisited land found -- a brand-new island
count += 1
sink(r, c) # sink the whole island so it's never recounted
return count
Qayta bayon: har bir katagi '1' (quruqlik) yoki '0' (suv) bo'lgan m x n grid berilgan, orol esa 4 yo'nalishda (yuqori, past, chap, o'ng) bog'langan quruqlik kataklari guruhi. Orollar sonini qaytaring.
visited to'plamisiz eng toza yo'li, uni aynan o'sha yerda grid ichida '1'dan '0'ga o'zgartirish, ya'ni "cho'ktirish". Bitta birlashtirilgan guard clause — chegaradan tashqarida, yoki quruqlik emas — rekursiyani ham grid chegaralarida, ham orol chegaralarida to'xtatadi, qo'shimcha hisob-kitobsiz.'1' duch kelgan har safar, bu — yangi orol: sonni bir marta oshiring, keyin cho'ktiruvchi DFS'ga skanerlash davom etishdan oldin o'sha orolning qolgan qismini '0'larga aylantirishga ruxsat bering, shunda uning hech bir katagi keyinroq ikkinchi marta sanalmaydi.def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def sink(r, c):
# bounds check comes first -- "or" short-circuits, so grid[r][c]
# is never read for an out-of-bounds (r, c)
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited by sinking this cell BEFORE recursing
sink(r - 1, c)
sink(r + 1, c)
sink(r, c - 1)
sink(r, c + 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1': # unvisited land found -- a brand-new island
count += 1
sink(r, c) # sink the whole island so it's never recounted
return count
'1' cell, it flips to '0', so every later check sees it as water. Because the DFS call for that cell immediately recurses into all four neighbors before doing anything else, the entire connected island gets flipped to '0's — "sunk" — before the outer scan ever reaches that island's other cells, which is exactly what stops it from being counted a second time.sink(r-1, c)'s neighbors include (r, c) itself. If the sinking line hasn't run yet, that cell still reads as '1', so the neighboring call recurses right back into it, which recurses back again, and the two calls bounce between each other until Python's recursion limit is hit. Marking the cell sunk before recursing at all guarantees every later check of that same cell — from any neighbor, in any order — immediately sees '0' and returns without recursing further.'1' katakka tashrif buyurgan zahoti, u '0'ga aylanadi, shunda keyingi har qanday tekshiruv uni suv deb ko'radi. O'sha katak uchun DFS chaqiruvi boshqa hech narsa qilishdan oldin darhol barcha to'rtta qo'shniga rekursiya qilgani uchun, butun bog'langan orol tashqi skanerlash o'sha orolning boshqa kataklariga yetguncha '0'larga aylanadi — "cho'kadi" — bu esa aynan uni ikkinchi marta sanalishidan to'xtatadigan narsa.sink(r-1, c)ning qo'shnilari orasida (r, c)ning o'zi ham bor. Agar cho'ktirish qatori hali ishlamagan bo'lsa, o'sha katak hamon '1' deb o'qiladi, shuning uchun qo'shni chaqiruv to'g'ridan-to'g'ri unga qaytadan rekursiya qiladi, u esa yana orqaga rekursiya qiladi, va ikkala chaqiruv Python'ning rekursiya chegarasiga yetguncha orqa-oldinga sakrab yuradi. Katakni rekursiya qilishdan oldin cho'kkan deb belgilash, o'sha bir xil katakning keyingi har qanday tekshiruvi — istalgan qo'shnidan, istalgan tartibda — darhol '0'ni ko'rib, keyinroq rekursiya qilmasdan qaytishini kafolatlaydi.