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

ابتدا همه رأس‌هایی را که یک قدم با نقطه شروع فاصله دارند بررسی کن، بعد رأس‌های دو قدم دورتر، سپس سه قدم دورتر و به همین ترتیب.

به همین دلیل BFS را جست‌وجوی سطح‌به‌سطح می‌نامیم. BFS فقط برای Traverse کردن گراف نیست؛ در گراف بدون وزن یا گرافی که تمام یال‌ها هزینه یکسان دارند، کوتاه‌ترین مسیر را بر اساس تعداد یال‌ها پیدا می‌کند.

در این مقاله BFS را از پایه بررسی می‌کنیم: Queue، visited، Level، Shortest Path، Parent، BFS روی Grid و Maze، Multi-Source BFS، Bidirectional BFS، 0-1 BFS، کاربردهای واقعی، پیچیدگی و خطاهای رایج در JavaScript و TypeScript.

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

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

Code

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

اگر از A شروع کنیم، BFS ابتدا خود A را می‌بیند، بعد همسایه‌های مستقیم آن یعنی B و C و سپس رأس‌های دورتر یعنی D و E.

Code

Level 0: A
Level 1: B, C
Level 2: D, E

این ترتیب Level-by-Level همان چیزی است که BFS را برای پیدا کردن نزدیک‌ترین Node و Shortest Path در گراف بدون وزن مناسب می‌کند.

ایده اصلی BFS: چرا Queue؟

BFS از Queue استفاده می‌کند. Queue از اصل زیر پیروی می‌کند:

Code

FIFO
First In, First Out

یعنی هر چیزی که زودتر وارد Queue شود، زودتر پردازش می‌شود. این رفتار باعث می‌شود تمام رأس‌های یک Level قبل از رفتن به Level بعدی پردازش شوند.

اگر به‌جای Queue از Stack استفاده کنیم، رفتار به DFS نزدیک می‌شود.

مراحل اصلی BFS

رأس شروع را visited می‌کنیم.
آن را داخل Queue قرار می‌دهیم.
اولین عنصر Queue را برمی‌داریم.
همسایه‌های دیده‌نشده را پیدا می‌کنیم.
هر همسایه جدید را بلافاصله visited و سپس enqueue می‌کنیم.
تا خالی شدن Queue یا رسیدن به هدف ادامه می‌دهیم.

چرا visited ضروری است؟

گراف می‌تواند Cycle داشته باشد:

Code

A → B → C → A

بدون visited ممکن است الگوریتم برای همیشه تکرار شود:

Code

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

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

بهترین الگو این است که Node را هنگام اضافه کردن به Queue visited کنیم:

JavaScript

visited.add(next);
queue.push(next);

نه زمانی که از Queue خارج می‌شود. در غیر این صورت یک Node ممکن است از چند Parent مختلف چند بار وارد Queue شود.

پیاده‌سازی ساده BFS با JavaScript

JavaScript

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

  while (queue.length > 0) {
    const current = queue.shift();

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

مثال:

JavaScript

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "E"],
  D: ["B"],
  E: ["B", "C"]
};

console.log(bfs(graph, "A"));

خروجی می‌تواند باشد:

JSON

["A", "B", "C", "D", "E"]

نکته Performance در JavaScript: از shift زیاد استفاده نکن

Array.shift() برای Queueهای بزرگ می‌تواند هزینه‌بر باشد. نسخه بهتر:

JavaScript

function bfsOptimized(graph, start) {
  const queue = [start];
  let head = 0;

  const visited = new Set([start]);
  const order = [];

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

در این روش هیچ عنصر فیزیکی از ابتدای Array حذف نمی‌شود.

BFS چگونه Shortest Path پیدا می‌کند؟

اگر تمام یال‌ها هزینه یکسان داشته باشند، BFS رأس‌ها را بر اساس تعداد Edge از Start پردازش می‌کند.

پس اولین بار که به یک Node می‌رسیم، کمترین تعداد Edge از Start تا آن Node را پیدا کرده‌ایم.

محاسبه Distance

JavaScript

function bfsDistances(graph, start) {
  const queue = [start];
  let head = 0;

  const distance = {
    [start]: 0
  };

  while (head < queue.length) {
    const current = queue[head++];

    for (const next of graph[current] ?? []) {
      if (distance[next] !== undefined) continue;

      distance[next] = distance[current] + 1;
      queue.push(next);
    }
  }

  return distance;
}

مثلاً:

Code

A = 0
B = 1
C = 1
D = 2
E = 2

بازسازی خود Shortest Path با Parent

اگر فقط Distance کافی نیست و خود مسیر را می‌خواهیم، Parent هر Node را ذخیره می‌کنیم.

JavaScript

function shortestPathBFS(graph, start, target) {
  const queue = [start];
  let head = 0;

  const visited = new Set([start]);
  const parent = new Map();

  while (head < queue.length) {
    const current = queue[head++];

    if (current === target) break;

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      parent.set(next, current);
      queue.push(next);
    }
  }

  if (!visited.has(target)) {
    return null;
  }

  const path = [];
  let current = target;

  while (current !== undefined) {
    path.push(current);

    if (current === start) break;

    current = parent.get(current);
  }

  return path.reverse();
}

