Perbedaan Depth-first Search (DFS) dan Breadth-first Search (BFS)

DFS maupun BFS adalah algoritma pencarian yang umumnya digunakan untuk menelusuri jalur pada struktur data tree ataupun graph.

Keduanya merupakan algoritma pencarian yang paling sering digunakan. Sebenarnya apa perbedaan keduanya?

Perbedaan Depth-first Search (DFS) dan Breadth-first Search (BFS)

Di artikel ini kita akan mengulas lebih rinci mengenai perbedaan algoritma Depth-first Search (DFS) dan Breadth-first Search (BFS). Yuk, simak!

Daftar Isi

Pengertian DFS

DFS atau Depth-first Search adalah algoritma untuk menemukan atau melintasi sebuah graph maupun tree dengan arah lintasan secara dalam.

Eksekusi algoritma dimulai dari simpul akar dan menjelajahi setiap cabang sebelum proses backtracking (mundur menjelajahi simpul lain).

Algoritma ini menggunakan struktur data stack untuk mengingat, mendapatkan simpul berikutnya, dan untuk memulai pencarian setiap kali jalan buntu muncul di setiap iterasi.

Pengertian BFS

BFS, kependekan dari Breadth-first Search adalah algoritma yang digunakan untuk membuat grafik data dan mencari atau melintasi struktur tree/graph.

Algoritma ini secara efisien mengunjungi dan menandai semua node kunci dalam graph dengan cara yang akurat.

Algoritma BFS memilih satu node (titik awal atau sumber) dalam graph, kemudian mengunjungi semua node yang berdekatan dengan node yang dipilih.

Setelah algoritma mengunjungi dan menandai node awal, algoritma akan bergerak menuju node terdekat yang belum dikunjungi dan menganalisisnya.

Setelah dikunjungi, semua node ditandai. Iterasi ini berlanjut hingga semua simpul pada graph berhasil dikunjungi dan ditandai.

Perbedaan DFS dan BFS

Kedua algoritma baik DFS maupun BFS bekerja dengan melapiskan tree di atas sebuah graph, yang biasa kita sebut sebagai pohon pencarian (search tree).

DFS dan BFS menetapkan simpul akar pada simpul pertama kemudian menambahkan suksesor leaf node atau simpul anak dari simpul saat ini.

Dengan cara tersebut, DFS dan BFS menelusuri seluruh graph hingga menemukan simpul tujuan atau hingga simpul graph berakhir.

Perbedaan kedua algoritma ini terletak pada urutan atau cara algoritma dalam mengunjungi sebuah node atau simpul dan menambahkannya ke pohon pencarian.

Di setiap iterasi, algoritma DFS menambahkan sebuah simpul anak dari simpul yang dikunjungi saat ini dengan sekurang-kurangnya tidak menyertakan satu simpul anak.

Jadi, DFS menambahkan simpul awal, lalu anaknya, lalu cucunya, dan seterusnya. Oleh karena itu, DFS meningkatkan kedalaman pohon pencarian di setiap langkah sebanyak mungkin.

Kemudian, jika tidak ada lagi anak dari sebuah simpul untuk ditambahkan, ia akan kembali ke induk simpul tersebut.

Sebaliknya, BFS menumbuhkan pohon pencarian secara lapis demi lapis. Pertama-tama, BFS menambahkan semua anak node awal, sehingga menyelesaikan level 1.

Kemudian, menambahkan semua anak dari semua leaf node di level pertama satu per satu. Setelah itu, ia menambahkan semua anak dari cucu simpul awal, dan seterusnya.

Jadi, jika faktor percabangan konstan di semua level, BFS membuat pohon lebih lebar di setiap langkah.

Untuk melakukannya, BFS melakukan kebalikan dari DFS, yakni menambahkan anak dari simpul yang paling baru ditambahkan yang memiliki setidaknya satu anak yang tidak disertakan ke dalam pohon pencarian.

Untuk memudahkan, berikut adalah beberapa poin perbedaan rinci antara algoritma DFS dan algoritma BFS.

1. Struktur data

Algoritma DFS menggunakan struktur data stack untuk menyimpan catatan lokasi simpul yang hendak dikunjungi, sedangkan algoritma BFS menggunakan struktur data queue.

2. Efektivitas

Algoritma DFS bekerja lebih baik apabila target atau node tujuan berada jauh dari node sumbernya. Sebaliknya BFS lebih efektif apabila lebih dekat ke simpul sumber.

3. Penggunaan memori

Apabila dibandingkan dalam hal penggunaan memori, algoritma DFS membutuhkan lebih sedikit dibandingkan dengan algoritma DFS untuk menyimpan semua catatan simpul yang sudah maupun akan dikunjungi

4. Backtracking

Backtracking adalah proses mundur ke simpul sebelumnya apabila pohon pencarian menemui jalan buntu atau mencapai leaf node paling dalam. Dalam hal ini DFS menggunakan backtracking untuk mencapai simpul induk, sedangkan BFS tidak.

5. Kecepatan

Dalam hal kecepatan penelusuran simpul tujuan, algoritma DFS lebih unggul dan cepat dibandingkan algoritma BFS. Kekurangannya adalah DFS dapat terjebak dalam infinite loop atau terus melakukan penelusuran tanpa henti.

Penutup

Demikianlah penjelasan lengkap mengenai perbedaan algoritma Depth-first search (DFS) dan algoritma Breadth-first search (BFS). Semoga informasi yang disajikan dapat bermanfaat dan menambah khazanah pengetahuan kita.

Apabila Anda suka dengan artikel seperti ini, jangan lupa kunjungi rubrik Data Structure atau membaca artikel lainnya mengenai Perbedaan Informed Search dan Uninformed Search

Salam!

Referensi:

Trivusi