Algoritma Breadth First Search (BFS) dengan Source Code Python

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.

Pada Postingan kali ini saya akan membagikan source code Algoritma BFS 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 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")

Dan ini adalah gambar dari graf yang dibuat permisalannya

Sekian, Terima Kasih