Scribd
Unggah
42 tayangan1 halaman

Algoritma Depth First Search (DFS)

DFS adalah metode pencarian pada pohon dengan menelusuri satu cabang sampai ujung. Pencarian dilakukan secara rekursif pada simpul terkiri setiap level. Algoritma DFS menandai simpul yang dikunjungi dan meneruskan pencarian pada simpul adjacent belum dikunjungi secara berulang hingga semua simpul terkunjungi.

Diunggah oleh

Maharani Inas
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd
42 tayangan1 halaman

Algoritma Depth First Search (DFS)

DFS adalah metode pencarian pada pohon dengan menelusuri satu cabang sampai ujung. Pencarian dilakukan secara rekursif pada simpul terkiri setiap level. Algoritma DFS menandai simpul yang dikunjungi dan meneruskan pencarian pada simpul adjacent belum dikunjungi secara berulang hingga semua simpul terkunjungi.

Diunggah oleh

Maharani Inas
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd

MAHARANI INAS

Depth First Search (DFS)

Dengan menggambarkan proses di dalam stack-nya, algoritma Depth First Search (DFS)
adalah suatu metode pencarian pada sebuah pohon dengan menelusuri satu cabang sebuah pohon
sampai menemukan solusi. Pencarian dilakukan pada satu simpul dalam setiap level dari yang
paling kiri dan dilanjutkan pada simpul sebelah kanan. Jika solusi ditemukan maka tidak
diperlukan proses backtracking, yaitu penelusuran balik untuk mendapatkan jalur yang
diinginkan. Pada metode DFS pemakaian memori tidak banyak karena hanya simpul-simpul
pada lintasan yang aktif saja yang disimpan. Selain itu, jika solusi yang dicari berada pada level
yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Dalam metode pencarian baik yang BFS maupun DFS memiliki algoritma yang berbeda.
Pada algoritma DFS adalah algoritma yang melakukan penelusuran dengan mengunjungi secara
rekursif. Misalkan G = <N, A> adalah suatu graph tak berarah, maka untuk mengunjungi semua
simpul dapat dilakukan dengan menerapkan teknik DFS sebagai berikut.

a) Transversal dimulai dari simpul ! ∈ # sebagai node awal (starting point),


b) Tandai v sebagai sebagai tanda telah dikunjungi,
c) Bila terdapat node $ yang adjacent dengan v yang belum dikunjungi, pilih simpul w
tersebut
d) sebagai simpul awal yang baru.
e) Secara rekursif, ulangi langkah (b) s/d (c).
f) Bila proses rekursif pada (d) tidak dapat berlanjut lagi dan bila masih terdapat node lain
yang
g) adjacent dengan v , maka kita ulangi proses DFS dengan node tersebut sebagai node awal
h) yang baru, begitu seterusnya.
i) Bila semua node yang adjacent dengan v telah dikunjungi/ditandai semua, maka proses
DFS,
j) dengan v sebagai node awal, telah selesai.
k) Bila terdapat node-node lain v’∈ N yang tidak adjacent dengan v dan belum dikunjungi,
pilih
l) salah satu dari node tersebut sebagai node awal yang baru, dan ulangi proses DFS.
m) Pencarian berakhir bila seluruh simpul di G telah dikunjungi.

Anda mungkin juga menyukai