DFS روی گراف
Graph Depth-First SearchDFS یک مسیر را تا جای ممکن عمیق ادامه می‌دهد و سپس backtrack می‌کند. می‌توان آن را recursive یا با Stack پیاده‌سازی کرد.
اول این مفهوم را در ذهن نگه دار
DFS یک مسیر را تا جای ممکن عمیق ادامه می‌دهد و سپس backtrack می‌کند. می‌توان آن را recursive یا با Stack پیاده‌سازی کرد.
چطور کار می‌کند؟ ساده و مرحله‌ای
قبل از رفتن سراغ neighborها Node را visited کن تا cycle باعث loop نشود.
با adjacency list، پیمایش کامل معمولاً O(V + E) است.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای DFS روی گراف هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function dfs(graph, start) {
const seen = new Set();
function visit(node) {
if (seen.has(node)) return;
seen.add(node);
for (const next of graph[node] ?? []) visit(next);
}
visit(start);
return seen;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(V+E)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- بررسی اتصال
- پایه بعضی الگوریتم‌های cycle/SCC
- پیمایش عمیق گراف
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
Visited Set و O(V + E) را بگو و وقتی shortest path بدون وزن مهم است DFS را با BFS مقایسه کن.
DFS روی گراف چه مسئله‌ای را حل می‌کند؟
DFS یک مسیر را تا جای ممکن عمیق ادامه می‌دهد و سپس backtrack می‌کند. می‌توان آن را recursive یا با Stack پیاده‌سازی کرد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(V+E) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.