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).
Pada Postingan kali ini saya akan membagikan source code Algoritma DFS dengan menggunakan bahasa pemrograman Python, Berikut adalah source codenya :
#contoh peta
Peta = {'A':set(['B','H']),
'B':set(['A','C','H']),
'C':set(['B','D','E']),
'D':set(['C','E','F','G','H']),
'E':set(['C','D']),
'F':set(['D','G']),
'G':set(['F','G','H']),
'H':set(['A','B','D','G'])}
def dfs(graf, mulai, tujuan):
stack = [[mulai]]
visited = set()
while stack:
#hitung panjang tumpukan dan masukkan ke variabel panjang_tumpukan
panjang_tumpukan = len(stack)-1
# masukkan tumpukan paling atas ke variabel jalur
jalur = stack.pop(panjang_tumpukan)
# simpan node yang dipilih ke variabel state, misal jalur = C,B maka simpan B ke variabel state
state = jalur[-1]
# cek state apakah sama dengan tujuan, jika ya maka return jalur
if state == tujuan:
return jalur
# jika state tidak sama dengan tujuan, maka cek apakah state tidak ada di visited
elif state not in visited:
# jika state tidak ada di visited maka cek cabang
for cabang in graf.get(state, []): #cek semua cabang dari state
jalur_baru = list(jalur) #masukkan isi dari variabel jalur ke variabel jalur_baru
jalur_baru.append(cabang) #update/tambah isi jalur_baru dengan cabang
stack.append(jalur_baru) #update/tambah queue dengan jalur_baru
# tandai state yang sudah dikunjungi sebagai visited
visited.add(state)
#cek isi tumpukan
isi = len(stack)
if isi == 0:
print("Tidak ditemukan")
Dan ini adalah gambar dari graf yang dibuat permisalannya
Sekian, Terima Kasih
Tidak ada komentar:
Posting Komentar