مثلاً:

Code

A → B → D

می‌تواند کوتاه‌ترین مسیر از A به D باشد.

چرا BFS برای Weighted Graph عمومی مناسب نیست؟

فرض کنید:

Code

A → B cost 100
A → C cost 1
C → B cost 1

BFS از نظر تعداد Edge مسیر مستقیم A → B را کوتاه‌تر می‌داند، اما هزینه آن 100 است.

مسیر:

Code

A → C → B

دو Edge دارد ولی هزینه کل آن 2 است.

پس BFS تعداد Edgeها را کمینه می‌کند، نه مجموع Weightها را.

برای وزن‌های مثبت متفاوت معمولاً باید از Dijkstra استفاده کنیم.

اگر همه Edgeها وزن یکسان داشته باشند، BFS همچنان درست است.

تفاوت BFS و DFS

ویژگی	BFS	DFS
ساختار اصلی	Queue	Stack / Recursion
نحوه حرکت	سطح‌به‌سطح	عمقی
Shortest Path بدون وزن	تضمین می‌کند	تضمین ندارد
مناسب برای Level	بله	معمولاً نه
کاربرد رایج	nearest node، shortest path، levels	cycle، backtracking، topo

مثلاً برای:

Code

        A
      /   \
     B     C
    / \     \
   D   E     F

BFS:

Code

A, B, C, D, E, F

DFS ممکن است:

Code

A, B, D, E, C, F

باشد.

Level Order Traversal در Tree

BFS روی Tree معمولاً Level Order Traversal نامیده می‌شود.

JavaScript

function levelOrder(root) {
  if (!root) return [];

  const queue = [root];
  let head = 0;
  const result = [];

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];

      level.push(node.value);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

خروجی:

JSON

[
  [1],
  [2, 3],
  [4, 5, 6]
]

BFS روی Grid و Maze

یک Grid را می‌توان به Graph تبدیل کرد:

هر Cell = Vertex
هر حرکت مجاز = Edge

اگر هر حرکت Cost یکسان داشته باشد، BFS کوتاه‌ترین تعداد Move را پیدا می‌کند.

Code

S . # .
. . # .
# . . T

Code

S = Start
T = Target
# = Wall

جهت‌های حرکت چهارگانه

JavaScript

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

پیاده‌سازی Maze BFS

JavaScript

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

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

  const queue = [[start[0], start[1], 0]];
  let head = 0;

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

  visited[start[0]][start[1]] = true;

  while (head < queue.length) {
    const [r, c, dist] = queue[head++];

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

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (
        nr < 0 ||
        nr >= rows ||
        nc < 0 ||
        nc >= cols
      ) {
        continue;
      }

      if (visited[nr][nc]) continue;
      if (grid[nr][nc] === "#") continue;

      visited[nr][nc] = true;
      queue.push([nr, nc, dist + 1]);
    }
  }

  return -1;
}

کاربرد در Social Network

اگر:

Code

User = Vertex
Friendship = Edge

باشد، BFS می‌تواند کمترین تعداد واسطه بین دو کاربر را پیدا کند.

Levelها:

Code

Level 1 = Friends
Level 2 = Friends of Friends
Level 3 = ...

مفهوم Degree of Separation مستقیماً با همین مدل قابل توضیح است.

Web Crawler لایه‌ای

اگر:

Code

Page = Vertex
Link = Edge

باشد، BFS می‌تواند صفحات را بر اساس Depth از صفحه شروع Crawl کند:

Code

depth 0
depth 1
depth 2
...

در سیستم واقعی باید duplicate detection، URL normalization، rate limiting و robots.txt نیز مدیریت شوند.

Connected Components با BFS

در Graph بدون جهت می‌توان از هر Node دیده‌نشده BFS اجرا کرد و Componentها را ساخت.

