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

Code Python Metode BFS

jalur = {'M' : ['C','B','A'],
'A' : ['E','D'],
'D' : [],
'E' : ['K','J'],
'J' : ['Q','T'],
'T' : [],
'Q' : [],
'K' : [],
'B' : ['G','F'],
'F' : [],
'G' : ['N','L'],
'L' : ['T','R'],
'R' : [],
'T' : [],
'N' : [],
'C' : ['I','H'],
'H' : ['P','O','T'],
'T' : [],
'O' : ['S','T'],
'T' : [],
'S' : [],
'P' : [],
'I' : []
}
def bfs(graf, mulai, tujuan):
star =[[mulai]]
visited = set()
while star :
#masukkan antrian paling depan ke variabel jalur
jalur = star.pop(0)
# Simpan node yang dipilih ke variabel state, misal jalur = C, B maka simpan B ke variabel s
tate
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 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 BFS : ", bfs(jalur,"M","T"))

22