Depth-First Search (DFS) یکی از پایه‌ای‌ترین الگوریتم‌های پیمایش گراف و درخت است. ایده‌ی اصلی آن این است:

از یک رأس شروع کن، یک مسیر را تا جایی که ممکن است عمیق ادامه بده، و وقتی دیگر راهی برای ادامه نبود، برگرد و مسیر دیگری را امتحان کن.

این رفتار شبیه وارد شدن به یک هزارتو است: یک راه را تا بن‌بست می‌رویم، بعد برمی‌گردیم و شاخه‌ی دیگری را بررسی می‌کنیم.

DFS فقط برای Traversal نیست. بسیاری از الگوریتم‌های مهم گراف مثل Cycle Detection، Connected Components، Topological Sort، Strongly Connected Components، Bridges، Articulation Points و انواع Backtracking بر پایه‌ی همین ایده ساخته می‌شوند.

در این مقاله DFS را از صفر بررسی می‌کنیم؛ از Recursion و Stack گرفته تا کاربردهای واقعی، تفاوت با BFS، پیاده‌سازی روی Graph و Tree، تشخیص Cycle، Componentها، Grid و Maze، پیچیدگی و خطاهای رایج در JavaScript و TypeScript.

DFS دقیقاً چه مسئله‌ای را حل می‌کند؟

فرض کنید گراف زیر را داریم:

A
├── B
│   ├── D
│   └── E
└── C
    └── F

اگر DFS را از A شروع کنیم، ممکن است ترتیب پیمایش چنین باشد:

A → B → D → E → C → F

DFS ابتدا وارد یک شاخه می‌شود:

A → B → D

وقتی D همسایه‌ی جدیدی ندارد، Backtrack می‌کند:

D → B

بعد شاخه‌ی دیگر:

B → E

و بعد از تمام شدن شاخه‌های B به A برمی‌گردد و C را بررسی می‌کند.

ایده‌ی اصلی DFS

DFS می‌تواند با دو روش اصلی پیاده‌سازی شود:

1. Recursion
2. Explicit Stack

در نسخه‌ی Recursive، Call Stack زبان برنامه‌نویسی همان Stack الگوریتم را می‌سازد.

در نسخه‌ی Iterative، خودمان یک Stack ایجاد می‌کنیم.

DFS با Recursion

ساده‌ترین شکل:

function dfs(graph, start) {
  const visited = new Set();
  const order = [];

  function visit(node) {
    if (visited.has(node)) return;

    visited.add(node);
    order.push(node);

    for (const next of graph[node] ?? []) {
      visit(next);
    }
  }

  visit(start);

  return order;
}

چرا visited لازم است؟

در Graph برخلاف Tree ممکن است Cycle داشته باشیم.

مثلاً:

A → B → C → A

اگر visited نداشته باشیم:

A → B → C → A → B → C → ...

Recursion هیچ‌وقت متوقف نمی‌شود.

پس قبل از رفتن به یک Node باید مطمئن شویم قبلاً پردازش نشده است.

چه زمانی visited کنیم؟

معمولاً در ابتدای ورود به Node:

visited.add(node);

یعنی وقتی Node را Discover کردیم، همان لحظه آن را Mark می‌کنیم.

این کار جلوی Loop و پردازش تکراری را می‌گیرد.

DFS با Stack

همان رفتار را می‌توان بدون Recursion پیاده‌سازی کرد.

function dfsIterative(graph, start) {
  const stack = [start];
  const visited = new Set();
  const order = [];

  while (stack.length > 0) {
    const current = stack.pop();

    if (visited.has(current)) continue;

    visited.add(current);
    order.push(current);

    const neighbors = graph[current] ?? [];

    for (let i = neighbors.length - 1; i >= 0; i--) {
      const next = neighbors[i];

      if (!visited.has(next)) {
        stack.push(next);
      }
    }
  }

  return order;
}

چرا همسایه‌ها را برعکس Push کردیم؟

Stack از قانون:

LIFO
Last In, First Out

پیروی می‌کند.

اگر بخواهیم ترتیب Iterative شبیه Recursive باشد، معمولاً همسایه‌ها را از انتها به ابتدا Push می‌کنیم.

البته ترتیب DFS به ترتیب adjacency list وابسته است و همیشه فقط یک ترتیب معتبر نداریم.

تفاوت DFS و BFS

این یکی از مهم‌ترین مقایسه‌های الگوریتمی است.

مثال

در این Tree:

        A
      /   \
     B     C
    / \   / \
   D   E F   G

DFS ممکن است:

A, B, D, E, C, F, G

