Kelemahan Algoritma Pencarian Depth First Search

LancangKuning.com - Algoritma Depth First Search (DFS)  merupakan algoritma yang dijadikan sebagai pencarian jalur dengan cara melebarkan anak akar yang terletak pada urutan pertama dari pohon pencarian (search tree) sehingga menemukan tujuan. Algoritma Depth First Search memiliki persamaan dengan Algoritma BFS, keduanya melaksanakan perhitungan secara terurut.

Algoritma Depth First Search kebalikannya atau melaksanakan penghitungan secara terurut dari urutan paling ujung mundur ke urutan pertama. DFS ialah sebuah algoritma pencarian yang berjalan dalam dan lebih dalam lagi sehingga ditemukannya tujuan, setelah itu pencarian Backtracking kembali ke titik simpul yang belum juga ditelusuri.

Algoritma Depth First Search lebih mengunjungi langsung simpul atau titik yang belum ditemukan, sehingga pohon pencarian pada DFS memiliki hasil transversal yang lebih dalam daripada BFS yang memiliki hasil transversal yang seimbang. Algoritma Depth First Search memiliki tiga lintasan Hamiltonia, yang terletak pada satu di setiap komponen, sedangkan pohon pada Algoritma Breadth First Search memiliki simpul tiga derajat yang mencerminkan keseimbangan.

Baca juga : Tempat Wisata di Pekanbaru

Penjelasan gambar diatas tentang Algoritma Depth First Search, setiap titik simpul yang pertama bersebelahan dengan titik simpul akar sampai dengan tingkat yang terdalam pada pendahulunya, dan dilanjutkan mencapai seluruh titik simpul pada sub pohon tersebut yang berdekatan dengan akar.

Terdapat dua kelemahan pada Algoritma Depth First Search yaitu :

1. Pohon yang ditegakkan memiliki level yang tak terkira, maka tidak ada kesempatan untuk menemukan solusi atau tujuan yang diinginkan. Tetapi, ini bisa dijadikan sebagai pencari waktu tempuh yang singkat atau penyelesaian yang efektif dari sebuah persoalan.
2. Jika ada beberapa solusi yang sama tetapi terletak pada solusi yang berbeda, maka tidak ada kesempatan untuk menemukan solusi yang baik atau pun hanya menemukan satu jalan keluar dari setiap pencariannya. Sehingga kekurangan Algoritma Depth First Search ini memungkinkan tidak akan ada ditemukannya tujuan yang diinginkan.

Baca juga : Teori Probabilitas

Berdasarkan Transversal Algoritma DFS dapa menggunakan cara suatu graf G menelusuri semua titik simpul dan sisi dari graf G, dan memperhitungkan atau mempermasalahkan komponen yang terhubung dari G. DFS pada graf memiliki symbol, n memiliki arti simpul dan m memiliki arti sisi yang membutuhkan waktu (n + m).

Algoritma DFS dapat digunakan sebagai cara pemecah masalah pada graf, menemukan dan melaporkan lintasan antara dua buah titik simpul yang berdekatan, serta menemukan sirkuit yang terletak pada graf dan digunakan sebagai penggambaran graf euler pada pohon biner.

Langkah-langkah transversal graf menggunakan Algoritma DFS

1. Kunjungi seluruh simpul akar pada sebuah graf.
2. Jadikan simpul ini sebagai akar agar bisa melakukan Depth First Search pada langkah pertama.
3. Jika tidak ada titik simpul tetangga yang belum ditelusuri, lakukan urutan balik ke titik simpul yang pernah ditelusuri sebelumnya.
4. Pada Algoritma Depth First Search penelusuran berhenti ketika titik simpul pertama dari Depth First Search tidak mempunyai tetangga yang belum ditelusuri.

Algoritma pencarian memiliki implementasi yang saling berhubungan, algoritma Depth First Search ini secara langsung menggunakan rekursif dalam implementasiannya, salah satu contohnya digunakan dalam berbagai aplikasi yaitu menemukan solusi dari Maze.

Baca juga : Tempat Wisata di Riau

Berdasarkan penjelasan diatas, algoritma Depth First Search memiliki kelemahan tergantung pada masalah graf yang akan di pecahkan. Sedangkan pada pengimplementasian non rekursif seluruh titik simpul yang diluaskan akan dimasukkan ke LIFO dijadikan sebagai penelusuran.

Pengaplikasian algoritma Depth First Search memiliki penelusuran graf yang lebih rumit dan kegunaan dalam permasalahan kehidupan sehari-hari, seperti pembuatan Layout gambar Web yang memanfaatkan graf berarah dan sisi yang berhubungan, gambar satelit yang menggunakan lintasan terpendek yang sangat penting pada proses penggambaran satelit tersebut, dan strategi klasik untuk menelusuri sebuah maze yang dilakukan dengan cara tandai setiap persimpangan, pojokan, koridor, dan jalan buntu yang ditelusuri, serta simpan lintasan untuk kembali ke pintu masuk atau titik simpul awal.(Mechy)