JavaScript

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

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

    const queue = [start];
    let head = 0;
    const component = [];

    visited.add(start);

    while (head < queue.length) {
      const current = queue[head++];
      component.push(current);

      for (const next of graph[current] ?? []) {
        if (visited.has(next)) continue;

        visited.add(next);
        queue.push(next);
      }
    }

    components.push(component);
  }

  return components;
}

Multi-Source BFS چیست؟

گاهی چند Start همزمان داریم.

مثلاً چند بیمارستان داریم و برای هر منطقه نزدیک‌ترین بیمارستان را می‌خواهیم.

در این حالت همه Sourceها را با Distance صفر داخل Queue قرار می‌دهیم.

JavaScript

function multiSourceBFS(graph, sources) {
  const queue = [...sources];
  let head = 0;

  const distance = new Map();

  for (const source of sources) {
    distance.set(source, 0);
  }

  while (head < queue.length) {
    const current = queue[head++];

    for (const next of graph[current] ?? []) {
      if (distance.has(next)) continue;

      distance.set(
        next,
        distance.get(current) + 1
      );

      queue.push(next);
    }
  }

  return distance;
}

کاربردها:

نزدیک‌ترین Hospital
نزدیک‌ترین Server
Fire Spread
Infection Spread
nearest exit
distance to water
distance transform

Bidirectional BFS چیست؟

اگر Start و Target مشخص باشند، گاهی می‌توان همزمان:

از Start جلو رفت.
از Target به عقب آمد.

وقتی دو Search Front به هم برسند، مسیر پیدا شده است.

اگر branching factor برابر b و عمق جواب d باشد، BFS عادی تقریباً با فضای:

Code

b^d

مواجه است، در حالی که Bidirectional BFS به‌صورت ایده‌آل دو جست‌وجوی عمق d/2 دارد:

Code

b^(d/2)

این تفاوت در Graphهای بزرگ می‌تواند بسیار مهم باشد.

0-1 BFS چیست؟

اگر Weight یال‌ها فقط 0 یا 1 باشند، می‌توان از نسخه‌ای به نام 0-1 BFS استفاده کرد.

در این حالت از Deque استفاده می‌کنیم:

Weight 0 → ابتدای Deque
Weight 1 → انتهای Deque

این روش برای چنین Graphهایی از BFS معمولی مناسب‌تر است و معمولاً از اجرای Dijkstra عمومی سبک‌تر است.

Bipartite Graph با BFS

می‌توان Graph را با دو رنگ رنگ کرد.

هر Neighbor باید رنگ مخالف Current داشته باشد.

JavaScript

function isBipartite(graph) {
  const color = new Map();

  for (const start of Object.keys(graph)) {
    if (color.has(start)) continue;

    const queue = [start];
    let head = 0;

    color.set(start, 0);

    while (head < queue.length) {
      const current = queue[head++];

      for (const next of graph[current] ?? []) {
        if (!color.has(next)) {
          color.set(next, 1 - color.get(current));
          queue.push(next);
        } else if (
          color.get(next) === color.get(current)
        ) {
          return false;
        }
      }
    }
  }

  return true;
}

BFS در State Space

بسیاری از مسائل ظاهراً Graph نیستند ولی می‌توان آن‌ها را Graph مدل کرد:

Code

State = Vertex
Operation = Edge

اگر هر Operation هزینه برابر داشته باشد، BFS کمترین تعداد Operation را پیدا می‌کند.

نمونه‌ها:

Knight Moves در Chess
Word Ladder
Minimum button presses
Puzzle transformations
تبدیل عدد با مجموعه عملیات مجاز

Word Ladder

مثلاً:

Code

hit → hot → dot → dog → cog

هر Word یک State است و تغییر یک حرف یک Edge محسوب می‌شود.

BFS کمترین تعداد Transform را پیدا می‌کند.

BFS در Graph جهت‌دار

BFS در Directed Graph نیز قابل استفاده است.

اگر:

Code

A → B

باشد، لزوماً نمی‌توان از B به A رفت.

پس adjacency list باید Direction واقعی را حفظ کند.

BFS در Graph disconnected

یک BFS از Start فقط رأس‌های Reachable از آن Start را می‌بیند.

برای Traverse کل Graph:

Code

for each unvisited vertex:
    run BFS

انجام می‌دهیم.

پیچیدگی BFS

با adjacency list:

Code

Time = O(V + E)

چون هر Vertex یک بار پردازش اصلی می‌شود و هر Edge تعداد محدودی بررسی می‌شود.

حافظه کمکی:

Code

O(V)

برای Queue، visited، parent یا distance.

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

Code

O(V + E)

Adjacency Matrix

اگر Graph به صورت Matrix باشد، برای پیدا کردن Neighborهای هر Vertex ممکن است یک Row کامل را بررسی کنیم.

در نتیجه زمان می‌تواند به:

Code

O(V²)

برسد.

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

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

باعث Loop یا پردازش تکراری می‌شود.

2. visited کردن هنگام dequeue

ممکن است یک Node چند بار enqueue شود.

3. استفاده از BFS برای Weightهای متفاوت

Shortest Path تضمین نمی‌شود.

4. استفاده زیاد از shift در JavaScript

در Queue بزرگ Performance را ضعیف می‌کند.

5. فراموش کردن Componentهای دیگر

یک Start فقط بخش Reachable را پوشش می‌دهد.

6. ذخیره نکردن Parent

اگر خود Path را لازم دارید، Distance کافی نیست.

7. خطای Boundary در Grid

همیشه باید:

Code

0 <= row < rows
0 <= col < cols

بررسی شود.

نسخه TypeScript

TypeScript

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

function bfs(
  graph: Graph,
  start: string
): string[] {
  const queue: string[] = [start];
  let head = 0;

  const visited = new Set<string>([start]);
  const order: string[] = [];

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

چه زمانی از BFS استفاده کنیم؟

BFS مناسب است وقتی:

Graph بدون وزن است.
همه Edgeها هزینه یکسان دارند.
نزدیک‌ترین Node را می‌خواهیم.
Shortest Path بر اساس تعداد Edge لازم است.
Levelها اهمیت دارند.
Minimum number of moves می‌خواهیم.
Multi-Source distance لازم داریم.
Bipartite check می‌خواهیم.
روی Tree، Level Order Traversal لازم است.

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

اگر Weightها مثبت و متفاوت‌اند:

Code

Dijkstra

اگر Weight فقط 0 و 1 است:

Code

0-1 BFS

اگر Deep exploration یا Backtracking طبیعی‌تر است:

Code

DFS

اگر Edge منفی دارید، بسته به مسئله الگوریتم‌هایی مثل Bellman-Ford مطرح می‌شوند.

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

مسئله	انتخاب مناسب
Traverse سطح‌به‌سطح	BFS
Shortest Path بدون وزن	BFS
Minimum number of moves	BFS
Shortest Path با وزن مثبت متفاوت	Dijkstra
Weight فقط 0 و 1	0-1 BFS
Traverse عمقی	DFS
چند Source همزمان	Multi-Source BFS
Start و Target مشخص	Bidirectional BFS می‌تواند مفید باشد

جمع‌بندی

Breadth-First Search با Queue کار می‌کند و Graph را به ترتیب فاصله از Start می‌پیماید:

Code

Level 0
Level 1
Level 2
...

همین ویژگی باعث می‌شود در Graph بدون وزن یا با Edgeهای هم‌هزینه، اولین بار رسیدن به یک Node کمترین تعداد Edge را تضمین کند.

پیچیدگی استاندارد BFS با adjacency list:

Code

O(V + E)

و حافظه کمکی آن معمولاً:

Code

O(V)

است.

اما نکته اصلی حفظ کردن چند خط کد نیست. باید Pattern مسئله را تشخیص دهیم:

Code

نزدیک‌ترین State؟
کمترین تعداد Move؟
Shortest Path بدون وزن؟
Level-by-Level traversal؟

→ BFS

وقتی این Pattern را ببینید، بسیاری از مسائل Maze، Grid، Social Network، Tree، Web Crawler و State Search به یک ساختار مشترک تبدیل می‌شوند.

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

ابتدا همه رأس‌هایی را که یک قدم با نقطه شروع فاصله دارند بررسی کن، بعد رأس‌های دو قدم دورتر، سپس سه قدم دورتر و به همین ترتیب.

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

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

Code

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

Code

Level 0: A
Level 1: B, C
Level 2: D, E

این ترتیب Level-by-Level همان چیزی است که BFS را برای پیدا کردن نزدیک‌ترین Node و Shortest Path در گراف بدون وزن مناسب می‌کند.

ایده اصلی BFS: چرا Queue؟

BFS از Queue استفاده می‌کند. Queue از اصل زیر پیروی می‌کند:

Code

FIFO
First In, First Out

اگر به‌جای Queue از Stack استفاده کنیم، رفتار به DFS نزدیک می‌شود.

مراحل اصلی BFS

رأس شروع را visited می‌کنیم.
آن را داخل Queue قرار می‌دهیم.
اولین عنصر Queue را برمی‌داریم.
همسایه‌های دیده‌نشده را پیدا می‌کنیم.
هر همسایه جدید را بلافاصله visited و سپس enqueue می‌کنیم.
تا خالی شدن Queue یا رسیدن به هدف ادامه می‌دهیم.

چرا visited ضروری است؟

گراف می‌تواند Cycle داشته باشد:

Code

A → B → C → A

بدون visited ممکن است الگوریتم برای همیشه تکرار شود:

Code

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

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

بهترین الگو این است که Node را هنگام اضافه کردن به Queue visited کنیم:

JavaScript

visited.add(next);
queue.push(next);

نه زمانی که از Queue خارج می‌شود. در غیر این صورت یک Node ممکن است از چند Parent مختلف چند بار وارد Queue شود.

پیاده‌سازی ساده BFS با JavaScript

JavaScript

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

  while (queue.length > 0) {
    const current = queue.shift();

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

مثال:

JavaScript

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "E"],
  D: ["B"],
  E: ["B", "C"]
};