باشد.

BFS:

A, B, C, D, E, F, G

DFS در Tree

در Tree چون Cycle نداریم، Traversal ساده‌تر است.

سه Traversal مشهور Binary Tree که از جنس DFS هستند:

• Preorder
• Inorder
• Postorder

Preorder

ترتیب:

Root → Left → Right

function preorder(node, result = []) {
  if (!node) return result;

  result.push(node.value);
  preorder(node.left, result);
  preorder(node.right, result);

  return result;
}

Inorder

ترتیب:

Left → Root → Right

function inorder(node, result = []) {
  if (!node) return result;

  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);

  return result;
}

در Binary Search Tree، Inorder معمولاً مقادیر را به ترتیب صعودی می‌دهد.

Postorder

ترتیب:

Left → Right → Root

function postorder(node, result = []) {
  if (!node) return result;

  postorder(node.left, result);
  postorder(node.right, result);
  result.push(node.value);

  return result;
}

Postorder در حذف Tree، محاسبه‌ی Subtree و Dependency Processing بسیار مفید است.

DFS و Connected Components

فرض کنید Graph بدون جهت Disconnected است:

A -- B     D -- E
|          |
C          F

یک DFS از A فقط Component اول را می‌بیند.

برای پیدا کردن همه Componentها:

function connectedComponents(graph) {
  const visited = new Set();
  const components = [];

  function dfs(node, component) {
    visited.add(node);
    component.push(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        dfs(next, component);
      }
    }
  }

  for (const node of Object.keys(graph)) {
    if (visited.has(node)) continue;

    const component = [];
    dfs(node, component);
    components.push(component);
  }

  return components;
}

Reachability

یکی از ساده‌ترین کاربردهای DFS:

آیا از A می‌توان به B رسید؟

function canReach(graph, start, target) {
  const visited = new Set();

  function dfs(node) {
    if (node === target) return true;
    if (visited.has(node)) return false;

    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (dfs(next)) {
        return true;
      }
    }

    return false;
  }

  return dfs(start);
}

Cycle Detection در گراف بدون جهت

در Undirected Graph یک نکته مهم داریم:

اگر از A به B رفته‌ایم، وقتی از B دوباره A را می‌بینیم، این به‌تنهایی Cycle نیست.

چون A Parent ما بوده است.

پس باید Parent را Track کنیم.

function hasCycleUndirected(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        if (dfs(next, node)) {
          return true;
        }
      } else if (next !== parent) {
        return true;
      }
    }

    return false;
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) {
      if (dfs(node, null)) {
        return true;
      }
    }
  }

  return false;
}

Cycle Detection در گراف جهت‌دار

در Directed Graph فقط visited کافی نیست.

باید بفهمیم Node در مسیر فعلی Recursion قرار دارد یا نه.

برای این کار معمولاً از سه State استفاده می‌کنیم:

0 = unvisited
1 = visiting
2 = visited

اگر از Node فعلی به Nodeای برسیم که State آن:

1

است، یعنی یک Back Edge داریم و Cycle پیدا شده است.

function hasCycleDirected(graph) {
  const state = new Map();

  function dfs(node) {
    state.set(node, 1);

    for (const next of graph[node] ?? []) {
      const nextState = state.get(next) ?? 0;

      if (nextState === 1) {
        return true;
      }

      if (nextState === 0 && dfs(next)) {
        return true;
      }
    }

    state.set(node, 2);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if ((state.get(node) ?? 0) === 0) {
      if (dfs(node)) {
        return true;
      }
    }
  }

  return false;
}

Topological Sort با DFS

Topological Sort برای Directed Acyclic Graph یا DAG استفاده می‌شود.

ایده مهم:

یک Node را زمانی وارد جواب کن که همه Dependencyهایش پردازش شده باشند.

این یعنی Postorder.

function topologicalSort(graph) {
  const visited = new Set();
  const order = [];

  function dfs(node) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        dfs(next);
      }
    }

    order.push(node);
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return order.reverse();
}

در Production بهتر است Cycle Detection نیز اضافه شود، چون Topological Sort فقط برای DAG معتبر است.

مثال واقعی Dependency

فرض کنید:

Build App
↓
Compile
↓
Install Dependencies

یا:

Course A → Course B

یعنی قبل از B باید A انجام شود.

DFS می‌تواند Dependencyها را ابتدا پردازش کند و بعد Node اصلی را در نتیجه قرار دهد.

DFS و Backtracking

Backtracking معمولاً یک DFS روی State Space است.

مثلاً در Maze:

