BFS dan DFS adalah dua cara utama menjelajahi semua node di graph.

BFS (Breadth-First Search)

Kunjungi semua tetangga dulu sebelum pindah ke level berikutnya. Gunakan Queue.

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

  while (queue.length > 0) {
    const vertex = queue.shift();
    console.log(vertex);

    for (const neighbor of graph.adjacencyList.get(vertex)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}
// Dari Jakarta: Jakarta → Bandung → Surabaya → Yogya

DFS (Depth-First Search)

Masuk sedalam mungkin dulu sebelum mundur. Gunakan Stack (atau rekursi).

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

  function explore(vertex) {
    visited.add(vertex);
    console.log(vertex);

    for (const neighbor of graph.adjacencyList.get(vertex)) {
      if (!visited.has(neighbor)) {
        explore(neighbor);
      }
    }
  }

  explore(start);
}
// Dari Jakarta: Jakarta → Bandung → Yogya → Surabaya

Perbandingan:

🎭 Analogi sehari-hari: Cari kunci yang ilang di rumah.

• BFS: cek semua ruangan lantai 1 dulu, baru naik ke lantai 2 (ekspansi level-by-level)
• DFS: masuk kamar tidur, cek lemari, di dalam lemari ada laci, di laci ada kotak, cek kotak — sedalam mungkin sebelum coba kamar lain

💡 Kenapa BFS = shortest path (unweighted)? Karena BFS expand level-by-level. Saat target ditemukan, dijamin ditemukan di level paling dekat dari start. DFS bisa nemu duluan, tapi mungkin lewat jalur lebih panjang.

⚠️ Jebakan umum:

• Lupa visited Set di graph (cycle bisa terjadi) = infinite loop. Wajib selalu
• queue.shift() = O(n) per dequeue → BFS jadi O(VE). Pakai pointer-based queue
• DFS rekursif untuk graph besar = stack overflow. Iteratif pakai stack manual lebih aman
• Add to visited saat enqueue, bukan saat dequeue — kalau salah waktu, node sama bisa masuk queue 2x

🎯 BFS atau DFS untuk problem ini?

• Shortest path unweighted → BFS (mandatory)
• All possible paths → DFS
• Cycle detection → DFS (lebih natural dengan recursion)
• Topological sort → DFS post-order
• Connected components → BFS atau DFS (sama efisien)
• Memory tight + tree dalam → DFS

🧪 Tebakan cepat: Maze 1000x1000, cari pintu keluar terdekat. BFS atau DFS? BFS — DFS bisa nyasar masuk koridor panjang dulu. BFS pasti shortest.

TL;DR: BFS = level-by-level (queue), shortest path. DFS = sedalam mungkin (stack/recursion), cycle detection. Wajib visited set untuk graph.