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).
Pseucode DFS
|
Deklarasi
w : integer
Algoritma:
write(v)
dikunjungi[v]¬true
for tiap simpul w yang bertetangga
dengan simpul v do
if not dikunjungi[w] then
DFS(w)
endif
endfor
|
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). Breadth- pencarian pertama memiliki efisiensi yang sama
dengan mendalam-pencarian pertama: itu adalah di (| V | 2) untuk representasi
adjacency matrix dan (| V | + | E |) untuk daftar adjacency representasi??.
Tidak seperti mendalam-pencarian pertama, itu menghasilkan pemesanan tunggal
simpul karena antrian adalah (pertama-in pertama-out) struktur FIFO dan
karenanya urutan simpul ditambahkan ke antrian adalah urutan yang sama di mana
mereka dikeluarkan dari saya t. Untuk struktur hutan BFS dari sebuah grafik
diarahkan, juga dapat memiliki dua jenis sehingga fedges: tepi pohon dan tepi silang edges.Tree adalah yang digunakan untuk
mencapai simpul sebelumnya yang belum dikunjungi. tepi lintas menghubungkan
simpul untuk mereka kunjungi sebelumnya, tetapi, tidak seperti tepi kembali
pohon DFS, mereka terhubung simpul baik pada tingkat yang sama atau berdekatan
pohon BFS.