1. یک مسیر را انتخاب کن.
2. جلو برو.
3. اگر بن‌بست شد، برگرد.
4. مسیر دیگر را امتحان کن.

این دقیقاً همان الگوی DFS است.

Maze با DFS

function solveMazeDFS(grid, start, target) {
  const rows = grid.length;
  const cols = grid[0].length;

  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
  ];

  const visited = Array.from(
    { length: rows },
    () => Array(cols).fill(false)
  );

  const path = [];

  function dfs(r, c) {
    if (
      r < 0 ||
      r >= rows ||
      c < 0 ||
      c >= cols
    ) {
      return false;
    }

    if (grid[r][c] === "#") return false;
    if (visited[r][c]) return false;

    visited[r][c] = true;
    path.push([r, c]);

    if (r === target[0] && c === target[1]) {
      return true;
    }

    for (const [dr, dc] of directions) {
      if (dfs(r + dr, c + dc)) {
        return true;
      }
    }

    path.pop();

    return false;
  }

  const found = dfs(start[0], start[1]);

  return found ? path : null;
}

آیا DFS کوتاه‌ترین مسیر را پیدا می‌کند؟

خیر، نه به صورت عمومی.

DFS اولین مسیری را که پیدا کند ممکن است بسیار طولانی باشد.

مثلاً:

A → B → C → D → E → Target

را قبل از:

A → X → Target

پیدا کند.

پس برای Shortest Path در Unweighted Graph معمولاً:

BFS

بهتر است.

DFS روی Grid

بسیاری از مسائل Grid با DFS حل می‌شوند.

مثلاً:

• Number of Islands
• Flood Fill
• Connected Regions
• Maze Reachability
• Region Counting

