Saya memahami perbedaan antara DFS dan BFS, tetapi saya tertarik untuk mengetahui kapan lebih praktis untuk menggunakan satu di atas yang lain?

Adakah yang bisa memberikan contoh bagaimana DFS akan mengalahkan BFS dan sebaliknya?

Itu sangat tergantung pada struktur pohon pencarian dan jumlah dan lokasi solusi (alias item yang dicari).

• Jika Anda tahu solusinya tidak jauh dari akar pohon, pencarian pertama luasnya (BFS) mungkin lebih baik.

• Jika pohon sangat dalam dan solusinya jarang, pencarian pertama kedalaman (DFS) mungkin membutuhkan waktu yang sangat lama, tetapi BFS bisa lebih cepat.

• Jika pohonnya sangat lebar, BFS mungkin membutuhkan terlalu banyak memori, jadi itu mungkin sama sekali tidak praktis.

• Jika solusi sering tetapi terletak jauh di dalam pohon, BFS mungkin tidak praktis.

• Jika pohon pencarian sangat dalam, Anda harus membatasi kedalaman pencarian untuk pencarian pertama (DFS), bagaimanapun (misalnya dengan pendalaman berulang).

Tapi ini hanya aturan praktis; Anda mungkin perlu bereksperimen.

Pencarian Kedalaman-pertama

Pencarian mendalam-pertama sering digunakan dalam simulasi game (dan situasi seperti game di dunia nyata). Dalam gim biasa Anda dapat memilih salah satu dari beberapa tindakan yang mungkin. Setiap pilihan mengarah ke pilihan lebih lanjut, masing-masing mengarah ke pilihan lebih lanjut, dan seterusnya ke dalam grafik kemungkinan berbentuk pohon yang terus berkembang.

Misalnya dalam permainan seperti Catur, tic-tac-toe ketika Anda memutuskan langkah apa yang harus dilakukan, Anda bisa membayangkan secara mental bergerak, kemudian kemungkinan respons lawan, lalu respons Anda, dan sebagainya. Anda dapat memutuskan apa yang harus dilakukan dengan melihat langkah mana yang mengarah ke hasil terbaik.

Hanya beberapa jalur dalam pohon permainan yang mengarah ke kemenangan Anda. Beberapa mengarah ke kemenangan oleh lawan Anda, ketika Anda mencapai akhir seperti itu, Anda harus membuat cadangan, atau mundur, ke simpul sebelumnya dan mencoba jalur yang berbeda. Dengan cara ini Anda menjelajahi pohon sampai Anda menemukan jalan dengan kesimpulan yang sukses. Kemudian Anda membuat langkah pertama di sepanjang jalan ini.

Pencarian luas pertama

Pencarian luas pertama memiliki properti yang menarik: Pertama-tama menemukan semua simpul yang satu ujung dari titik awal, lalu semua simpul yang berjarak dua tepi, dan seterusnya. Ini berguna jika Anda mencoba menemukan jalur terpendek dari titik awal ke titik tertentu. Anda memulai BFS, dan ketika Anda menemukan titik yang ditentukan, Anda tahu jalan yang telah Anda lacak sejauh ini adalah jalur terpendek ke titik tersebut. Jika ada jalur yang lebih pendek, BFS pasti sudah menemukannya.

Pencarian Breadth-first dapat digunakan untuk menemukan node tetangga di jaringan peer to peer seperti BitTorrent, sistem GPS untuk menemukan lokasi terdekat, situs jejaring sosial untuk menemukan orang dalam jarak yang ditentukan dan hal-hal seperti itu.

Penjelasan Bagus dari http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Contoh BFS

Berikut adalah contoh dari apa yang akan terlihat seperti BFS. Ini adalah sesuatu seperti Level Order Tree Traversal di mana kita akan menggunakan QUEUE dengan pendekatan ITERATIVE (Kebanyakan RECURSION akan berakhir dengan DFS). Angka-angka menunjukkan urutan akses node dalam BFS:

Dalam pencarian pertama yang mendalam, Anda mulai di root, dan ikuti salah satu cabang pohon sejauh mungkin sampai simpul yang Anda cari ditemukan atau Anda menekan simpul daun (simpul tanpa anak). Jika Anda menekan simpul daun, maka Anda melanjutkan pencarian di leluhur terdekat dengan anak-anak yang belum dijelajahi.