console.log(bfs(graph, "A"));

خروجی می‌تواند باشد:

JSON

["A", "B", "C", "D", "E"]

نکته Performance در JavaScript: از shift زیاد استفاده نکن

Array.shift() برای Queueهای بزرگ می‌تواند هزینه‌بر باشد. نسخه بهتر:

JavaScript

function bfsOptimized(graph, start) {
  const queue = [start];
  let head = 0;

  const visited = new Set([start]);
  const order = [];

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

در این روش هیچ عنصر فیزیکی از ابتدای Array حذف نمی‌شود.

BFS چگونه Shortest Path پیدا می‌کند؟

اگر تمام یال‌ها هزینه یکسان داشته باشند، BFS رأس‌ها را بر اساس تعداد Edge از Start پردازش می‌کند.

پس اولین بار که به یک Node می‌رسیم، کمترین تعداد Edge از Start تا آن Node را پیدا کرده‌ایم.

محاسبه Distance

JavaScript

function bfsDistances(graph, start) {
  const queue = [start];
  let head = 0;

  const distance = {
    [start]: 0
  };

  while (head < queue.length) {
    const current = queue[head++];

    for (const next of graph[current] ?? []) {
      if (distance[next] !== undefined) continue;

      distance[next] = distance[current] + 1;
      queue.push(next);
    }
  }

  return distance;
}

مثلاً:

Code

A = 0
B = 1
C = 1
D = 2
E = 2

بازسازی خود Shortest Path با Parent

اگر فقط Distance کافی نیست و خود مسیر را می‌خواهیم، Parent هر Node را ذخیره می‌کنیم.

JavaScript

function shortestPathBFS(graph, start, target) {
  const queue = [start];
  let head = 0;

  const visited = new Set([start]);
  const parent = new Map();

  while (head < queue.length) {
    const current = queue[head++];

    if (current === target) break;

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      parent.set(next, current);
      queue.push(next);
    }
  }

  if (!visited.has(target)) {
    return null;
  }

  const path = [];
  let current = target;

  while (current !== undefined) {
    path.push(current);

    if (current === start) break;

    current = parent.get(current);
  }

  return path.reverse();
}

مثلاً:

Code

A → B → D

می‌تواند کوتاه‌ترین مسیر از A به D باشد.

چرا BFS برای Weighted Graph عمومی مناسب نیست؟

فرض کنید:

Code

A → B cost 100
A → C cost 1
C → B cost 1

BFS از نظر تعداد Edge مسیر مستقیم A → B را کوتاه‌تر می‌داند، اما هزینه آن 100 است.

مسیر:

Code

A → C → B

دو Edge دارد ولی هزینه کل آن 2 است.

پس BFS تعداد Edgeها را کمینه می‌کند، نه مجموع Weightها را.

برای وزن‌های مثبت متفاوت معمولاً باید از Dijkstra استفاده کنیم.

اگر همه Edgeها وزن یکسان داشته باشند، BFS همچنان درست است.

تفاوت BFS و DFS

ویژگی	BFS	DFS
ساختار اصلی	Queue	Stack / Recursion
نحوه حرکت	سطح‌به‌سطح	عمقی
Shortest Path بدون وزن	تضمین می‌کند	تضمین ندارد
مناسب برای Level	بله	معمولاً نه
کاربرد رایج	nearest node، shortest path، levels	cycle، backtracking، topo

مثلاً برای:

