Depth-First Search

Hari ini saya belajar tentang Depth First Search pada mata kuliah ai. Mata kuliah AI adalah mata kuliah semester 4 di universitas bina nusantara jakarta . Ai juga merupakan peminatan di Jurusan Teknik Informatika . Sekedar pengengenalan pada sesi pertama kuliah hari ini , kami mempelajari DFS (Depth First Search)

Pengertian Depth-First Search

Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya. Pencarian rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang dicari.

Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal).

Keuntungan Dari Algoritma Depth-First Search

• Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja.
• Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan Dari Algoritma Depth-First Search

• Memungkinkan tidak ditemukannya tujuan dari apa yang diharapkan
• Hanya menemukan satu solusi