Perbedaan Antara BFS dan DFS

BFS vs DFS

Breadth First Search (juga dikenal sebagai BFS) adalah metode pencarian yang digunakan untuk memperluas semua node grafik tertentu. Ini menyelesaikan tugas ini dengan mencari setiap solusi tunggal untuk memeriksa dan memperluas node ini (atau kombinasi dari sekuens di dalamnya). Dengan demikian, BFS tidak menggunakan algoritma heuristik (atau algoritma yang mencari solusi melalui beberapa skenario). Setelah semua node diperoleh, mereka ditambahkan ke antrian yang dikenal sebagai antrian First In, First Out. Simpul-simpul yang belum dieksplorasi 'disimpan' dalam wadah bertanda 'terbuka'; setelah dieksplorasi mereka diangkut ke sebuah wadah bertanda 'tertutup'.

Pencarian Kedalaman Pertama (juga dikenal sebagai DFS) adalah metode pencarian yang menggali lebih dalam ke simpul anak dari pencarian sampai tujuan tercapai (atau sampai ada simpul tanpa permutasi lain atau 'anak-anak'). Setelah satu tujuan ditemukan, pencarian mundur ke simpul sebelumnya yang telah pergi dengan solusi, mengulangi proses sampai semua node berhasil dicari. Dengan demikian, node terus dikesampingkan untuk eksplorasi lebih lanjut - ini disebut implementasi non-rekursif.

Fitur-fitur BFS adalah kompleksitas ruang dan waktu, kelengkapan, bukti kelengkapan, dan optimalitas. Kompleksitas ruang mengacu pada proporsi jumlah node pada tingkat pencarian terdalam. Kompleksitas waktu mengacu pada jumlah aktual 'waktu' yang digunakan untuk mempertimbangkan setiap jalur yang akan diambil oleh sebuah simpul dalam pencarian. Kelengkapan adalah, pada dasarnya, pencarian yang menemukan solusi dalam grafik terlepas dari apa jenis grafiknya. Bukti kelengkapan adalah tingkat paling dangkal di mana tujuan ditemukan dalam sebuah simpul pada kedalaman tertentu. Akhirnya, optimalitas mengacu pada BFS yang tidak berbobot - yaitu grafik yang digunakan untuk biaya unit-step.

DFS adalah output paling alami menggunakan spanning tree - yang merupakan pohon yang terdiri dari semua simpul dan beberapa sisi dalam grafik yang tidak diarahkan. Dalam formasi ini, grafik dibagi menjadi tiga kelas: Tepi ke depan, menunjuk dari sebuah simpul ke simpul anak; tepi belakang, menunjuk dari simpul ke simpul sebelumnya; dan lintas sisi, yang tidak melakukan salah satu dari ini.

Ringkasan:

1. BFS mencari setiap solusi tunggal dalam grafik untuk memperluas node-nya; DFS bersembunyi jauh di dalam simpul anak sampai tujuan tercapai.

2. Fitur BFS adalah kompleksitas ruang dan waktu, kelengkapan, bukti kelengkapan, dan optimalitas; output paling alami untuk DFS adalah spanning tree dengan tiga kelas: tepi depan, tepi belakang, dan tepi silang.