Code

        A
      /   \
     B     C
    / \     \
   D   E     F

BFS:

Code

A, B, C, D, E, F

DFS ممکن است:

Code

A, B, D, E, C, F

باشد.

Level Order Traversal در Tree

BFS روی Tree معمولاً Level Order Traversal نامیده می‌شود.

JavaScript

function levelOrder(root) {
  if (!root) return [];

  const queue = [root];
  let head = 0;
  const result = [];

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];

      level.push(node.value);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

خروجی:

JSON

[
  [1],
  [2, 3],
  [4, 5, 6]
]

BFS روی Grid و Maze

یک Grid را می‌توان به Graph تبدیل کرد:

هر Cell = Vertex
هر حرکت مجاز = Edge

اگر هر حرکت Cost یکسان داشته باشد، BFS کوتاه‌ترین تعداد Move را پیدا می‌کند.

Code

S . # .
. . # .
# . . T

Code

S = Start
T = Target
# = Wall

جهت‌های حرکت چهارگانه

JavaScript

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

پیاده‌سازی Maze BFS

JavaScript

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

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

  const queue = [[start[0], start[1], 0]];
  let head = 0;

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

  visited[start[0]][start[1]] = true;

  while (head < queue.length) {
    const [r, c, dist] = queue[head++];

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

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (
        nr < 0 ||
        nr >= rows ||
        nc < 0 ||
        nc >= cols
      ) {
        continue;
      }

      if (visited[nr][nc]) continue;
      if (grid[nr][nc] === "#") continue;

      visited[nr][nc] = true;
      queue.push([nr, nc, dist + 1]);
    }
  }

  return -1;
}

کاربرد در Social Network

اگر:

Code

User = Vertex
Friendship = Edge

باشد، BFS می‌تواند کمترین تعداد واسطه بین دو کاربر را پیدا کند.

Levelها:

Code

Level 1 = Friends
Level 2 = Friends of Friends
Level 3 = ...

مفهوم Degree of Separation مستقیماً با همین مدل قابل توضیح است.

Web Crawler لایه‌ای

اگر:

Code

Page = Vertex
Link = Edge

باشد، BFS می‌تواند صفحات را بر اساس Depth از صفحه شروع Crawl کند:

Code

depth 0
depth 1
depth 2
...

در سیستم واقعی باید duplicate detection، URL normalization، rate limiting و robots.txt نیز مدیریت شوند.

Connected Components با BFS

در Graph بدون جهت می‌توان از هر Node دیده‌نشده BFS اجرا کرد و Componentها را ساخت.

JavaScript

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

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

    const queue = [start];
    let head = 0;
    const component = [];

    visited.add(start);

    while (head < queue.length) {
      const current = queue[head++];
      component.push(current);

      for (const next of graph[current] ?? []) {
        if (visited.has(next)) continue;

        visited.add(next);
        queue.push(next);
      }
    }

    components.push(component);
  }

  return components;
}

Multi-Source BFS چیست؟

گاهی چند Start همزمان داریم.

مثلاً چند بیمارستان داریم و برای هر منطقه نزدیک‌ترین بیمارستان را می‌خواهیم.

در این حالت همه Sourceها را با Distance صفر داخل Queue قرار می‌دهیم.

JavaScript

function multiSourceBFS(graph, sources) {
  const queue = [...sources];
  let head = 0;

  const distance = new Map();

  for (const source of sources) {
    distance.set(source, 0);
  }

  while (head < queue.length) {
    const current = queue[head++];

    for (const next of graph[current] ?? []) {
      if (distance.has(next)) continue;

      distance.set(
        next,
        distance.get(current) + 1
      );

      queue.push(next);
    }
  }

  return distance;
}

کاربردها:

نزدیک‌ترین Hospital
نزدیک‌ترین Server
Fire Spread
Infection Spread
nearest exit
distance to water
distance transform

Bidirectional BFS چیست؟

اگر Start و Target مشخص باشند، گاهی می‌توان همزمان:

از Start جلو رفت.
از Target به عقب آمد.

وقتی دو Search Front به هم برسند، مسیر پیدا شده است.

اگر branching factor برابر b و عمق جواب d باشد، BFS عادی تقریباً با فضای:

Code

b^d

مواجه است، در حالی که Bidirectional BFS به‌صورت ایده‌آل دو جست‌وجوی عمق d/2 دارد:

Code

b^(d/2)

این تفاوت در Graphهای بزرگ می‌تواند بسیار مهم باشد.

0-1 BFS چیست؟

