Graph Traversal | التنقل في الـ Graph

إيه هو Graph Traversal؟

🗺️ الفكرة الأساسية

📖 تشبيه استكشاف المتاهة

تخيل إنك في متاهة وعايز تزور كل الغرف:

• BFS: زور كل الغرف القريبة الأول، بعدين الأبعد
• DFS: روح في اتجاه لآخره، بعدين ارجع وجرب اتجاه تاني

🎯 الهدف

نزور كل node في الـ graph مرة واحدة بس!

مهم نتتبع الـ nodes اللي زرناها عشان ما نلفش في حلقة!

BFS

Breadth-First Search - البحث بالعرض

🌊 إزاي BFS بيشتغل؟

1. ابدأ من node معينة، ضيفها في الـ Queue

2. طلّع أول node من الـ Queue

3. زورها، وضيف كل جيرانها (neighbors) في الـ Queue

4. كرر لحد ما الـ Queue يفضى

📦 بيستخدم Queue (FIFO)

First In, First Out - اللي يدخل الأول يخرج الأول

BFS Order

بيزور level by level

DFS

Depth-First Search - البحث بالعمق

⬇️ إزاي DFS بيشتغل؟

1. ابدأ من node معينة، ضيفها في الـ Stack

2. طلّع آخر node من الـ Stack (pop)

3. زورها، وضيف كل جيرانها في الـ Stack

4. كرر لحد ما الـ Stack يفضى

📚 بيستخدم Stack (LIFO)

Last In, First Out - اللي يدخل الأخير يخرج الأول

أو ممكن نستخدم Recursion!

DFS Order

بينزل للعمق الأول، بعدين يرجع

INTERACTIVE

BFS vs DFS Demo

Unvisited

Current

In Queue/Stack

Visited

Queue (BFS)

Stack (DFS)

Click "BFS" or "DFS" to start.

Visit Order:

BFS vs DFS

المقارنة	BFS	DFS
Data Structure	Queue	Stack / Recursion
Time	O(V + E)	O(V + E)
Space	O(V)	O(V)
Shortest Path?	✓ Yes	✗ No
الأفضل لـ	Shortest path, Level-order	Cycle detection, Topological sort

Implementation

BFS.js

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

DFS.js

function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  
  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    
    visited.add(node);
    console.log(node);
    
    for (const neighbor of graph[node]) {
      stack.push(neighbor);
    }
  }
}