Page 16 - E-Book Kecerdasan Buatan Dandung PTI 1A

Code Python Metode DFS

jalur = {'M' : ['C','B','A'],
'A' : ['E','D'],
'D' : [],
'E' : ['K','J'],
'J' : ['Q','T'],
'T' : [],
'Q' : [],
'K' : [],
'B' : ['G','F'],
'F' : [],
def dfs(graf, mulai, tujuan):
'G' : ['N','L'],
star =[[mulai]]
'L' : ['T','R'],
visited = set()
'R' : [],
while star :
'T' : [],
#hitung panjang tumpukan dan masukkan ke variabel panjang_tumpukan
'N' : [],
panjang_tumpukan = len(star)-1
'C' : ['I','H'],
# Masukan tumpukan paling atas ke variabel jalur
'H' : ['P','O','T'],
jalur = star.pop(panjang_tumpukan)
'T' : [],
# Simpan node yang dipilih ke variabel state, misal jalur = C, B maka simpan B ke
'O' : ['S','T'],
Variabel state
'T' : [],
state = jalur[-1]
'S' : [],
# Cek state apakah sama dengan tujuan, jika ya maka return jalur
'P' : [],
if state == tujuan :
'I' : []
return jalur
}
# Jika state tidak sama dengan tujuan, maka cek apakah state tidak ada di visit
ed
elif state not in visited:
#jika statet 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 isi jalur baru dengan cabang
star.append(jalur_baru) # update queue dengan jalur_baru
#tandai state yang sudah dikunjungi sebagai visited
visited.add(state)
#cek isi antrian
isi = len(star)
if isi == 0:
print("tidaj ditemukan")

#memanggil fungsi
print("Hasil DFS : ", dfs(jalur,"M","T"))

13