اگر Weight یال‌ها فقط 0 یا 1 باشند، می‌توان از نسخه‌ای به نام 0-1 BFS استفاده کرد.

در این حالت از Deque استفاده می‌کنیم:

Weight 0 → ابتدای Deque
Weight 1 → انتهای Deque

این روش برای چنین Graphهایی از BFS معمولی مناسب‌تر است و معمولاً از اجرای Dijkstra عمومی سبک‌تر است.

Bipartite Graph با BFS

می‌توان Graph را با دو رنگ رنگ کرد.

هر Neighbor باید رنگ مخالف Current داشته باشد.

JavaScript

function isBipartite(graph) {
  const color = new Map();

  for (const start of Object.keys(graph)) {
    if (color.has(start)) continue;

    const queue = [start];
    let head = 0;

    color.set(start, 0);

    while (head < queue.length) {
      const current = queue[head++];

      for (const next of graph[current] ?? []) {
        if (!color.has(next)) {
          color.set(next, 1 - color.get(current));
          queue.push(next);
        } else if (
          color.get(next) === color.get(current)
        ) {
          return false;
        }
      }
    }
  }

  return true;
}

BFS در State Space

بسیاری از مسائل ظاهراً Graph نیستند ولی می‌توان آن‌ها را Graph مدل کرد:

Code

State = Vertex
Operation = Edge

اگر هر Operation هزینه برابر داشته باشد، BFS کمترین تعداد Operation را پیدا می‌کند.

نمونه‌ها:

Knight Moves در Chess
Word Ladder
Minimum button presses
Puzzle transformations
تبدیل عدد با مجموعه عملیات مجاز

Word Ladder

مثلاً:

Code

hit → hot → dot → dog → cog

هر Word یک State است و تغییر یک حرف یک Edge محسوب می‌شود.

BFS کمترین تعداد Transform را پیدا می‌کند.

BFS در Graph جهت‌دار

BFS در Directed Graph نیز قابل استفاده است.

اگر:

Code

A → B

باشد، لزوماً نمی‌توان از B به A رفت.

پس adjacency list باید Direction واقعی را حفظ کند.

BFS در Graph disconnected

یک BFS از Start فقط رأس‌های Reachable از آن Start را می‌بیند.

برای Traverse کل Graph:

Code

for each unvisited vertex:
    run BFS

انجام می‌دهیم.

پیچیدگی BFS

با adjacency list:

Code

Time = O(V + E)

چون هر Vertex یک بار پردازش اصلی می‌شود و هر Edge تعداد محدودی بررسی می‌شود.

حافظه کمکی:

Code

O(V)

برای Queue، visited، parent یا distance.

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

Code

O(V + E)

Adjacency Matrix

اگر Graph به صورت Matrix باشد، برای پیدا کردن Neighborهای هر Vertex ممکن است یک Row کامل را بررسی کنیم.

در نتیجه زمان می‌تواند به:

Code

O(V²)

برسد.

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

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

باعث Loop یا پردازش تکراری می‌شود.

2. visited کردن هنگام dequeue

ممکن است یک Node چند بار enqueue شود.

3. استفاده از BFS برای Weightهای متفاوت

Shortest Path تضمین نمی‌شود.

4. استفاده زیاد از shift در JavaScript

در Queue بزرگ Performance را ضعیف می‌کند.

5. فراموش کردن Componentهای دیگر

یک Start فقط بخش Reachable را پوشش می‌دهد.

6. ذخیره نکردن Parent

اگر خود Path را لازم دارید، Distance کافی نیست.

7. خطای Boundary در Grid

همیشه باید:

Code

0 <= row < rows
0 <= col < cols

بررسی شود.

نسخه TypeScript

TypeScript

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

