BFS vs DFS – Perbedaan Antara Keduanya

Apa itu BFS?

BFS adalah algoritma yang digunakan untuk membuat grafik data atau menelusuri pohon atau struktur yang melintasinya. Algoritma ini secara efisien mengunjungi dan menandai semua simpul kunci dalam grafik dengan cara yang akurat.

Algoritme ini memilih satu simpul (titik awal atau titik sumber) dalam grafik, lalu mengunjungi semua simpul yang berdekatan dengan simpul yang dipilih. Setelah algoritme mengunjungi dan menandai simpul awal, ia bergerak menuju simpul terdekat yang belum dikunjungi dan menganalisisnya.

Setelah dikunjungi, semua node ditandai. Iterasi ini berlanjut hingga semua node pada grafik berhasil dikunjungi dan ditandai. Bentuk lengkap dari BFS adalah pencarian Breadth-first.

Apa itu DFS?

DFS adalah algoritma untuk menemukan atau melintasi grafik atau pohon dalam arah kedalaman. Eksekusi algoritma dimulai dari node akar dan mengeksplorasi setiap cabang sebelum melakukan backtracking. Ia menggunakan struktur data tumpukan untuk mengingat, untuk mendapatkan simpul berikutnya, dan untuk memulai pencarian, setiap kali jalan buntu muncul dalam iterasi apa pun. Bentuk lengkap DFS adalah pencarian Depth-first.

Perbedaan antara Pohon Biner BFS dan DFS

Berikut adalah perbedaan penting antara BFS dan DFS.

BFS	DFS
BFS menemukan jalur terpendek ke tujuan.	DFS pergi ke bagian bawah subpohon, lalu mundur.
Bentuk lengkap BFS adalah Breadth-First Search.	Bentuk lengkap DFS adalah Depth First Search.
Ia menggunakan antrian untuk melacak lokasi berikutnya yang akan dikunjungi.	Ia menggunakan tumpukan untuk melacak lokasi berikutnya yang akan dikunjungi.
BFS melintasi menurut tingkat pohon.	DFS melintasi menurut kedalaman pohon.
Ini diimplementasikan menggunakan daftar FIFO.	Ini diimplementasikan menggunakan daftar LIFO.
Ini membutuhkan lebih banyak memori dibandingkan dengan DFS.	Ini membutuhkan lebih sedikit memori dibandingkan dengan BFS.
Algoritma ini memberikan solusi jalur paling dangkal.	Algoritma ini tidak menjamin solusi jalur paling dangkal.
Tidak perlu mundur di BFS.	Ada kebutuhan untuk menelusuri kembali DFS.
Anda tidak akan pernah bisa terjebak dalam putaran terbatas.	Anda bisa terjebak dalam putaran tak terbatas.
Jika Anda tidak menemukan tujuan apa pun, Anda mungkin perlu memperluas banyak node sebelum solusi ditemukan.	Jika Anda tidak menemukan tujuan apa pun, kemunduran simpul daun dapat terjadi.

Contoh BFS

Dalam contoh BFS berikut, kami menggunakan grafik yang memiliki 6 titik sudut.

Contoh BFS

Langkah 1)

Anda memiliki grafik tujuh angka yang berkisar dari 0 – 6.

Langkah 2)

0 atau nol telah ditandai sebagai simpul akar.

Langkah 3)

0 dikunjungi, ditandai, dan dimasukkan ke dalam struktur data antrian.

Langkah 4)

Sisa 0 node yang berdekatan dan belum dikunjungi dikunjungi, ditandai, dan dimasukkan ke dalam antrian.

Langkah 5)

Perulangan traversing diulang sampai semua node dikunjungi.

Contoh DFS

Dalam contoh DFS berikut, kami telah menggunakan grafik tak berarah yang memiliki 5 titik sudut.

Langkah 1)

Kita mulai dari titik 0. Algoritma dimulai dengan meletakkannya di daftar yang dikunjungi dan secara bersamaan meletakkan semua titik yang berdekatan di struktur data disebut tumpukan.

Langkah 2)

Anda akan mengunjungi elemen yang berada di bagian atas tumpukan, misalnya 1 dan menuju ke node yang berdekatan. Itu karena 0 sudah dikunjungi. Oleh karena itu, kami mengunjungi simpul 2.

Langkah 3)

Simpul 2 memiliki simpul terdekat yang belum dikunjungi di 4. Oleh karena itu, kita menambahkan simpul tersebut ke dalam tumpukan dan mengunjunginya.

Langkah 4)

Terakhir, kita akan mengunjungi simpul terakhir 3, yang tidak memiliki simpul bersebelahan yang belum dikunjungi. Kami telah menyelesaikan traversal grafik menggunakan algoritma DFS.

Aplikasi BFS

Berikut Aplikasi BFS:

Grafik Tidak Berbobot

Algoritma BFS dapat dengan mudah membuat jalur terpendek dan pohon merentang minimum untuk mengunjungi semua simpul pada grafik dalam waktu sesingkat mungkin dengan akurasi tinggi.

Jaringan P2P

BFS dapat diimplementasikan untuk menemukan semua node terdekat atau bertetangga dalam jaringan peer-to-peer. Ini akan menemukan data yang dibutuhkan lebih cepat.

Perayap Web

Mesin pencari atau perayap web dapat dengan mudah membuat beberapa tingkat indeks dengan menggunakan BFS. Implementasi BFS dimulai dari sumbernya yaitu halaman web, kemudian mengunjungi semua link dari sumber tersebut.

Penyiaran Jaringan

Paket yang disiarkan dipandu oleh algoritma BFS untuk menemukan dan menjangkau semua node yang alamatnya dimilikinya.

Penerapan DFS

Berikut adalah aplikasi penting DFS:

Grafik Tertimbang

Dalam graf berbobot, traversal graf DFS menghasilkan pohon jalur terpendek dan pohon rentang minimum.

Mendeteksi Siklus dalam Grafik

Sebuah grafik memiliki siklus jika kita menemukan tepi belakang selama DFS. Oleh karena itu, kita harus menjalankan DFS untuk grafik dan memverifikasi tepi belakangnya.

Menemukan jalan

Kita dapat mengkhususkan diri pada algoritma DFS untuk mencari jalur antara dua simpul.

Penyortiran Topologi

Hal ini terutama digunakan untuk menjadwalkan pekerjaan dari ketergantungan tertentu di antara kelompok pekerjaan. Dalam ilmu komputer, digunakan dalam penjadwalan instruksi, serialisasi data, sintesis logika, menentukan urutan tugas kompilasi.

Mencari Komponen Grafik yang Terhubung Kuat

Ini digunakan dalam grafik DFS ketika ada jalur dari setiap simpul dalam grafik ke simpul lain yang tersisa.

Memecahkan Teka-Teki dengan Hanya Satu Solusi

Algoritma DFS dapat dengan mudah diadaptasi untuk mencari semua solusi labirin dengan memasukkan node pada jalur yang ada ke dalam kumpulan yang dikunjungi.