پیمایش عمقی (DFS)
پیمایش عمق اول با پشته و بازگشت: رفتن تا عمق ممکن، تشخیص دور در گراف و مقایسه با BFS
DFS چیست؟
پیمایش عمق اول (Depth-First Search) تا جای ممکن در یک شاخه به عمق می‌رود؛ وقتی به بن‌بست رسید، برمی‌گردد (Backtrack) و شاخه بعدی را امتحان می‌کند — مثل کاوش ماز!
دو ابزار: پشته یا بازگشت
DFS با پشته (LIFO) یا به‌صورت بازگشتی (که خودش از پشته فراخوانی استفاده می‌کند) پیاده می‌شود:
- رأس فعلی را بازدید و علامت بزن
- به اولین همسایه دیده‌نشده برو (بازگشتی)
- وقتی همسایه دیده‌نشده نبود، برگرد
مثال گام‌به‌گام
گراف: A - B - D
| |
C - E - F
DFS از A:
A -> B -> D -> E -> C (برگشت) -> F
ترتیب: A, B, D, E, C, F (عمق اول!)مقایسه با BFS همان گراف: A, B, C, D, E, F — دو شخصیت متفاوت!
پیچیدگی
| معیار | پیچیدگی |
|---|---|
| زمان (لیست همسایگی) | O(V + E) |
| حافظه | O(V) — پشته/بازگشت |
BFS یا DFS؟
| مسئله | انتخاب |
|---|---|
| کوتاه‌ترین مسیر بدون وزن | BFS ✓ |
| وجود مسیر | هر دو |
| تشخیص دور | DFS ✓ |
| ترتیب توپولوژیک | DFS ✓ |
| اجزای همبند | هر دو |
| حل ماز | DFS ✓ |
| نزدیک‌ترین همسایه‌ها | BFS ✓ |
تشخیص دور با DFS
در گراف جهت‌دار: اگر در حین DFS به رأسی برسیم که در حال پردازش است (در پشته فعلی)، دور پیدا شد! این پایه تشخیص deadlock در سیستم‌عامل و وابستگی چرخه‌ای در build system هاست.
کاربردهای واقعی DFS
- تشخیص دور در سیستم‌های وابستگی (npm، make)
- ترتیب توپولوژیک (اولویت انجام کارها)
- حل ماز و پازل
- پیدا کردن اجزای قویاً همبند
- الگوریتم‌های مسیر در هوش مصنوعی
هشدار: DFS بازگشتی روی گراف بزرگ (ده‌ها هزار رأس) ممکن است پشته پایتون را سرریز کند (RecursionError)؛ در این حالت نسخه پشته‌ای (تکراری) استفاده کنید.
جمع‌بندی
- رفتن تا عمق ممکن + Backtrack — با پشته یا بازگشت
- O(V + E) مثل BFS اما مسیر متفاوت
- قهرمان: تشخیص دور، ترتیب توپولوژیک، ماز
- BFS برای کوتاه‌ترین مسیر بدون وزن
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.