BFS dan DFS adalah dua cara menelusuri graph: mulai dari satu node, lalu mengunjungi semua node yang bisa dicapai lewat edge, masing-masing sekali. BFS (breadth-first search) melebar dulu: semua tetangga terdekat, baru yang lebih jauh. DFS (depth-first search) menyelam dulu: terus masuk lewat satu jalur sampai buntu, baru mundur. Kayak mencari kunci di rumah: BFS mengecek semua ruangan di lantai satu dulu, DFS masuk satu kamar, buka lemari, buka laci, baru pindah kamar.
🧪 Tebakan cepat: kamu mau mencari jalan terpendek ke pintu keluar labirin. Pakai BFS atau DFS? Tebak dulu, jawabannya ada di bagian "Kenapa BFS menemukan jalur terpendek".
BFS: lapis demi lapis, pakai queue
const graph = {
A: ["B", "C"],
B: ["A", "D", "E"],
C: ["A", "E", "F"],
D: ["B"],
E: ["B", "C"],
F: ["C"],
};
function bfs(graph, start) {
const order = [];
const queue = [start]; // node yang menunggu dikunjungi
const seen = new Set([start]); // node yang sudah pernah ditemukan
while (queue.length > 0) {
const node = queue.shift(); // ambil dari depan
order.push(node);
for (const next of graph[node]) {
if (!seen.has(next)) {
seen.add(next);
queue.push(next); // masuk ke belakang
}
}
}
return order;
}
console.log(bfs(graph, "A")); // ["A", "B", "C", "D", "E", "F"]
graphadalah adjacency list: tiap node punya array tetangganya. Tetangga diproses sesuai urutan di array itu.queueadalah antrean: diisi dari belakang (push), diambil dari depan (shift). Yang ditemukan duluan, dikunjungi duluan.seenadalahSetberisi node yang sudah ditemukan. Tanpa ini, A menemukan B, B menemukan A lagi, dan loop-nya gak pernah berhenti.- Node ditandai di
seenwaktu masuk queue, bukan waktu dikunjungi, supaya gak masuk queue dua kali.
| Ambil | Tetangga baru, masuk queue | Queue sesudahnya | Urutan kunjungan |
|---|---|---|---|
| A | B, C | B, C | A |
| B | D, E | C, D, E | A, B |
| C | F (A dan E sudah ditemukan) | D, E, F | A, B, C |
| D, E, F | (gak ada) | (kosong) | A, B, C, D, E, F |
DFS: masuk sedalam mungkin
function dfs(graph, node, seen = new Set(), order = []) {
seen.add(node);
order.push(node);
for (const next of graph[node]) {
if (!seen.has(next)) dfs(graph, next, seen, order); // masuk lebih dalam dulu
}
return order;
}
console.log(dfs(graph, "A")); // ["A", "B", "D", "E", "C", "F"]
DFS langsung masuk ke tetangga pertama yang belum dikunjungi, dengan memanggil dirinya sendiri (rekursi). Dari A ke B, dari B ke D. D buntu, jadi mundur ke B dan lanjut ke E. Dari E ke C, dari C ke F. Panggilan yang masih menunggu disimpan di call stack, jadi DFS sebenarnya memakai stack, sedangkan BFS memakai queue.
Kenapa BFS menemukan jalur terpendek
BFS mengunjungi semua node yang jaraknya 1 edge dari start, lalu semua yang 2 edge, dan seterusnya. Jadi pertama kali BFS menemukan sebuah node, jalurnya pasti yang paling sedikit edge-nya. Di graph tadi, BFS menemukan F lewat A, C, F (2 edge), sedangkan DFS lewat A, B, E, C, F (4 edge). Jawaban tebakannya: BFS.
Ini berlaku di graph tanpa bobot (unweighted), di mana tiap edge dianggap sama panjang. Kalau edge punya bobot seperti jarak dalam km, pakai Dijkstra. Keduanya, BFS dan DFS, mengunjungi tiap node sekali dan memeriksa tiap edge, jadi waktunya sebanding dengan jumlah node ditambah jumlah edge.
⚠️ Jebakan yang sering ketemu
- Lupa
seen. Graph bisa punya cycle, jadi tanpa catatan, node yang sama dikunjungi berulang-ulang dan loop-nya gak berhenti. - Menandai terlambat. Kalau node baru ditandai waktu diambil dari queue, node yang sama bisa masuk queue dua kali dan muncul dua kali di hasil.
- Mengambil dari belakang.
queue.pop()mengambil yang terakhir masuk, dan hasilnya jadi menyelam seperti DFS. BFS selalu mengambil dari depan denganshift(). shift()di graph besar.shiftmenggeser semua isi array. Untuk queue yang sangat panjang, pakai index penunjuk:const node = queue[head++]denganlet head = 0.
TL;DR: BFS menelusuri graph lapis demi lapis dengan queue: ambil dari depan, masukkan tetangga baru ke belakang, dan catat yang sudah ditemukan di Set. DFS masuk sedalam mungkin lewat rekursi (stack), lalu mundur kalau buntu. BFS menjamin jalur terpendek di graph tanpa bobot. Keduanya perlu mencatat node yang sudah ditemukan, karena graph bisa punya cycle.
