DFS یک مسیر را تا جای ممکن عمیق میرود و سپس Backtrack میکند. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Depth-First Search (DFS) زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
مثل حل هزارتو است: یک مسیر را تا بنبست ادامه میدهیم و سپس برمیگردیم.
مراحل اجرا
- رأس شروع را visited میکنیم.
- یک همسایه دیدهنشده را انتخاب میکنیم.
- در همان شاخه عمیق میشویم.
- در بنبست Backtrack میکنیم.
نمونه کد JavaScript
function dfs(graph, start) {
const seen = new Set(), order = [];
function visit(u) {
if (seen.has(u)) return;
seen.add(u); order.push(u);
for (const v of graph[u] ?? []) visit(v);
}
visit(start); return order;
}مثالهای واقعی و دنیای کار
- پیمایش فایلها و پوشهها
- Cycle Detection
- Connected Components
- Backtracking و Maze
پیچیدگی زمانی و فضایی
O(V + E) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
پیمایش عمیق، cycle و component
چه زمانی مناسب نیست؟
برای کوتاهترین مسیر بدون وزن، BFS مستقیمتر است.
جمعبندی
Depth-First Search (DFS) را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.