BFS & DFS (Graph Traversal) — Algoritma

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

Graph adalah kumpulan node (titik, misalnya kota) yang disambung edge (garis, misalnya jalan). Menjelajahi graph artinya mengunjungi semua node yang bisa dicapai dari satu node awal, satu per satu. Ada dua cara dasar: BFS (breadth-first search) melebar dulu, lapis demi lapis, kayak riak air; DFS (depth-first search) masuk sedalam mungkin dulu, kayak menyusuri labirin sampai buntu lalu mundur.

🧪 Tebakan cepat: C adalah tetangga langsung A. Kalau DFS mulai dari A di graph lesson ini, C dikunjungi di urutan ke berapa: kedua, ketiga, atau terakhir? Tebak dulu, jawabannya ada di bagian "DFS: masuk sedalam mungkin".

BFS: melebar lapis demi lapis

Ada enam kota, A sampai F, dengan jalan A-B, A-C, B-D, B-E, C-F, dan E-F (semua dua arah). BFS memakai queue (antrean): yang masuk duluan keluar duluan. Mulai dari A:

Langkah	Ambil dari depan	Tetangga baru, masuk belakang	Queue sesudahnya
1	A	B, C	B, C
2	B	D, E	C, D, E
3	C	F	D, E, F
4	D	(gak ada)	E, F
5	E	(gak ada, F sudah ketemu)	F
6	F	(gak ada)	(kosong)

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

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

  while (queue.length > 0) {
    const node = queue.shift(); // ambil dari depan
    order.push(node);
    for (const next of graph[node]) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next); // masuk dari belakang
      }
    }
  }
  return order;
}

console.log(bfs(graph, "A")); // ["A", "B", "C", "D", "E", "F"]

graph adalah adjacency list: tiap kota menyimpan array tetangganya.
queue.shift() mengambil isi paling depan, queue.push(next) menaruh di paling belakang.
visited adalah Set, kumpulan nilai tanpa dobel: has mengecek, add menambah. Node ditandai begitu masuk queue, supaya gak masuk dua kali.
Hasilnya A (lapis 0), lalu tetangga A: B, C (lapis 1), lalu tetangga mereka: D, E, F (lapis 2).

Graph ini punya putaran: A-B-E-F-C-A. Tanpa visited, kota yang sama masuk queue lagi dan lagi, dan loop-nya gak pernah selesai.

Jarak terpendek dengan BFS

Karena BFS jalan lapis demi lapis, lapis sebuah node sama dengan jumlah jalan paling sedikit dari start. Ini berlaku di graph tanpa bobot (unweighted), yang tiap jalannya dihitung 1. Untuk menyimpan jaraknya, ubah bfs sedikit:

Ganti visited dengan object dist, isi awalnya dist[start] = 0: start berjarak 0 dari dirinya sendiri.
Ganti cek !visited.has(next) dengan dist[next] === undefined, artinya belum pernah ketemu.
Ganti visited.add(next) dengan dist[next] = dist[node] + 1: satu jalan lebih jauh dari node yang sedang diambil.
Kembalikan dist, bukan order.

Dari A, hasilnya { A: 0, B: 1, C: 1, D: 2, E: 2, F: 2 }. Jarak pertama yang dicatat sudah yang terpendek, karena lapis yang lebih dekat selalu diproses duluan, jadi jangan diubah lagi. Node yang gak bisa dicapai dari start gak pernah masuk dist, jadi gak ada di hasil.

DFS: masuk sedalam mungkin

DFS memakai stack (tumpukan): yang terakhir masuk keluar duluan. Cara paling gampang menulisnya adalah rekursi, function yang memanggil dirinya sendiri, karena panggilan yang belum selesai sudah ditumpuk JavaScript di call stack.

function dfs(graph, node, visited = new Set(), order = []) {
  visited.add(node);
  order.push(node);
  for (const next of graph[node]) {
    if (!visited.has(next)) dfs(graph, next, visited, order); // masuk lebih dalam
  }
  return order; // selesai di sini: mundur ke pemanggil
}

console.log(dfs(graph, "A")); // ["A", "B", "D", "E", "F", "C"]

Dari A, DFS masuk ke B (tetangga pertama A), lalu D. D buntu: tetangganya cuma B, sudah dikunjungi. DFS mundur ke B, masuk ke E, lalu F, lalu C. Jadi C, tetangga langsung A, malah dikunjungi terakhir. Itu jawaban tebakannya. visited = new Set() dan order = [] dibuat sekali di panggilan pertama, lalu dikirim ke tiap panggilan berikutnya, jadi semuanya berbagi catatan yang sama.

BFS atau DFS?

	BFS	DFS
Penyimpan	queue, yang masuk duluan keluar duluan (FIFO)	stack atau rekursi, yang terakhir masuk keluar duluan (LIFO)
Urutan	lapis demi lapis	satu jalur sampai buntu, lalu mundur
Cocok untuk	jarak terpendek (shortest path) di graph tanpa bobot	menjelajah semua jalur, mencari jalan keluar labirin, mengecek putaran

Dua-duanya O(V + E), dengan V jumlah node dan E jumlah edge: tiap node dan tiap edge didatangi sekali, jadi graph dua kali lebih besar, waktunya kira-kira dua kali lipat. Kalau jalannya punya panjang yang beda-beda (graph berbobot), BFS gak lagi memberi rute terpendek. Untuk itu ada Dijkstra.

⚠️ Jebakan yang sering ketemu

Menandai visited saat diambil, bukan saat masuk queue. F bisa masuk queue dua kali, dari C dan dari E. Tandai begitu push.
Menimpa jarak yang sudah ada. Tanpa cek dist[next] === undefined, jalan balik dari B ke A mengubah jarak A jadi 2.
queue.shift() di graph besar. shift menggeser semua isi array tiap kali dipanggil, jadi lambat untuk jutaan node. Pakai penunjuk: let head = 0; lalu const node = queue[head++];.
DFS rekursif di graph yang sangat dalam. Call stack-nya bisa penuh (stack overflow). Pakai stack sendiri: array dengan push dan pop.

TL;DR: BFS memakai queue dan mengunjungi node lapis demi lapis, jadi cocok untuk jarak terpendek di graph tanpa bobot: dist[next] = dist[node] + 1 untuk tetangga yang belum punya jarak. DFS memakai stack atau rekursi dan masuk sedalam mungkin sebelum mundur. Dua-duanya butuh penanda sudah dikunjungi (visited atau dist) supaya gak berputar selamanya di graph yang punya putaran, dan dua-duanya O(V + E).