BFS (Breadth-First Search) dan DFS (Depth-First Search) adalah dua cara dasar menjelajahi graph. Hampir semua algoritma graph lainnya dibangun di atas keduanya.

BFS — Breadth-First Search

BFS menjelajahi graph level demi level — kunjungi semua tetangga langsung dulu, baru tetangga-tetangga dari tetangga. Mirip riak air yang menyebar.

Struktur data kunci: Queue (FIFO)

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

  while (queue.length > 0) {
    const node = queue.shift(); // ambil depan (FIFO)
    order.push(node);

    for (const neighbor of adj[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor); // tambah ke belakang
      }
    }
  }
  return order;
}

const adj = { A: ["B", "C"], B: ["A", "D"], C: ["A", "E"], D: ["B"], E: ["C"] };
bfs(adj, "A"); // ["A", "B", "C", "D", "E"]

Kegunaan BFS:

• Shortest path di unweighted graph — level = jarak terpendek dari start
• Social network: "teman dari teman" (friend suggestion)
• Web crawler: jelajahi halaman level demi level
• Cek graph connected: apakah semua node bisa dicapai dari start?

DFS — Depth-First Search

DFS menjelajahi sedalam mungkin sebelum mundur (backtrack). Mirip eksplorasi labirin — ikuti satu jalan sampai mentok.

Struktur data kunci: Stack (LIFO) — atau call stack (rekursi)

// Rekursif (paling umum)
function dfs(adj, node, visited = new Set(), order = []) {
  if (visited.has(node)) return order;
  visited.add(node);
  order.push(node);

  for (const neighbor of adj[node]) {
    dfs(adj, neighbor, visited, order);
  }
  return order;
}

// Iteratif dengan stack
function dfsIter(adj, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const node = stack.pop(); // ambil atas (LIFO)
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);

    for (const neighbor of adj[node]) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return order;
}

Kegunaan DFS:

• Topological sort (urutan dependency)
• Cycle detection di graph
• Connected components — temukan semua kluster
• Maze/puzzle solving (backtracking)
• Tree traversal (pre-order, in-order, post-order)

BFS vs DFS

Contoh: Shortest Path dengan BFS

// Distance dari start ke semua node (unweighted)
function bfsDistance(adj, start) {
  const dist = { [start]: 0 };
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    for (const neighbor of adj[node]) {
      if (!(neighbor in dist)) {
        dist[neighbor] = dist[node] + 1; // level + 1
        queue.push(neighbor);
      }
    }
  }
  return dist;
}

bfsDistance(adj, "A"); // { A: 0, B: 1, C: 1, D: 2, E: 2 }

Kompleksitas (keduanya): O(V + E) — kunjungi tiap node dan edge sekali.

Tip: Jika masalah tentang "jarak terpendek di unweighted graph" → BFS. Jika tentang "jelajahi semua / backtracking" → DFS.

🎭 Analogi sehari-hari (graph context): Pertama kali sampai ke kota baru. Mau eksplorasi.

• BFS: keliling 1 blok lengkap dulu, baru ke blok sebelahnya — riak air menyebar
• DFS: masuk satu jalan sampai ujung, balik kalau buntu, coba jalan lain — labirin

💡 BFS = shortest path proof: Saat node di-visit pertama kali via BFS, dijamin level minimum. Karena semua jalur lebih pendek pasti sudah dieksplor lebih dulu (Queue FIFO). DFS bisa nemu node duluan tapi mungkin lewat detour panjang.

⚠️ Jebakan umum di graph traversal:

• Lupa visited set = infinite loop di graph dengan cycle (beda dari tree yang gak ada cycle)
• Add to visited saat enqueue, bukan dequeue — kalau salah waktu, node bisa double-enqueue
• queue.shift() O(n) = traversal jadi O(VE) bukan O(V+E). Pakai pointer queue
• DFS rekursif untuk graph besar = stack overflow. Pakai iteratif dengan stack manual
• Mixed undirected/directed confusion = path direction salah

🎯 Pilih BFS atau DFS:

• Shortest path unweighted → BFS
• All paths / backtracking → DFS
• Cycle detection → DFS (lebih natural)
• Topological sort → keduanya bisa (Kahn BFS atau DFS post-order)
• Connected components → keduanya O(V+E)
• Shortest path weighted → bukan BFS/DFS — Dijkstra

🧪 Tebakan cepat: Friend-of-friend suggestion (2-degree away di social network). Pakai apa? BFS dengan distance limit 2. DFS bisa nyasar terlalu dalam, BFS pas memberhentikan di level 2.

TL;DR: BFS (queue, level-by-level, shortest unweighted path). DFS (stack/recursion, sedalam mungkin, natural cycle detection). Wajib visited set di graph. O(V+E) keduanya. Foundation hampir semua algoritma graph.