الگوریتم جستجوی عمق اول (Depth-First Search - DFS) الگوریتمی است که بر پایه جستجوی سطح اول (BFS) ساخته شده است، اما ساختار درخت یا گراف را به شیوه‌ای متفاوت کاوش می‌کند.
در اینجا توضیحات جامعی درباره این الگوریتم ارائه شده است:
۱. مکانیسم و تمرکز DFS
برخلاف BFS که بر کاوش گره‌ها به صورت سطح به سطح (level by level) تمرکز دارد [10، 8]، DFS تا جایی که ممکن است در یک مسیر عمیق می‌شود قبل از اینکه به کاوش مسیر بعدی بپردازد.
- روش کاوش: DFS با رفتن به عمق یک شاخه، تا زمانی که به انتهای آن (مانند یک گره برگ یا بن‌بست) برسد، پیش می‌رود، و سپس به عقب برمی‌گردد تا شاخه‌های دیگر را کاوش کند.
۲. ساختار داده اصلی: پشته (Stack)
در حالی که BFS از یک صف (Queue) استفاده می‌کند، DFS از یک پشته (Stack) برای کاوش گره‌ها به شیوه عمق اول استفاده می‌نماید.
- پشته فراخوانی: اغلب، پشته‌ای که DFS استفاده می‌کند، همان پشته تماس (Call Stack) است، زیرا اکثر پیاده‌سازی‌های DFS از بازگشت (Recursion) استفاده می‌کنند.
۳. کاربردهای اصلی DFS
DFS برای مسائلی مناسب‌تر است که نیاز به کاوش تمام مسیرها یا بررسی هر پیکربندی ممکن دارند.
- موارد استفاده:
- پیدا کردن تمام مسیرهای ممکن در یک درخت.
- جستجو برای یک شرط خاص در عمق ساختار.
- تشخیص چرخه‌ها در گراف.
۴. کارایی حافظه
ماهیت عمق اول DFS باعث می‌شود که در برخی موارد از نظر حافظه کارآمدتر باشد. با این حال، DFS برای مسائلی که به دنبال کوتاه‌ترین مسیر یا کاوش کم‌عمق هستند، مناسب نیست، زیرا تضمین نمی‌کند که نزدیک‌ترین راه‌حل را اول پیدا کند (برخلاف BFS).
۵. مثال کاربردی: مسئله شمارش جزایر (Number of Islands)
یک مسئله متداول در LeetCode که از الگوی DFS استفاده می‌کند، مسئله «شمارش جزایر» است.
- هدف مسئله: هدف این است که تعداد جزایر موجود در یک شبکه دو بعدی را بشمارید، جایی که عدد ‘۱’ نشان‌دهنده خشکی و ‘۰’ نشان‌دهنده آب است. یک جزیره با اتصال ‘۱’های مجاور به صورت افقی یا عمودی تشکیل می‌شود.
- حل با DFS:
- شبکه پیمایش می‌شود و هرگاه با یک ‘۱’ (خشکی) مواجه شویم، مشخص می‌کند که شروع یک جزیره است.
- از آنجا، DFS برای کاوش تمام ‘۱’های متصل (همسایگان در چهار جهت) به صورت عمیق انجام می‌شود.
- در طول DFS، هر سلول بازدید شده با تغییر مقدار آن به ‘۰’ علامت‌گذاری می‌شود تا اطمینان حاصل شود که دوباره شمرده نمی‌شود.
- پس از بازدید از تمام سلول‌های متصل برای آن جزیره، شمارنده جزایر افزایش یافته و جستجو در بقیه شبکه ادامه می‌یابد.
- تعداد کل فراخوانی‌های اولیه DFS (به استثنای فراخوانی‌های بازگشتی) برابر با تعداد جزایر است.
۶. پس‌گشت (Backtracking) به عنوان گسترش DFS
الگوی پس‌گشت (Backtracking) در حقیقت صرفاً گسترشی از جستجوی عمق اول (DFS) است.
- تفاوت اصلی: در DFS، معمولاً یک ساختار از پیش ساخته شده (مانند درخت یا گراف) را پیمایش می‌کنیم. در پس‌گشت، اغلب باید درخت راه‌حل (Solution Tree) را خودتان بسازید، به ویژه در مسائل ترکیبی که ساختار درخت به صراحت داده نشده و به صورت پویا در حین تصمیم‌گیری‌ها تولید می‌شود.
- مکانیسم پس‌گشت: در این الگو، تمام راه‌حل‌های ممکن با اتخاذ یک سری تصمیمات کاوش می‌شوند. هنگامی که یک تصمیم منجر به بن‌بست می‌شود، شما به تصمیم قبلی باز می‌گردید (backtrack)، آن را لغو می‌کنید و یک مسیر دیگر را امتحان می‌کنید.
به طور کلی، DFS مانند یک غواص است که تا انتهای هر غار عمیق می‌رود تا مطمئن شود چیزی را از دست نداده است، و تنها پس از بررسی کامل آن غار، به سطح برمی‌گردد تا غار بعدی را بررسی کند.