Kecerdasan Buatan - Pertemuan 6

Algoritma DFS (Depth First Search)

LATAR BELAKANG

Pada kali ini saya akan sedikit menjelaskan tentang Algoritma DFS (Depth First Search),apa itu DFS dan contoh kasus tentang DFS,pada tulisan ini saya akan coba membahas itu.

ISI

DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.

Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.

Pencarian juga dapat dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi  ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

Contoh kasus mencari jalur/path dari A ke F

Contoh kasus kali ini akan saya coba jelaskan melalui video berikut:

PENUTUP

Kesimpulan

Jadi,DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman.Dimana penelusuran dilakukan terus menerus hingga mencapai level terdalam.

Saran

Sebaiknya memperbanyak referensi dan mencoba menyelesaikan sebuah kasus menggunakan DFS agar pemahaman lebih dalam.

Nama : Rizki Fadillah

NPM : 1144089

Kelas : 3A

Prodi : D4 Teknik Informatika

Mata Kuliah : Kecerdasan Buatan

Link Github : Rizki-1144089

Plagiarisme:

• Duplichecker
• Smallseotools

Referensi:

• Materi perkuliahan Kecerdasan Buatan Pertemuan 6
• anthonilockheart.blogspot.co.id/2013/04/depth-first-search-dfs-breath-first.html
• saungkode.wordpress.com