Number of Islands

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  let count = 0;

  function dfs(r, c) {
    if (
      r < 0 ||
      r >= rows ||
      c < 0 ||
      c >= cols
    ) {
      return;
    }

    if (grid[r][c] !== "1") {
      return;
    }

    grid[r][c] = "0";

    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

هر بار که یک Land جدید پیدا می‌کنیم، DFS تمام Island همان ناحیه را Mark می‌کند.

Flood Fill

در ابزار Paint، اگر روی یک Pixel کلیک کنیم و بخواهیم ناحیه‌ی متصل هم‌رنگ تغییر کند، DFS یا BFS قابل استفاده است.

Pixel = Vertex
Adjacent Pixel = Edge

DFS در File System

فرض کنید:

Folder
├── file1
├── subfolder
│   ├── file2
│   └── file3

برای پیمایش Recursive پوشه‌ها، DFS طبیعی است.

یک پوشه را باز می‌کنیم، محتوای داخلش را کامل بررسی می‌کنیم و بعد به سطح قبلی برمی‌گردیم.

DFS در DOM

ساختار DOM یک Tree است.

برای پیمایش Nodeهای DOM نیز می‌توان DFS اجرا کرد.

مثلاً:

function walkDOM(node) {
  console.log(node.nodeName);

  for (const child of node.children) {
    walkDOM(child);
  }
}

DFS و Dependency Graph

در Build Systemها، Package Managerها و Task Schedulerها، DFS برای:

• کشف Dependencyها
• تشخیص Circular Dependency
• ترتیب پردازش

بسیار رایج است.

DFS و Strongly Connected Components

الگوریتم‌هایی مثل:

• Kosaraju
• Tarjan

به‌شدت روی DFS تکیه دارند.

DFS فقط Traversal ساده نیست؛ بلکه زمان ورود و خروج، Stack و Back Edgeها اطلاعات ساختاری مهمی از Graph می‌دهند.

Discovery Time و Finish Time

در DFS می‌توان زمان ورود و خروج هر Node را ثبت کرد.

مثلاً:

discover[A] = 1
finish[A] = 10

این ایده در الگوریتم‌های پیشرفته مثل:

• Topological Sort
• SCC
• Bridge
• Articulation Point

بسیار مهم است.

Edge Classification در Directed Graph

در DFS روی Directed Graph، Edgeها را می‌توان به انواع مختلف تقسیم کرد:

• Tree Edge
• Back Edge
• Forward Edge
• Cross Edge

مهم‌ترین مورد برای Cycle Detection:

Back Edge

است.

اگر Edge به Ancestor فعال در recursion stack برگردد، Cycle داریم.

DFS و Bridges

Bridge یالی است که اگر حذف شود تعداد Connected Componentها افزایش می‌یابد.

الگوریتم معروف Tarjan برای پیدا کردن Bridgeها از DFS و دو مقدار استفاده می‌کند:

disc[u]
low[u]

پس DFS پایه‌ی بسیاری از مسائل Structural Graph Analysis است.

DFS و Articulation Points

Articulation Point رأسی است که حذف آن Graph را disconnectedتر می‌کند.

این مسئله نیز با DFS Tree و Low-Link Values حل می‌شود.

Recursive DFS یا Iterative DFS؟

Recursive

مزایا:

• ساده‌تر
• نزدیک‌تر به تعریف الگوریتم
• مناسب Tree و Backtracking

معایب:

• محدودیت Call Stack
• خطر Stack Overflow

Iterative

مزایا:

• کنترل کامل روی Stack
• مناسب Graphهای بسیار عمیق
• جلوگیری از Recursion Limit

معایب:

• کمی Verboseتر
• در بعضی الگوریتم‌های Postorder پیچیده‌تر

مشکل Stack Overflow

اگر Graph یک Chain خیلی بلند باشد:

1 → 2 → 3 → 4 → ... → 100000

Recursive DFS ممکن است Call Stack را پر کند.

در JavaScript این موضوع مهم است.

برای Graphهای بزرگ و عمیق، Iterative DFS با Stack دستی امن‌تر است.

پیچیدگی زمانی DFS

با adjacency list:

Time = O(V + E)

چون:

• هر Vertex حداکثر یک بار Visit می‌شود.
• هر Edge تعداد محدودی بررسی می‌شود.

در Undirected Graph هر Edge معمولاً دو بار در adjacency list دیده می‌شود، اما:

O(2E) = O(E)

پیچیدگی فضایی

برای:

• visited
• recursion stack یا stack
• auxiliary structures

معمولاً:

O(V)

حافظه کمکی داریم.

اگر خود Graph را هم حساب کنیم:

O(V + E)

Adjacency Matrix

اگر Graph با Matrix ذخیره شود، برای پیدا کردن همسایه‌های هر Node باید یک Row کامل را Scan کنیم.

در نتیجه DFS ممکن است:

O(V²)

زمان بگیرد.

DFS در Directed و Undirected Graph

DFS در هر دو نوع Graph کار می‌کند.

اما منطق بعضی مسئله‌ها فرق دارد.

مثلاً Cycle Detection:

Undirected:
visited + parent

Directed:
visited state / recursion stack

DFS برای تمام Graph

اگر Graph Disconnected است، یک DFS کافی نیست.

باید:

for (const node of Object.keys(graph)) {
  if (!visited.has(node)) {
    dfs(node);
  }
}

را اجرا کنیم.

Entry و Exit Event

در DFS دو لحظه مهم داریم:

Enter node
Exit node

مثلاً:

function dfs(node) {
  console.log("enter", node);

  for (const next of graph[node] ?? []) {
    if (!visited.has(next)) {
      dfs(next);
    }
  }

  console.log("exit", node);
}

این تفاوت بین Preorder و Postorder را ایجاد می‌کند.

Backtracking دقیقاً چه فرقی با DFS دارد؟

DFS یک Strategy برای پیمایش State Space است.

Backtracking معمولاً DFSای است که:

• یک انتخاب انجام می‌دهد،
• State را تغییر می‌دهد،
• Recursively ادامه می‌دهد،
• بعد State را Undo می‌کند.

مثلاً:

path.push(choice);

search();

path.pop();

پس:

Backtracking ≈ DFS + choose + undo

مثال Permutation با Backtracking

function permutations(nums) {
  const result = [];
  const used = Array(nums.length).fill(false);
  const current = [];

  function dfs() {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      used[i] = true;
      current.push(nums[i]);

      dfs();

      current.pop();
      used[i] = false;
    }
  }

  dfs();

  return result;
}

این Graph ظاهری ندارد، اما State Space به صورت Tree جست‌وجو می‌شود.

DFS و Memoization

در بعضی State Spaceها ممکن است یک State از مسیرهای مختلف دوباره دیده شود.

در این حالت می‌توان DFS را با Memoization ترکیب کرد.

این ایده پایه‌ی بسیاری از Top-Down Dynamic Programmingهاست.

کاربردهای واقعی DFS

1. File System Traversal

پیمایش Recursive پوشه‌ها و فایل‌ها.

2. Dependency Analysis

کشف Dependencyها و Circular Dependency.

3. Compiler و Build Systems

پردازش Graph وابستگی Moduleها.

4. Maze و Puzzle

بررسی Reachability و Backtracking.

5. Network Topology

Connected Components، Cycle و Structural Analysis.

6. DOM Traversal

پیمایش درخت DOM.

7. Source Code Analysis