Contoh DFS

Berikut adalah contoh dari apa DFS akan terlihat. Saya pikir traversal post order di pohon biner akan mulai bekerja dari tingkat Leaf terlebih dahulu. Angka-angka menunjukkan urutan akses node dalam DFS:

Perbedaan antara DFS dan BFS

Membandingkan BFS dan DFS, keuntungan besar DFS adalah memiliki persyaratan memori yang jauh lebih rendah daripada BFS, karena tidak perlu menyimpan semua pointer anak di setiap level. Bergantung pada data dan apa yang Anda cari, DFS atau BFS dapat menguntungkan.

Misalnya, diberi pohon keluarga jika seseorang mencari seseorang di pohon yang masih hidup, maka akan aman untuk mengasumsikan bahwa orang itu akan berada di bawah pohon. Ini berarti bahwa BFS akan membutuhkan waktu yang sangat lama untuk mencapai level terakhir. Namun, DFS akan menemukan tujuannya lebih cepat. Tapi, jika seseorang mencari anggota keluarga yang sudah lama meninggal, maka orang itu akan lebih dekat ke puncak pohon. Kemudian, BFS biasanya akan lebih cepat daripada DFS. Jadi, keuntungan dari keduanya bervariasi tergantung pada data dan apa yang Anda cari.

Satu lagi contoh adalah Facebook; Saran pada Teman Teman. Kami membutuhkan teman dekat untuk saran di mana kami dapat menggunakan BFS. Mungkin menemukan jalur terpendek atau mendeteksi siklus (menggunakan rekursi) kita bisa menggunakan DFS.

Breadth First Search umumnya merupakan pendekatan terbaik ketika kedalaman pohon dapat bervariasi, dan Anda hanya perlu mencari bagian dari pohon untuk mencari solusinya. Misalnya, menemukan jalur terpendek dari nilai awal ke nilai akhir adalah tempat yang baik untuk menggunakan BFS.

Pencarian Pertama Kedalaman biasanya digunakan ketika Anda perlu mencari seluruh pohon. Lebih mudah untuk mengimplementasikan (menggunakan rekursi) daripada BFS, dan membutuhkan lebih sedikit status: Sementara BFS mengharuskan Anda menyimpan seluruh 'perbatasan', DFS hanya mengharuskan Anda menyimpan daftar node induk dari elemen saat ini.

DFS lebih hemat ruang daripada BFS, tetapi bisa mencapai kedalaman yang tidak perlu.

Nama-nama mereka mengungkapkan: jika ada keluasan yang besar (yaitu faktor percabangan besar), tetapi kedalamannya sangat terbatas (mis. Jumlah "gerakan" yang terbatas), maka DFS bisa lebih disukai daripada BFS.

Di IDDFS

Harus disebutkan bahwa ada varian yang kurang dikenal yang menggabungkan efisiensi ruang DFS, tetapi (secara kumulatif) kunjungan tingkat-tingkat BFS, adalah pencarian mendalam-pencarian mendalam-pertama yang berulang . Algoritma ini meninjau kembali beberapa node, tetapi hanya berkontribusi faktor konstan dari perbedaan asimptotik.

Ketika Anda mendekati pertanyaan ini sebagai seorang programmer, satu faktor menonjol: jika Anda menggunakan rekursi, maka pencarian mendalam-pertama lebih mudah untuk diterapkan, karena Anda tidak perlu mempertahankan struktur data tambahan yang mengandung node yang belum dijelajahi.

Inilah pencarian mendalam-pertama untuk grafik yang tidak berorientasi jika Anda menyimpan informasi "sudah dikunjungi" di node:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

Jika menyimpan informasi "sudah dikunjungi" dalam struktur data terpisah:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

Bandingkan ini dengan pencarian pertama yang luas di mana Anda perlu mempertahankan struktur data terpisah untuk daftar node yang belum dikunjungi, apa pun yang terjadi.

Salah satu keuntungan penting BFS adalah dapat digunakan untuk menemukan jalur terpendek antara dua node dalam grafik tanpa bobot. Padahal, kita tidak bisa menggunakan DFS untuk hal yang sama .

