BFS dan DFS adalah kaedah melintasi yang digunakan dalam mencari graf. Grafik traversal adalah proses untuk melawat semua nod grafik. Grafik adalah sekumpulan Vertices 'V' dan Edges 'E' yang menyambungkan ke simpang.
Carta Perbandingan
| Asas untuk perbandingan | BFS | DFS |
|---|---|---|
| Asas | Algoritma berasaskan Vertex | Algoritma berasaskan kelebihan |
| Struktur data yang digunakan untuk menyimpan simpul | Beratur | Timbunan |
| Penggunaan ingatan | Tidak cekap | Cekap |
| Struktur pokok yang dibina | Wide dan pendek | Sempit dan panjang |
| Melangkah fesyen | Garis yang tidak pernah terdahulu dieksplorasi pada mulanya. | Verteks di sepanjang tepi diterokai pada mulanya. |
| Kesungguhan | Optimal untuk mencari jarak terpendek, tidak dalam kos. | Tidak optimum |
| Permohonan | Mengkaji graf bipartit, komponen yang disambungkan dan jalan terpendek yang hadir dalam graf. | Mengkaji graf bersambung dua sisi, graf kuat yang disambungkan, graf aciklik dan susunan topologi. |
Definisi BFS
Carian Breadth First (BFS) adalah kaedah melintasi yang digunakan dalam graf. Ia menggunakan barisan untuk menyimpan simpang yang telah dikunjungi. Dalam kaedah ini penekanan adalah pada simpul grafik, satu titik dipilih pada mulanya kemudian ia dikunjungi dan ditanda. Pahat yang bersebelahan dengan hujung yang dilawati kemudian dilawati dan disimpan dalam baris gilir secara berurutan. Begitu juga, simptom yang disimpan kemudiannya diperlakukan satu persatu, dan simpang berdekatan mereka dikunjungi. Satu node sepenuhnya diterokai sebelum melawat mana-mana nod lain dalam graf, dengan kata lain, ia melintasi node yang tidak dapat diterokai terlebih dahulu terlebih dahulu.
Contoh
Kami mempunyai graf yang mana titiknya ialah A, B, C, D, E, F, G. Memandangkan A sebagai titik permulaan. Langkah-langkah yang terlibat dalam proses adalah:
- Vertex A diperluaskan dan disimpan dalam barisan.
- Verteks B, D dan G pengganti A, diperluas dan disimpan dalam barisan sementara Vertex A dikeluarkan.
- Sekarang B di hujung depan barisan dikeluarkan bersama dengan simpan gurunya pengganti E dan F.
- Vertex D berada di hujung depan barisan dikeluarkan, dan nod yang terhubungnya F telah dikunjungi.
- Vertex G dikeluarkan dari barisan, dan ia mempunyai pengganti E yang sudah dikunjungi.
- Sekarang E dan F akan dikeluarkan dari barisan, dan penerusnya C adalah dilalui dan disimpan dalam barisan.
- Pada akhirnya C juga dialih keluar dan gilirannya kosong yang bermaksud kita telah selesai.
- Output yang dijana adalah - A, B, D, G, E, F, C.
BFS boleh berguna untuk mencari sama ada graf itu mempunyai komponen yang berkaitan atau tidak. Dan juga ia boleh digunakan untuk mengesan graf bipartit .
Graf adalah bipartite apabila simpul graf dibahagikan kepada dua set disjoint; tiada dua titik bersebelahan akan tinggal dalam set yang sama. Kaedah lain untuk memeriksa graf bipartit adalah untuk memeriksa berlakunya kitaran ganjil dalam graf. Grafik bipartit tidak boleh mengandungi kitaran ganjil.
BFS juga lebih baik untuk mencari jalan terpendek dalam graf itu boleh dilihat sebagai rangkaian.
Definisi DFS
Kaedah melintasi Keterlihatan Pertama (DFS) menggunakan timbunan untuk menyimpan simpang yang telah dikunjungi. DFS adalah kaedah berasaskan pinggir dan berfungsi dalam fesyen rekursif di mana titik-titik itu dijelajahi sepanjang jalan (tepi). Penjelajahan nod digantung sebaik sahaja satu lagi nod yang belum dijelajahi ditemukan dan nod yang belum dijelajahi terdahulu dilalui. DFS melintasi / melawat setiap puncak tepat sekali dan setiap pinggir diperiksa tepat dua kali.
Contoh
Sama seperti BFS membolehkan graf yang sama untuk melaksanakan operasi DFS, dan langkah-langkah yang terlibat adalah:
- Memandangkan A sebagai titik awal yang dieksplorasi dan disimpan dalam timbunan.
- B penerus vertikal A disimpan dalam timbunan.
- Vertex B mempunyai dua pengganti E dan F, di antara mereka mengikut abjad E diteliti terlebih dahulu dan disimpan dalam timbunan.
- Penerus vertex E, iaitu, G disimpan dalam timbunan.
- Vertex G mempunyai dua sambungan yang bersambung, dan kedua-duanya sudah dikunjungi, jadi G muncul dari timbunan.
- Begitu juga, E s juga dikeluarkan.
- Kini, puncak B berada di bahagian atas timbunan, nod lain (puncak) F dieksplorasi dan disimpan dalam timbunan.
- Vertex F mempunyai dua pengganti C dan D, di antara mereka C dilalui terlebih dahulu dan disimpan dalam timbunan.
- Vertex C hanya mempunyai satu pendahulunya yang sudah dikunjungi, jadi ia dikeluarkan dari timbunan.
- Sekarang puncak D yang disambungkan ke F dikunjungi dan disimpan dalam timbunan.
- Oleh kerana vertex D tidak mempunyai sebarang nod yang tidak dipertimbangkan, maka D dikeluarkan.
- Begitu juga, F, B dan A juga muncul.
- Output yang dihasilkan adalah - A, B, E, G, F, C, D.
Aplikasi DFS termasuk pemeriksaan dua graf bersambung, graf kuat, graf aciklik, dan topological order .
Grafik dipanggil dua tepi bersambung jika dan hanya jika ia tetap disambungkan walaupun salah satu daripada pinggirnya dikeluarkan. Aplikasi ini sangat berguna, dalam rangkaian komputer di mana kegagalan satu pautan dalam rangkaian tidak akan menjejaskan rangkaian yang tinggal, dan ia masih akan disambungkan.
Grafik yang disambungkan dengan kuat adalah graf di mana terdapat laluan yang mesti ada di antara pasangan terarah. DFS digunakan dalam graf yang diarahkan untuk mencari laluan di antara setiap sepasang pusingan yang diperintahkan. DFS mudah menyelesaikan masalah sambungan.
Perbezaan Utama Antara BFS dan DFS
- BFS adalah algoritma berasaskan verteks manakala DFS adalah algoritma berasaskan kelebihan.
- Struktur data gilir digunakan dalam BFS. Sebaliknya, DFS menggunakan tindanan atau rekursi.
- Ruang memori digunakan dengan cekap dalam DFS sementara penggunaan ruang dalam BFS tidak berkesan.
- BFS adalah algoritma optimum manakala DFS tidak optimum.
- DFS membina pokok sempit dan panjang. Sebaliknya, BFS membina pokok yang luas dan pendek.
Kesimpulannya
BFS dan DFS, kedua-dua teknik mencari grafik mempunyai masa yang sama tetapi penggunaan ruang yang berbeza, DFS mengambil ruang linear kerana kita perlu mengingati laluan tunggal dengan nod yang belum dijelajahi, manakala BFS menyimpan setiap nod dalam ingatan.
DFS menghasilkan penyelesaian yang lebih dalam dan tidak optimum, tetapi ia berfungsi dengan baik apabila penyelesaiannya padat sedangkan BFS adalah optimum yang mencari matlamat optimum pada mulanya.