پیمایش AST و Dependency Graph.

8. AI Search

بعضی Search Spaceها با DFS یا Depth-Limited DFS بررسی می‌شوند.

Depth-Limited Search

اگر نخواهیم DFS بی‌نهایت عمیق شود، می‌توانیم Limit قرار دهیم.

function depthLimitedDFS(
  graph,
  start,
  target,
  limit
) {
  const path = [];

  function dfs(node, depth) {
    if (depth > limit) {
      return false;
    }

    path.push(node);

    if (node === target) {
      return true;
    }

    for (const next of graph[node] ?? []) {
      if (dfs(next, depth + 1)) {
        return true;
      }
    }

    path.pop();

    return false;
  }

  return dfs(start, 0) ? path : null;
}

در Graph واقعی باید Cycle Control نیز اضافه شود.

Iterative Deepening DFS

IDDFS چند بار Depth-Limited DFS را اجرا می‌کند:

depth = 0
depth = 1
depth = 2
...

تا Target پیدا شود.

این روش بعضی مزایای BFS و DFS را ترکیب می‌کند:

• حافظه کم مثل DFS
• پیدا کردن کم‌عمق‌ترین جواب در بعضی State Spaceها

اشتباهات رایج DFS

1. فراموش کردن visited

باعث Loop در Graph دارای Cycle می‌شود.

2. استفاده از یک visited اشتباه در Backtracking

در بعضی مسائل باید State بعد از recursion Undo شود.

در بعضی دیگر visited باید دائمی بماند.

تشخیص این تفاوت مهم است.

3. فرض کردن DFS کوتاه‌ترین مسیر می‌دهد

نمی‌دهد.

4. فراموش کردن Componentهای جدا

یک Start فقط بخش reachable را می‌بیند.

5. Recursion خیلی عمیق

ممکن است Stack Overflow ایجاد شود.

6. اشتباه در Directed Cycle Detection

فقط visited کافی نیست؛ باید recursion stack یا state سه‌رنگی داشته باشیم.

7. تغییر Graph بدون کنترل

در بعضی DFSها حذف Edge یا Node در حین iteration می‌تواند traversal را خراب کند.

نسخه TypeScript

type Graph = Record<string, string[]>;

function dfs(
  graph: Graph,
  start: string
): string[] {
  const visited = new Set<string>();
  const order: string[] = [];

  function visit(node: string): void {
    if (visited.has(node)) {
      return;
    }

    visited.add(node);
    order.push(node);

    for (const next of graph[node] ?? []) {
      visit(next);
    }
  }

  visit(start);

  return order;
}

چه زمانی DFS انتخاب خوبی است؟

وقتی:

• Traverse عمقی می‌خواهیم.
• Cycle Detection داریم.
• Connected Components می‌خواهیم.
• Topological Sort لازم داریم.
• Dependency Graph تحلیل می‌کنیم.
• Backtracking انجام می‌دهیم.
• Tree Traversal داریم.
• Reachability مهم است.
• Grid Regionها را بررسی می‌کنیم.
• SCC، Bridge یا Articulation Point می‌سازیم.

چه زمانی DFS مناسب نیست؟

اگر کوتاه‌ترین مسیر بدون وزن لازم است:

BFS

معمولاً بهتر است.

اگر Shortest Path وزن‌دار می‌خواهیم:

Dijkstra / Bellman-Ford

بسته به وزن‌ها مطرح می‌شود.

اگر Search Space بسیار عمیق است و Recursion Limit مشکل ایجاد می‌کند، نسخه Iterative بهتر است.

جدول تصمیم سریع

جمع‌بندی

Depth-First Search یکی از مهم‌ترین الگوریتم‌های پایه در Graph و Tree است.

الگوی آن ساده است:

Go deep
→ hit dead end
→ backtrack
→ try another branch

DFS را می‌توان با Recursion یا Stack پیاده‌سازی کرد.

با adjacency list پیچیدگی معمول آن:

O(V + E)

و حافظه کمکی:

O(V)

است.

اما ارزش واقعی DFS فقط در Traversal نیست. DFS پایه‌ی بسیاری از الگوریتم‌های مهم است:

Cycle Detection
Connected Components
Topological Sort
SCC
Bridges
Articulation Points
Backtracking
Tree Traversal

مهم‌ترین Pattern برای تشخیص DFS این است:

آیا باید یک شاخه را عمیق بررسی کنم؟
آیا باید در بن‌بست برگردم؟
آیا ساختار Dependency یا Cycle مهم است؟
آیا مسئله ذاتاً Recursive است؟

→ DFS