Apa itu BFS?
BFS adalah algoritma yang digunakan untuk membuat grafik data atau mencari struktur pokok atau melintasi. Algoritma dengan cekap mengunjungi dan menandai semua nod utama dalam grafik dengan cara tepat.
Algoritma ini memilih simpul tunggal (titik awal atau sumber) dalam grafik dan kemudian melawat semua nod yang berdekatan dengan nod yang dipilih. Setelah algoritma melawat dan menandakan nod permulaan, maka ia bergerak ke arah nod yang tidak dilawati terdekat dan menganalisisnya.
Setelah dikunjungi, semua nod ditandakan. Iterasi ini berterusan sehingga semua nod grafik berjaya dilayari dan ditandai. Bentuk lengkap BFS adalah carian pertama-lebar.
Dalam BSF ini Vs. Tutorial pokok DFS Binary, anda akan belajar:
- Apa itu BFS?
- Apa itu DFS?
- Contoh BFS
- Contoh DFS
- Perbezaan antara BFS dan DFS Binary Tree
- Aplikasi BFS
- Aplikasi DFS
Apa itu DFS?
DFS adalah algoritma untuk mencari atau melintasi grafik atau pokok ke arah kedalaman. Pelaksanaan algoritma bermula pada simpul akar dan meneroka setiap cabang sebelum mundur. Ia menggunakan struktur data timbunan untuk mengingat, mendapatkan titik berikutnya, dan untuk memulakan pencarian, setiap kali jalan buntu muncul dalam setiap lelaran. Bentuk lengkap DFS adalah carian pertama Kedalaman.
Contoh BFS
Dalam contoh DFS berikut, kami telah menggunakan graf yang mempunyai 6 bucu.
Contoh BFS
Langkah 1)
Anda mempunyai graf tujuh nombor antara 0 - 6.
Langkah 2)
0 atau sifar telah ditandakan sebagai nod akar.
Langkah 3)
0 dikunjungi, ditandai, dan dimasukkan ke dalam struktur data antrian.
Langkah 4)
Sisa 0 nod bersebelahan dan tidak dilawati dikunjungi, ditandakan, dan dimasukkan ke dalam barisan.
Langkah 5)
Pengulangan melintasi diulang sehingga semua nod dikunjungi.
Contoh DFS
Dalam contoh DFS berikut, kami telah menggunakan graf tidak terarah yang mempunyai 5 bucu.
Langkah 1)
Kami telah bermula dari bucu 0. Algoritma bermula dengan memasukkannya ke dalam senarai yang dikunjungi dan sekaligus meletakkan semua bucu bersebelahan dalam struktur data yang disebut tumpukan.
Langkah 2)
Anda akan mengunjungi elemen, yang berada di bahagian atas timbunan, sebagai contoh, 1 dan pergi ke nod bersebelahan. Ini kerana 0 telah dikunjungi. Oleh itu, kami melawat bucu 2.
Langkah 3)
Vertex 2 mempunyai bucu berdekatan yang tidak dilawati pada 4. Oleh itu, kami menambahkannya di timbunan dan mengunjunginya.
Langkah 4)
Akhirnya, kita akan mengunjungi simpul 3 terakhir, ia tidak mempunyai nod bersebelahan yang tidak dikunjungi. Kami telah menyelesaikan traversal grafik menggunakan algoritma DFS.
Perbezaan antara BFS dan DFS Binary Tree
| BFS | DFS |
| BFS menemui jalan terpendek ke destinasi. | DFS menuju ke bahagian bawah subtree, kemudian mengundur. |
| Bentuk lengkap BFS adalah Breadth-First Search. | Bentuk lengkap DFS adalah Depth First Search. |
| Ia menggunakan barisan untuk menjejaki lokasi seterusnya untuk dikunjungi. | Ia menggunakan timbunan untuk melacak lokasi seterusnya untuk dikunjungi. |
| BFS melintasi mengikut tahap pokok. | DFS melintasi mengikut kedalaman pokok. |
| Ia dilaksanakan menggunakan senarai FIFO. | Ia dilaksanakan menggunakan senarai LIFO. |
| Ia memerlukan lebih banyak memori berbanding DFS. | Ia memerlukan memori yang lebih sedikit berbanding dengan BFS. |
| Algoritma ini memberikan jalan penyelesaian yang paling cetek. | Algoritma ini tidak menjamin penyelesaian jalan yang paling cetek. |
| Tidak perlu melakukan backtracking di BFS. | Terdapat keperluan mengundurkan diri di DFS. |
| Anda tidak akan terperangkap dalam gelung terhingga. | Anda boleh terperangkap dalam gelung tanpa had. |
| Sekiranya anda tidak menemui matlamat, anda mungkin perlu mengembangkan banyak nod sebelum penyelesaiannya dijumpai. | Sekiranya anda tidak menjumpai tujuan, penembakan simpul daun mungkin berlaku. |
Aplikasi BFS
Berikut adalah Aplikasi BFS:
Grafik Tidak Berat:
Algoritma BFS dapat dengan mudah membuat jalan terpendek dan pokok rentang minimum untuk mengunjungi semua bucu grafik dalam masa sesingkat mungkin dengan ketepatan tinggi.
Rangkaian P2P:
BFS dapat dilaksanakan untuk mencari semua nod terdekat atau berdekatan dalam rangkaian peer to peer. Ini akan menemui data yang diperlukan dengan lebih pantas.
Perayap Web:
Enjin carian atau perayap web dapat membina pelbagai peringkat indeks dengan mudah menggunakan BFS. Pelaksanaan BFS bermula dari sumber, yang merupakan halaman web, dan kemudian ia mengunjungi semua pautan dari sumber tersebut.
Penyiaran Rangkaian:
Satu paket yang disiarkan dipandu oleh algoritma BFS untuk mencari dan mencapai semua nod yang mempunyai alamatnya.
Aplikasi DFS
Berikut adalah aplikasi penting DFS:
Graf wajaran:
Dalam graf berwajaran, grafik trafersal DFS menghasilkan pokok laluan terpendek dan pokok rentang minimum.
Mengesan Kitaran dalam Grafik:
Grafik mempunyai kitaran jika kita menemui pinggir belakang semasa DFS. Oleh itu, kita harus menjalankan DFS untuk grafik dan mengesahkan tepi belakang.
Mencari Jalan:
Kita dapat mengkhususkan diri dalam algoritma DFS untuk mencari jalan antara dua bucu.
Penyortiran Topologi:
Ini terutama digunakan untuk menjadwalkan pekerjaan dari ketergantungan yang diberikan di antara kumpulan pekerjaan. Dalam sains komputer, ia digunakan dalam penjadualan instruksi, serialisasi data, sintesis logik, menentukan urutan tugas penyusunan.
Mencari Komponen Graf yang Sangat Terhubung:
Ia digunakan dalam grafik DFS apabila terdapat jalur dari setiap bucu dalam grafik ke bucu baki yang lain.
Menyelesaikan Teka-teki dengan Satu Penyelesaian:
Algoritma DFS dapat dengan mudah disesuaikan untuk mencari semua penyelesaian untuk labirin dengan memasukkan simpul pada jalan yang ada dalam set yang dikunjungi.
PERBEZAAN UTAMA:
- BFS mencari jalan terpendek ke destinasi sedangkan DFS menuju ke bahagian bawah subtree, kemudian mengundur.
- Bentuk lengkap BFS adalah Breadth-First Search sementara bentuk lengkap DFS adalah Depth First Search.
- BFS menggunakan barisan untuk menjejaki lokasi seterusnya untuk dikunjungi. sedangkan DFS menggunakan timbunan untuk melacak lokasi seterusnya untuk dikunjungi.
- BFS melintasi mengikut tahap pokok manakala DFS melintasi mengikut kedalaman pokok.
- BFS dilaksanakan menggunakan senarai FIFO sebaliknya DFS dilaksanakan menggunakan senarai LIFO.
- Di BFS, anda tidak pernah terperangkap dalam gelung terhingga sedangkan di DFS anda boleh terperangkap dalam gelung tak terhingga.