חיפוש לרוחב מול חיפוש לעומק - מה ההבדל ומתי להשתמש בכל אחד?

BFS (Breadth-First Search, חיפוש לרוחב) ו-DFS (Depth-First Search, חיפוש לעומק) הם שני אלגוריתמי הסריקה הבסיסיים לגרפים ועצים. שניהם מבקרים את כל הצמתים ב-O(V + E), אך בסדר שונה לחלוטין - עם השלכות שונות על תוצאות החיפוש.

BFS - חיפוש שכבה אחר שכבה

BFS מתחיל מהצומת ההתחלתי, מבקר את כל שכניו, ואז את שכני-השכנים, וכך הלאה. מממש עם תור (Queue). מובטח שימצא את המסלול הקצר ביותר (במספר קשתות) בגרף לא-משוקלל.

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

DFS - חיפוש לעומק עד הקצה

DFS מתחיל מהצומת ההתחלתי וממשיך לעומק עד שלא ניתן להמשיך, אז חוזר אחורה ומנסה כיוון אחר. מממש עם מחסנית (Stack) - רקורסיבית או איטרטיבית.

function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

השוואה

מתי לבחור BFS?

• מציאת המסלול הקצר ביותר (מספר קצבאות) בגרף לא-משוקלל
• רשתות חברתיות (מציאת 'מרחק' בין אנשים)
• בעיות 'שכבות' כמו מציאת רדיוס, חיבוריות לפי עומק

מתי לבחור DFS?

• בדיקת קיום מסלול בין שני צמתים
• מציאת מחזורים (Cycle Detection) בגרף
• Topological Sort של DAG
• פתרון מבוכים ו-backtracking
• רכיבים קשירים (Connected Components)