# Breadth First Search (BFS)
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.
Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.
Nah disini kita langsung saja ke gambar grafik dan beserta contoh source code yang saya buat disini saya membuatnya menggunakan python
#Code Program
#contoh Peta
peta = {'A':set(['B']),
'B':set(['A','C','D']),
'C':set(['B','E']),
'D':set(['B','G','H']),
'E':set(['C','F','G']),
'F':set(['E']),
'G':set(['D','E','I','J']),
'H':set(['D','J']),
'I':set(['G'])}
def bfs(graf, mulai, tujuan):
queue = [[mulai]]
visited = set()
while queue:
# masukkan antrian paling depan ke variabel jalur
jalur = queue.pop(0)
# 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
queue.append(jalur_baru) #update/tambah queue dengan jalur_baru
# tandai state yang sudah dikunjungi sebagai visited
visited.add(state)
#cek isi antrian
isi = len(queue)
if isi == 0:
print("Tidak ditemukan")
# Hasil Program
Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.
Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.
Nah disini kita langsung saja ke contoh source code yang saya buat disini saya membuatnya menggunakan python.
#Code Program
#contoh Peta
peta = {'A':set(['B']),
'B':set(['A','C','D']),
'C':set(['B','E']),
'D':set(['B','G','H']),
'E':set(['C','F','G']),
'F':set(['E']),
'G':set(['D','E','I','J']),
'H':set(['D','J']),
'I':set(['G'])}
def dfs(graf, mulai, tujuan):
stack = [[mulai]]
visited = set()
while stack:
# masukkan antrian paling depan ke variabel jalur
jalur = stack.pop(-1)
# 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 antrian
isi = len(stack)
if isi == 0:
print("Tidak ditemukan")
# Hasil Program
