Depth-First Search (DFS)

Pencarian 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).

Kelebihan DFS adalah:
• Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus
menyimpan semua node yang pernah dibangkitkan.
• Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS
akan menemukannya secara cepat.

Kelemahan DFS adalah:
• Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka
tidak ada jaminan untuk menemukan solusi (Tidak Complete).
• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang
berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling
baik (Tidak Optimal).