Perbezaan antara BFS dan DFS

BFS vs DFS

Carian pertama yang luas (juga dikenali sebagai BFS) adalah kaedah carian yang digunakan untuk meluaskan semua nod graf tertentu. Ia menyelesaikan tugas ini dengan mencari setiap penyelesaian untuk memeriksa dan mengembangkan nod ini (atau gabungan urutan di dalamnya). Oleh itu, BFS tidak menggunakan algoritma heuristik (atau algoritma yang mencari penyelesaian melalui pelbagai senario). Selepas semua nod diperoleh, mereka ditambah ke barisan yang dikenali sebagai yang pertama, pertama kali keluar. Nod yang belum diterokai adalah 'disimpan' dalam bekas yang ditandakan 'terbuka'; Setelah diterokai, mereka diangkut ke bekas yang ditandakan 'ditutup'.

Carian pertama kedalaman (juga dikenali sebagai DFS) adalah kaedah carian yang melambatkan lebih jauh ke dalam nod kanak -kanak pencarian sehingga matlamat dicapai (atau sehingga ada nod tanpa sebarang permutasi atau 'anak -anak'). Selepas satu matlamat dijumpai, backtracks carian ke nod sebelumnya yang telah pergi dengan penyelesaian, mengulangi proses sehingga semua nod telah berjaya dicari. Oleh itu, nod terus diketepikan untuk penjelajahan lanjut - ini dipanggil pelaksanaan bukan rekursif.

Ciri -ciri BFS adalah kerumitan ruang dan masa, kesempurnaan, bukti kesempurnaan, dan optimum. Kerumitan ruang merujuk kepada perkadaran bilangan nod pada tahap pencarian yang paling dalam. Kerumitan masa merujuk kepada jumlah sebenar 'masa' yang digunakan untuk mempertimbangkan setiap jalan nod akan diambil dalam carian. Kelengkapan adalah, pada dasarnya, carian yang menemui penyelesaian dalam graf tanpa mengira jenis graf itu. Bukti kesempurnaan adalah tahap paling cetek di mana matlamat dijumpai dalam nod pada kedalaman pasti. Akhirnya, optimum merujuk kepada BFS yang tidak ditimbang - iaitu graf yang digunakan untuk kos unit.

DFS adalah output yang paling semula jadi menggunakan pokok yang merangkumi - yang merupakan pokok yang terdiri daripada semua simpang dan beberapa tepi dalam graf yang tidak diarahkan. Dalam pembentukan ini, graf dibahagikan kepada tiga kelas: tepi ke hadapan, menunjuk dari nod ke nod kanak -kanak; tepi belakang, menunjuk dari nod ke nod terdahulu; dan tepi salib, yang tidak melakukan salah satu daripada ini.

Ringkasan:

1. BFS mencari setiap penyelesaian dalam graf untuk mengembangkan nodnya; DFS meledak jauh di dalam nod kanak -kanak sehingga matlamat dicapai.

2. Ciri -ciri BFS adalah ruang dan kerumitan masa, kesempurnaan, bukti kesempurnaan, dan optimum; Output yang paling semulajadi untuk DFS adalah pokok yang merangkumi dengan tiga kelas: tepi ke hadapan, tepi belakang, dan tepi silang.