Untuk BFS, kita dapat mempertimbangkan contoh Facebook. Kami menerima saran untuk menambahkan teman dari profil FB dari profil teman lainnya. Misalkan A-> B, sedangkan B-> E dan B-> F, jadi A akan mendapatkan saran untuk E Dan F. Mereka harus menggunakan BFS untuk membaca hingga tingkat kedua. DFS lebih didasarkan pada skenario di mana kami ingin meramalkan sesuatu berdasarkan data yang kami miliki dari sumber ke tujuan. Seperti yang sudah disebutkan tentang catur atau sudoku. Sekali hal yang saya miliki berbeda di sini adalah, saya percaya DFS harus digunakan untuk jalur terpendek karena DFS akan mencakup seluruh jalur terlebih dahulu maka kita dapat memutuskan yang terbaik. Tetapi karena BFS akan menggunakan pendekatan greedy, maka itu mungkin terlihat seperti jalur terpendek, tetapi hasil akhirnya mungkin berbeda. Beri tahu saya apakah pemahaman saya salah.

Beberapa algoritma bergantung pada properti DFS (atau BFS) tertentu untuk berfungsi. Sebagai contoh algoritma Hopcroft dan Tarjan untuk menemukan komponen yang terhubung 2 mengambil keuntungan dari fakta bahwa setiap node yang sudah dikunjungi ditemui oleh DFS berada di jalur dari root ke node yang saat ini dieksplorasi.

Berikut ini adalah jawaban komprehensif untuk apa yang Anda tanyakan.

Secara sederhana:

Algoritma Breadth First Search (BFS), dari namanya "Breadth", menemukan semua tetangga dari sebuah node melalui tepi luar dari node kemudian menemukan tetangga yang belum dikunjungi dari tetangga yang disebutkan sebelumnya melalui tepi luar mereka dan seterusnya, sampai semua node yang dapat dijangkau dari sumber asli dikunjungi (kita dapat melanjutkan dan mengambil sumber asli lain jika masih ada simpul yang belum dikunjungi dan sebagainya). Itu sebabnya dapat digunakan untuk menemukan jalur terpendek (jika ada) dari sebuah simpul (sumber asli) ke simpul lain jika bobot tepinya seragam.

Algoritma Depth First Search (DFS), dari namanya "Depth", menemukan tetangga yang belum dikunjungi dari simpul x yang baru ditemukan melalui tepi-tepinya. Jika tidak ada tetangga yang belum dikunjungi dari simpul x, algoritma backtracks untuk menemukan tetangga yang belum dikunjungi dari simpul (melalui tepi luarnya) dari mana simpul x ditemukan, dan seterusnya, hingga semua node yang dapat dijangkau dari sumber asli dikunjungi. (kita dapat melanjutkan dan mengambil sumber asli lain jika masih ada simpul yang belum dikunjungi dan sebagainya).

Baik BFS dan DFS bisa tidak lengkap. Misalnya jika faktor percabangan sebuah node tidak terbatas, atau sangat besar untuk mendukung sumber daya (memori) (misalnya ketika menyimpan node yang akan ditemukan berikutnya), maka BFS tidak lengkap meskipun kunci yang dicari dapat berada pada jarak tertentu. beberapa tepi dari sumber aslinya. Faktor percabangan tak terbatas ini bisa karena pilihan tak terbatas (node ​​tetangga) dari node yang diberikan untuk ditemukan. Jika kedalamannya tidak terbatas, atau sangat besar untuk mendukung sumber daya (memori) (misalnya ketika menyimpan node yang akan ditemukan berikutnya), maka DFS tidak lengkap meskipun kunci yang dicari dapat menjadi tetangga ketiga dari sumber asli. Kedalaman tak terbatas ini bisa karena situasi di mana ada, untuk setiap node algoritma menemukan, setidaknya pilihan baru (node ​​tetangga) yang belum dikunjungi sebelumnya.

