Breadth-first vs Depth-first Tree Traversal di Javascript

Ketika kita mencari melalui pohon untuk menemukan apakah itu mengandung simpul tertentu, ada dua algoritma yang bisa kita bangun. Kita dapat melintasi pohon dengan pendekatan lebar-pertama atau kedalaman-pertama.

Metode kedalaman-pertama percaya akan berjalan sejauh pohon sampai mencapai jalan buntu. Setelah mencapai nilai nol, mulai kembali di atas dan mengikuti proses yang sama.

Metode pertama kali mencoba yang terbaik untuk tetap sedekat mungkin ke atas. Ini melintasi pohon satu baris pada satu waktu dan melihat semua simpul saudara. Ini berlanjut sampai mencapai baris terakhir.

Membangun kelas Node dan Pohon sederhana

Kelas Node akan memiliki konstruktor dengan dua properti. Ini akan memiliki properti data untuk menyimpan nilai simpul dan properti anak-anak untuk memegang array simpul anak. Metode add () dapat digunakan untuk menambahkan node baru ke Tree dan metode remove () akan menghapus simpul anak yang tidak diinginkan.

Saat membangun kelas Tree, kita hanya perlu properti untuk menunjuk ke simpul pertama, juga dikenal sebagai root.

Di dalam kelas Tree adalah tempat kami membangun fungsi pencarian DFS dan BFS kami untuk mencari melalui Tree of node.

Algoritma Kedalaman-Pertama

Untuk memeriksa untuk melihat pohon berisi nilai tertentu menggunakan pendekatan DFS, kita akan membuat fungsi yang dimulai dengan mendeklarasikan array koleksi, yang akan berisi simpul root. Kami kemudian akan membangun loop sementara yang akan berjalan sampai tidak ada lagi nilai di dalam array.

DFS menggunakan Stack untuk melintasi pohon node. Kami akan mendeklarasikan node saat ini dengan menggeser nilai pertama array. Dengan simpul ini, kami akan memeriksa untuk melihat apakah datanya sama dengan nilai yang kami cari. Jika sama, kita akan mengembalikan True dan keluar dari fungsi. Jika nilai simpul tidak cocok, kami akan mendorong anak-anak dari simpul itu ke depan array jika ada. Kami melepaskan anak-anak ke depan karena pendekatan DFS ingin kami pergi jauh ke bawah pohon sebelum memeriksa elemen saudara kandung. Jika tidak ada nilai yang cocok setelah mencari seluruh pohon, kami mengembalikan false pada akhir fungsi kami.

Algoritma Pertama-Luas

Setelah membangun fungsi DFS, fungsi BFS akan terlihat sangat mirip, tetapi dengan satu perbedaan kecil. Ketika kami menggunakan pendekatan BFS, kami ingin memeriksa semua elemen saudara sebelum pergi ke baris pohon berikutnya. Kami akan mencapai ini dengan menggunakan Antrian. Antrian mengharuskan kita untuk menggunakan metode push alih-alih metode unshift ketika menangani anak-anak node. Alih-alih mengambil anak-anak dari sebuah simpul dan mengatur mereka ke depan array koleksi, kami malah akan mendorong mereka sampai akhir. Ini memastikan bahwa kami akan memeriksa semua elemen saudara sebelum pergi ke baris pohon berikutnya.

Kapan menggunakan BFS vs. DFS?

Kedua algoritma dapat berguna ketika melintasi pohon untuk mencari nilai, tetapi yang mana yang lebih baik? Itu semua tergantung pada struktur pohon dan apa yang Anda cari. Jika Anda tahu nilai yang Anda cari lebih dekat ke atas, pendekatan BFS mungkin merupakan pilihan yang unggul, tetapi jika pohon sangat lebar dan tidak terlalu dalam, pendekatan DFS mungkin lebih cepat dan lebih efisien. Ingatlah bahwa ada banyak faktor lain yang perlu Anda tentukan sebelum memilih pendekatan mana yang akan diambil. Saya yakin Anda akan menemukannya!