Depth-First Search for Connected Components
آمادگی مصاحبهٔ الگوریتمی با Python
- In 90 minutes, introduce vertices, edges, paths, cycles, disconnected components, and adjacency lists; model four-neighbor grid cells as a graph.
- Introduce recursive calls through a stopping case, progress to a smaller unexplored region, and call-stack storage; relate recursion to an explicit LIFO stack.
- Recognize reachability and component questions; distinguish them from shortest-path questions.
- For Number of Islands, independently choose discovery marking and component-count updates before the worked Python implementation.
- Replace repeated reachability scans with one traversal per unseen component; implement iterative DFS and trace the corresponding recursive formulation.
- Prove that one traversal discovers exactly one component; derive O(V + E) time and O(V) auxiliary space, or O(rows * columns) for a grid.
- Test empty grids, one row, isolated cells, and a fully connected region; diagnose missing bounds checks, late marking, mutation without permission, and Python recursion-depth limits.
از خشکیها تا connected component
```svg
<svg viewBox="0 0 800 570" xmlns="http://www.w3.org/2000/svg"><text x="200" y="30" text-anchor="middle" class="tm-text" font-size="20" direction="rtl">graph بدون جهت</text><rect x="56" y="58" width="278" height="184" rx="32" class="tm-green" opacity="0.18"/><rect x="336" y="166" width="58" height="76" rx="26" class="tm-gold" opacity="0.22"/><path d="M100 100 L290 100 L195 200 Z" class="tm-line" fill="none" stroke-width="3"/><circle cx="100" cy="100" r="23" class="tm-soft"/><circle cx="290" cy="100" r="23" class="tm-soft"/><circle cx="195" cy="200" r="23" class="tm-soft"/><circle cx="365" cy="200" r="23" class="tm-soft"/><g text-anchor="middle" font-size="20"><text x="100" y="107" class="tm-text">A</text><text x="290" y="107" class="tm-text">B</text><text x="195" y="207" class="tm-text">C</text><text x="365" y="207" class="tm-text">D</text></g><text x="195" y="268" text-anchor="middle" class="tm-text-green" font-size="16" direction="rtl">یک component</text><text x="365" y="268" text-anchor="middle" class="tm-text-gold" font-size="16" direction="rtl">یکی دیگر</text><rect x="440" y="55" width="310" height="225" rx="16" class="tm-surface"/><text x="595" y="84" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">adjacency list در Python</text><g font-family="monospace" font-size="17"><text x="470" y="120" class="tm-text">{ 'A': ['B', 'C'],</text><text x="490" y="153" class="tm-text">'B': ['A', 'C'],</text><text x="490" y="186" class="tm-text">'C': ['A', 'B'],</text><text x="490" y="219" class="tm-text">'D': [] }</text></g><text x="595" y="256" text-anchor="middle" class="tm-muted" font-size="15" direction="rtl">هر edge در هر دو سمت</text><text x="205" y="310" text-anchor="middle" class="tm-text" font-size="20">Number of Islands</text><rect x="125" y="330" width="160" height="160" rx="8" class="tm-surface"/><path d="M178 330 V490 M232 330 V490 M125 383 H285 M125 437 H285" class="tm-line" fill="none"/><rect x="179" y="384" width="52" height="52" class="tm-accent"/><rect x="179" y="331" width="52" height="51" class="tm-green"/><rect x="126" y="384" width="51" height="52" class="tm-green"/><rect x="233" y="384" width="51" height="52" class="tm-green"/><rect x="179" y="438" width="52" height="51" class="tm-green"/><path d="M205 357 V463 M151 410 H259" class="tm-line-accent" fill="none" stroke-width="3"/><text x="595" y="350" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">هر خشکی یک vertex</text><text x="595" y="389" text-anchor="middle" class="tm-text-green" font-size="18" direction="rtl">edge: بالا، پایین، چپ، راست</text><text x="595" y="427" text-anchor="middle" class="tm-text-accent" font-size="18" direction="rtl">قطری: بدون اتصال</text><text x="595" y="467" text-anchor="middle" class="tm-muted" font-size="17" direction="rtl">همسایهها از مختصات؛ بدون ساخت فهرست</text><rect x="50" y="513" width="700" height="43" rx="12" class="tm-soft"/><text x="400" y="540" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">شمارش گروهها و دسترسی؛ نه تضمین کوتاهترین مسیر</text></svg>
```
هر جزیره، فقط یک بار
```svg
<svg viewBox="0 0 800 450" xmlns="http://www.w3.org/2000/svg"><defs><marker id="arrow" markerWidth="8" markerHeight="8" refX="7" refY="4" orient="auto"><path d="M0 0 L8 4 L0 8 Z" class="tm-arrow"/></marker></defs><text x="160" y="32" class="tm-text" font-size="20" text-anchor="middle">Number of Islands</text><text x="84" y="63" class="tm-muted" font-size="16" text-anchor="middle">0</text><text x="160" y="63" class="tm-muted" font-size="16" text-anchor="middle">1</text><text x="236" y="63" class="tm-muted" font-size="16" text-anchor="middle">2</text><text x="30" y="118" class="tm-muted" font-size="16">0</text><text x="30" y="194" class="tm-muted" font-size="16">1</text><text x="30" y="270" class="tm-muted" font-size="16">2</text><rect x="50" y="78" width="68" height="68" rx="8" class="tm-accent"/><rect x="126" y="78" width="68" height="68" rx="8" class="tm-accent"/><rect x="202" y="78" width="68" height="68" rx="8" class="tm-surface"/><rect x="50" y="154" width="68" height="68" rx="8" class="tm-surface"/><rect x="126" y="154" width="68" height="68" rx="8" class="tm-accent"/><rect x="202" y="154" width="68" height="68" rx="8" class="tm-surface"/><rect x="50" y="230" width="68" height="68" rx="8" class="tm-surface"/><rect x="126" y="230" width="68" height="68" rx="8" class="tm-surface"/><rect x="202" y="230" width="68" height="68" rx="8" class="tm-gold"/><g font-size="24" text-anchor="middle"><text x="84" y="120" class="tm-text">1</text><text x="160" y="120" class="tm-text">1</text><text x="236" y="120" class="tm-muted">0</text><text x="84" y="196" class="tm-muted">0</text><text x="160" y="196" class="tm-text">1</text><text x="236" y="196" class="tm-muted">0</text><text x="84" y="272" class="tm-muted">0</text><text x="160" y="272" class="tm-muted">0</text><text x="236" y="272" class="tm-text">1</text></g><path d="M118 112 H126 M160 146 V154" class="tm-line-accent" stroke-width="5"/><text x="535" y="85" class="tm-text" font-size="21" text-anchor="middle" direction="rtl">اتصال چهارجهته</text><text x="535" y="122" class="tm-text2" font-size="18" text-anchor="middle" direction="rtl">ورودی خالی پذیرفته میشود</text><text x="535" y="159" class="tm-text2" font-size="18" text-anchor="middle" direction="rtl">جدول تغییر نمیکند</text><text x="535" y="220" class="tm-text-accent" font-size="24" text-anchor="middle" direction="rtl">تعداد جزیرهها: 2</text><text x="160" y="334" class="tm-text2" font-size="17" text-anchor="middle" direction="rtl">اتصال قطری حساب نمیشود</text><text x="535" y="264" class="tm-text" font-size="19" text-anchor="middle" direction="rtl">فقط شروع گروه تازه: شمارنده +1</text><text x="535" y="300" class="tm-text2" font-size="18" text-anchor="middle" direction="rtl">پیمایش، کل گروه را علامت میزند</text><rect x="50" y="365" width="190" height="54" rx="10" class="tm-soft"/><text x="145" y="398" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">کشف خشکی دیدهنشده</text><path d="M245 392 H300" class="tm-line-accent" marker-end="url(#arrow)"/><rect x="310" y="365" width="190" height="54" rx="10" class="tm-green"/><text x="405" y="398" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">علامت در visited</text><path d="M505 392 H560" class="tm-line-accent" marker-end="url(#arrow)"/><rect x="570" y="365" width="180" height="54" rx="10" class="tm-soft"/><text x="660" y="398" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">گذاشتن در stack</text><text x="660" y="346" class="tm-text-accent" font-size="17" text-anchor="middle" direction="rtl">LIFO: آخرین ورود، اولین خروج</text><text x="405" y="443" class="tm-text-green" font-size="17" text-anchor="middle" direction="rtl">visited مانع کشف دوباره است</text></svg>
```
پیادهسازی کامل iterative DFS
**visited مشترک؛ علامتگذاری هنگام کشف**
```python
def numislands(grid):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
count = 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1" or (r, c) in visited:
continue
count += 1
visited.add((r, c))
stack = [(r, c)]
while stack:
cr, cc = stack.pop()
for dr, dc in directions:
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols:
if grid[nr][nc] == "1" and (nr, nc) not in visited:
visited.add((nr, nc))
stack.append((nr, nc))
return count
```
**ردگیری مثال**
- شروع اول: \((0,0)\)؛ \(\mathrm{count}=1\). کشفها: \((0,0)\rightarrow(0,1)\rightarrow(1,1)\)؛ سپس stack خالی میشود.
- ادامهٔ اسکن: هر سه خانه در visited هستند؛ بدون شمارش دوباره رد میشوند.
- شروع دوم: \((2,2)\)؛ \(\mathrm{count}=2\). پس از بررسی همسایهها، stack دوباره خالی میشود.
- خروجی: \(2\).
**حالا بدون نگاهکردن، تابع را بنویس.**
recursive DFS و مسیر بازگشت
```svg
<svg viewBox="0 0 800 540" xmlns="http://www.w3.org/2000/svg"><rect class="tm-soft" x="30" y="15" width="740" height="90" rx="12"/><text class="tm-text" x="400" y="42" font-size="18" text-anchor="middle" direction="rtl">stopping case: بیرون جدول، آب، یا قبلاً دیدهشده ← بازگشت</text><text class="tm-text2" x="400" y="69" font-size="16" text-anchor="middle" direction="rtl">اول بررسی مرز؛ بعد خواندن جدول</text><text class="tm-text-green" x="400" y="93" font-size="16" text-anchor="middle" direction="rtl">در غیر این صورت: ثبت در visited؛ سپس راست، پایین، چپ، بالا</text><text class="tm-text" x="135" y="137" font-size="18" text-anchor="middle" direction="rtl">مسیر کشف</text><text class="tm-text" x="640" y="137" font-size="18" text-anchor="middle">call stack</text><rect class="tm-green" x="40" y="155" width="190" height="48" rx="9"/><text class="tm-text" x="135" y="185" font-size="19" text-anchor="middle">visit(0,0) ✓</text><path class="tm-line-accent" d="M135 203 V245"/><text class="tm-text2" x="165" y="230" font-size="15" direction="rtl">راست</text><rect class="tm-green" x="40" y="245" width="190" height="48" rx="9"/><text class="tm-text" x="135" y="275" font-size="19" text-anchor="middle">visit(0,1) ✓</text><text class="tm-muted" x="370" y="273" font-size="16" text-anchor="middle" direction="rtl">visit(0,2): آب؛ بازگشت</text><path class="tm-line-accent" d="M135 293 V335"/><text class="tm-text2" x="165" y="320" font-size="15" direction="rtl">پایین</text><rect class="tm-green" x="40" y="335" width="190" height="48" rx="9"/><text class="tm-text" x="135" y="365" font-size="19" text-anchor="middle">visit(1,1) ✓</text><text class="tm-muted" x="370" y="350" font-size="15" text-anchor="middle" direction="rtl">(1,2)، (2,1)، (1,0): آب</text><text class="tm-muted" x="370" y="377" font-size="15" text-anchor="middle" direction="rtl">(0,1): قبلاً دیدهشده</text><text class="tm-text2" x="370" y="405" font-size="15" text-anchor="middle" direction="rtl">همه فوراً برمیگردند</text><rect class="tm-surface" x="530" y="155" width="220" height="56" rx="8"/><text class="tm-text" x="640" y="179" font-size="18" text-anchor="middle">visit(0,0)</text><text class="tm-text2" x="640" y="201" font-size="15" text-anchor="middle" direction="rtl">ادامه: پایین</text><rect class="tm-surface" x="530" y="220" width="220" height="56" rx="8"/><text class="tm-text" x="640" y="244" font-size="18" text-anchor="middle">visit(0,1)</text><text class="tm-text2" x="640" y="266" font-size="15" text-anchor="middle" direction="rtl">ادامه: چپ</text><rect class="tm-accent" x="530" y="285" width="220" height="56" rx="8"/><text class="tm-text" x="640" y="309" font-size="18" text-anchor="middle">visit(1,1)</text><text class="tm-text2" x="640" y="331" font-size="15" text-anchor="middle" direction="rtl">بررسی چهار همسایه</text><path class="tm-line-accent" d="M750 313 H770 V248 H750 M750 248 H780 V183 H750"/><text class="tm-text-accent" x="640" y="370" font-size="16" text-anchor="middle" direction="rtl">بازگشت به محل ادامه</text><text class="tm-muted" x="640" y="397" font-size="14" text-anchor="middle" direction="rtl">نمای فراخوانیها پیش از بازگشت</text><text class="tm-text2" x="400" y="438" font-size="15" text-anchor="middle" direction="rtl">در (0,1): چپ دیدهشده؛ بالا بیرون جدول</text><text class="tm-text2" x="400" y="465" font-size="15" text-anchor="middle" direction="rtl">در (0,0): پایین آب؛ چپ و بالا بیرون جدول؛ پایان پیمایش</text><text class="tm-text-green" x="400" y="494" font-size="16" text-anchor="middle" direction="rtl">هر ورود موفق: یک خشکی دیدهنشده کمتر</text><text class="tm-text-accent tm-enter" x="400" y="526" font-size="16" text-anchor="middle" direction="rtl">جزیرهٔ طولانی ← عمق زیاد ← RecursionError در Python؛ iterative هم حافظه میخواهد</text></svg>
```
درستی شمارش، هزینه و تستها
**پیمایش دقیقاً یک component**
هر کشف با یک path به شروع وصل است؛ پس از component خارج نمیشویم.
اگر خشکی قابلدسترسی جا بماند، اولین خانهٔ جاافتاده روی path باید از همسایهٔ قبلی کشف شود؛ تناقض.
**هر component، فقط یک افزایش**
اولین خشکی دیدهنشده ← افزایش شمارنده و پیمایش کامل.
بقیهٔ خانههای همان component در visited هستند؛ افزایش دوباره نداریم.
**هزینه در graph**
هر vertex یک بار؛ هر فهرست همسایه یک بار؛ هر edge بدون جهت دو بار.
زمان: \(O(|V|+|E|)\)؛ حافظهٔ کمکی: \(O(|V|)\).
فرض: عضویت و افزودن در set با هزینهٔ متوسط \(O(1)\).
**هزینه در جدول**
اسکن \(\mathrm{rows}\times\mathrm{cols}\) خانه؛ حداکثر \(4\) همسایه برای هر خشکی.
زمان: \(O(\mathrm{rows}\cdot\mathrm{cols})\).
حافظهٔ visited و stack در بدترین حالت: \(O(\mathrm{rows}\cdot\mathrm{cols})\).
**تستهای مرزی**
خالی یا یک ردیف خالی: \(0\)؛ سراسر آب: \(0\).
\(\begin{bmatrix}1&0&1\end{bmatrix}\rightarrow 2\)
\(\begin{bmatrix}1&0\\0&1\end{bmatrix}\rightarrow 2\)؛ همسایگی قطری نداریم.
\(\begin{bmatrix}1&1\\1&1\end{bmatrix}\rightarrow 1\)؛ آزمون cycle.
**خطاهای رایج و تمرین**
بدون چک مرز: اندیس منفی Python ممکن است به انتهای جدول وصل شود.
علامتزدن بعد از pop: ورود تکراری به stack؛ پردازش تکراری را هم رد کن.
تبدیل خشکی به آب بدون اجازه: تخریب ورودی.
از صفر پیادهسازی کن و تصمیمها را توضیح بده؛ برای شمارش، visited مشترک میماند.
Back to course