function bfs(
  graph: Graph,
  start: string
): string[] {
  const queue: string[] = [start];
  let head = 0;

  const visited = new Set<string>([start]);
  const order: string[] = [];

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

چه زمانی از BFS استفاده کنیم؟

BFS مناسب است وقتی:

Graph بدون وزن است.
همه Edgeها هزینه یکسان دارند.
نزدیک‌ترین Node را می‌خواهیم.
Shortest Path بر اساس تعداد Edge لازم است.
Levelها اهمیت دارند.
Minimum number of moves می‌خواهیم.
Multi-Source distance لازم داریم.
Bipartite check می‌خواهیم.
روی Tree، Level Order Traversal لازم است.

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

اگر Weightها مثبت و متفاوت‌اند:

Code

Dijkstra

اگر Weight فقط 0 و 1 است:

Code

0-1 BFS

اگر Deep exploration یا Backtracking طبیعی‌تر است:

Code

DFS

اگر Edge منفی دارید، بسته به مسئله الگوریتم‌هایی مثل Bellman-Ford مطرح می‌شوند.

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

مسئله	انتخاب مناسب
Traverse سطح‌به‌سطح	BFS
Shortest Path بدون وزن	BFS
Minimum number of moves	BFS
Shortest Path با وزن مثبت متفاوت	Dijkstra
Weight فقط 0 و 1	0-1 BFS
Traverse عمقی	DFS
چند Source همزمان	Multi-Source BFS
Start و Target مشخص	Bidirectional BFS می‌تواند مفید باشد

جمع‌بندی

Breadth-First Search با Queue کار می‌کند و Graph را به ترتیب فاصله از Start می‌پیماید:

Code

Level 0
Level 1
Level 2
...

پیچیدگی استاندارد BFS با adjacency list:

Code

O(V + E)

و حافظه کمکی آن معمولاً:

Code

O(V)

است.

اما نکته اصلی حفظ کردن چند خط کد نیست. باید Pattern مسئله را تشخیص دهیم:

Code

نزدیک‌ترین State؟
کمترین تعداد Move؟
Shortest Path بدون وزن؟
Level-by-Level traversal؟

→ BFS

وقتی این Pattern را ببینید، بسیاری از مسائل Maze، Grid، Social Network، Tree، Web Crawler و State Search به یک ساختار مشترک تبدیل می‌شوند.

الگوریتم BFS چیست؟ جست‌وجوی سطح‌به‌سطح از صفر تا صد

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

ایده اصلی BFS: چرا Queue؟

مراحل اصلی BFS

چرا visited ضروری است؟

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

پیاده‌سازی ساده BFS با JavaScript

نکته Performance در JavaScript: از shift زیاد استفاده نکن

BFS چگونه Shortest Path پیدا می‌کند؟

محاسبه Distance

بازسازی خود Shortest Path با Parent

چرا BFS برای Weighted Graph عمومی مناسب نیست؟

تفاوت BFS و DFS

Level Order Traversal در Tree

BFS روی Grid و Maze

جهت‌های حرکت چهارگانه

پیاده‌سازی Maze BFS

کاربرد در Social Network

Web Crawler لایه‌ای

Connected Components با BFS

Multi-Source BFS چیست؟

Bidirectional BFS چیست؟

0-1 BFS چیست؟

Bipartite Graph با BFS

BFS در State Space

Word Ladder

BFS در Graph جهت‌دار

BFS در Graph disconnected

پیچیدگی BFS

Adjacency Matrix

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

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

2. visited کردن هنگام dequeue

3. استفاده از BFS برای Weightهای متفاوت

4. استفاده زیاد از shift در JavaScript

5. فراموش کردن Componentهای دیگر

6. ذخیره نکردن Parent

7. خطای Boundary در Grid

نسخه TypeScript

چه زمانی از BFS استفاده کنیم؟

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

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

جمع‌بندی

الگوریتم Cuckoo Hashing چیست و چگونه کار می‌کند؟

الگوریتم DFS چیست؟ جست‌وجوی عمقی از صفر تا صد

الگوریتم BFS چیست؟ جست‌وجوی سطح‌به‌سطح از صفر تا صد

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

ایده اصلی BFS: چرا Queue؟

مراحل اصلی BFS

چرا visited ضروری است؟

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

پیاده‌سازی ساده BFS با JavaScript

نکته Performance در JavaScript: از shift زیاد استفاده نکن

BFS چگونه Shortest Path پیدا می‌کند؟

محاسبه Distance

بازسازی خود Shortest Path با Parent

چرا BFS برای Weighted Graph عمومی مناسب نیست؟

تفاوت BFS و DFS

Level Order Traversal در Tree

BFS روی Grid و Maze

جهت‌های حرکت چهارگانه

پیاده‌سازی Maze BFS

کاربرد در Social Network

Web Crawler لایه‌ای

Connected Components با BFS

Multi-Source BFS چیست؟

Bidirectional BFS چیست؟

0-1 BFS چیست؟

Bipartite Graph با BFS

BFS در State Space

Word Ladder

BFS در Graph جهت‌دار

BFS در Graph disconnected

پیچیدگی BFS

Adjacency Matrix

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

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

2. visited کردن هنگام dequeue

3. استفاده از BFS برای Weightهای متفاوت

4. استفاده زیاد از shift در JavaScript