Oleh karena itu, kita dapat menyimpulkan kapan harus menggunakan BFS dan DFS. Misalkan kita berurusan dengan faktor percabangan terbatas yang dapat dikelola dan kedalaman terbatas yang dapat dikelola. Jika node yang dicari adalah dangkal yaitu dapat dijangkau setelah beberapa tepi dari sumber asli, maka lebih baik menggunakan BFS. Di sisi lain, jika node yang dicari dalam yaitu mencapai setelah banyak tepi dari sumber asli, maka lebih baik menggunakan DFS.

Misalnya, dalam jejaring sosial jika kita ingin mencari orang yang memiliki minat yang sama dari orang tertentu, kita dapat menerapkan BFS dari orang ini sebagai sumber asli, karena sebagian besar orang-orang ini akan menjadi teman langsung atau teman teman yaitu satu atau dua ujungnya jauh. Di sisi lain, jika kita ingin mencari orang yang memiliki ketertarikan yang sama sekali berbeda dari orang tertentu, kita dapat menerapkan DFS dari orang ini sebagai sumber asli, karena sebagian besar orang-orang ini akan sangat jauh darinya yaitu teman teman teman .... yaitu terlalu banyak ujungnya.

Aplikasi BFS dan DFS dapat bervariasi juga karena mekanisme pencarian di masing-masing. Sebagai contoh, kita dapat menggunakan BFS (dengan asumsi faktor branching dapat dikelola) atau DFS (dengan asumsi kedalaman dapat dikelola) ketika kita hanya ingin memeriksa jangkauan dari satu node ke node lain yang tidak memiliki informasi di mana node tersebut berada. Keduanya juga dapat menyelesaikan tugas yang sama seperti pengurutan topologi grafik (jika ada). BFS dapat digunakan untuk menemukan jalur terpendek, dengan satuan berat tepi, dari node (sumber asli) ke yang lain. Sedangkan, DFS dapat digunakan untuk menguras semua pilihan karena sifatnya yang mendalam, seperti menemukan jalur terpanjang antara dua node dalam grafik asiklik. Juga DFS, dapat digunakan untuk deteksi siklus dalam grafik.

Pada akhirnya jika kita memiliki kedalaman yang tak terbatas dan faktor percabangan yang tak terbatas, kita dapat menggunakan Iterative Deepening Search (IDS).

Menurut sifat-sifat DFS dan BFS. Misalnya, ketika kita ingin mencari jalur terpendek. kami biasanya menggunakan bfs, itu bisa menjamin 'terpendek'. tapi dfs hanya bisa menjamin bahwa kita bisa datang dari titik ini bisa mencapai titik itu, tidak bisa menjamin yang 'terpendek'.

Saya pikir itu tergantung pada masalah apa yang Anda hadapi.

1. jalur terpendek pada grafik sederhana -> bfs
2. semua hasil yang mungkin -> dfs
3. cari di grafik (perlakukan tree, martix sebagai grafik juga) -> dfs ....

Karena Pencarian Kedalaman-Pertama menggunakan tumpukan ketika node diproses, backtracking disediakan dengan DFS. Karena Pencarian Breadth-First menggunakan antrian, bukan tumpukan, untuk melacak apa yang diproses node, backtracking tidak disediakan dengan BFS.

Ketika lebar pohon sangat besar dan kedalaman rendah gunakan DFS karena tumpukan rekursi tidak akan meluap. Gunakan BFS ketika lebar rendah dan kedalaman sangat besar untuk melintasi pohon.

Ini adalah contoh yang baik untuk menunjukkan bahwa BFS lebih baik daripada DFS dalam kasus tertentu. https://leetcode.com/problems/01-matrix/

Ketika diterapkan dengan benar, kedua solusi harus mengunjungi sel yang memiliki jarak lebih jauh dari sel saat ini +1. Tetapi DFS tidak efisien dan berulang kali mengunjungi sel yang sama menghasilkan O (n * n) kompleksitas.

Sebagai contoh,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

Itu tergantung pada situasi yang digunakan. Setiap kali kita memiliki masalah melintasi grafik, kita melakukannya untuk beberapa tujuan. Ketika ada masalah menemukan jalur terpendek dalam grafik tidak tertimbang, atau menemukan jika grafik adalah bipartit, kita bisa menggunakan BFS. Untuk masalah deteksi siklus atau logika apa pun yang memerlukan penelusuran ulang, kita dapat menggunakan DFS.