Pengertian Metode Depth First Search

LancangKuning - Terdapat salah satu sebuah metode pencarian yang biasa sering digunakan dalam sebuah struktur data adalah metode Depth-First Search. Pada sebuah struktur data, terdapat sebuah node. Maksud dari node itu adalah sebuah unit yang paling mendasar yang ada dalam sebuah struktur data. Node itu biasanya terdapat 2 bagian, yaitu seperti sebuah data dan sebuah link yang dapat mengarahkan ke node yang lainnya. Node yang saling berhubungan itu kemudian akan membentuk sebuah grafik atau yang biasa dikenal sebagai pohon data.

Maksud dari Depth-First Search atau yang disingkat menjadi DFS ini adalah sebuah metode untuk menjelajahi pohon data atau grafik. Dalam metode Depth-First Search ini, pencarian itu masuk sedalam mungkin dengan melalui satu jalur saja yang kemudian kembali dan akan mencoba masuk ke jalur lain yang ada. Metode DFS ini berjalan melalui labirin yang selalu menggunakan jagung sebagai sebuah penanda jalan untuk kembali.

Depth First Traversal (atau Search) untuk grafik mirip dengan Depth First Traversal dari sebuah pohon. Satu-satunya tangkapan di sini adalah, tidak seperti pohon, grafik mungkin berisi siklus, node dapat dikunjungi dua kali. Untuk menghindari pemrosesan node lebih dari sekali, gunakan array yang dikunjungi boolean.

Prasyarat: Lihat posting ini untuk semua aplikasi Depth First Traversal. Berikut adalah implementasi sederhana Depth First Traversal. Penerapan C ++ menggunakan representasi daftar kedekatan grafik. Penampung daftar STL digunakan untuk menyimpan daftar node yang berdekatan.

Solusi :

Pendekatan: Pencarian kedalaman-pertama adalah algoritma untuk melintasi atau mencari struktur data pohon atau grafik. Algoritme dimulai pada node root (memilih beberapa node arbitrer sebagai node root dalam kasus grafik) dan mengeksplorasi sejauh mungkin di setiap cabang sebelum melakukan backtracking. Jadi ide dasarnya adalah memulai dari root atau sembarang node dan menandai node tersebut dan pindah ke node yang berdekatan yang tidak ditandai dan melanjutkan loop ini sampai tidak ada node yang berdekatan yang tidak ditandai. Kemudian lacak kembali dan periksa node lain yang tidak ditandai dan lintasi. Terakhir, cetak node di jalur tersebut.

Algoritma:

1. Buat fungsi rekursif yang mengambil indeks node dan array yang dikunjungi.
2. Tandai node saat ini sebagai telah dikunjungi dan cetak node tersebut.
3. Lintasi semua node yang berdekatan dan tidak ditandai dan panggil fungsi rekursif dengan indeks node yang berdekatan.

Pencarian kedalaman pertama digunakan dalam pengurutan topologi, masalah penjadwalan, deteksi siklus dalam grafik, dan memecahkan teka-teki hanya dengan satu solusi, seperti labirin atau teka-teki sudoku. Aplikasi lain melibatkan analisis jaringan, misalnya, menguji apakah suatu grafik adalah bipartit. Jadi, backtracking adalah DFS untuk pohon implisit, sedangkan DFS melakukan backtracking tanpa pemangkasan. Backtracking biasanya diimplementasikan sebagai DFS plus pemangkasan pencarian. Anda melintasi pencarian solusi parsial pohon ruang angkasa yang pertama membangun di sepanjang jalan.

Algoritma DFS adalah algoritma rekursif yang menggunakan ide backtracking. Ini melibatkan pencarian menyeluruh dari semua node dengan melanjutkan, jika memungkinkan, dengan mundur. Di sini, kata mundur berarti bahwa ketika Anda bergerak maju dan tidak ada lagi node di sepanjang jalur saat ini, Anda bergerak mundur di jalur yang sama untuk menemukan node yang akan dilintasi. Semua node akan dikunjungi di jalur saat ini sampai semua node yang belum dikunjungi telah dilintasi, setelah itu jalur berikutnya akan dipilih.

Disini kita menjelajah satu arah saja lebih awal, mencapai jalan buntu dan kembali dan sekaligus bisa mencoba sesuatu yang lain. Algoritma itu akan mencoba melakukan sampai ke seluruh grafik yang telak dieksplorasi. Banyak masalah yang ada di dalam ilmu komputer yang dapat digambarkan dengan sebuah grafik.(Yazid)