BFS (BREADTH FIRST SEARCH) dengan contoh dan program dalam python

BREADTH FIRST SEARCH adalah Satu dari banyaknya algoritma pencarian path atau jalur secara melebar.

Syaratnya :

1. Mengunjungi node keberangkatan yang sudah ditentukan, lalu mengunjungi node lain yang bertetangga atau setara dengan node sebelumnya.

2. Menggunakan Queue atau antrian (First in first out) dimana setiap node yang dikunjungi akan dimasukkan ke dalam antrian tepat hanya 1 kali.

Step by step :

1. Masukkan node akar ke dalam queue.

2. Ambil node dari queue teratas, lalu cek apakah merupakan solusi?.

3. Jika node merupakan solusi, pencarian selesai, dan hasil dikembalikan.

4. Jika node bukan solusi, masukkan seluruh node anak ke dalam queue.

5. Jika queue kosong, dan setiap node sudah di cek, pencarian berakhir.

6. Jika queue tidak kosong, ulangi pencarian mulai step ke 2.

Contoh :

1. Tentukan vertexlist dan edgelist

2. Simulasikan pencarian jalur menggunakan BFS dengan node awal K dan node akhir D (Simulasikan 1 per 1 node)

3. Modifikasilah source code yang telah diberikan, lalu tentukan lah pencarian jalur menggunakan BFS dengan node awal K dan node akhir D.

Tree binernya seperti ini :

Jawab :

Buka link drive ini file berformat pdf.

https://drive.google.com/file/d/1Lmwx4fiL36o0g_rbdF4nWF3DfqzcOgDC/view?usp=sharing

Contoh program python bfs berikut ini link google colabsnya.

#Tessalonica Putry Avrylya - 672020167

#vertexlist dan edgelist dibuat list
graph = {
    'A': ['B', 'C'],
    'B': ['A','D','E'],
    'C': ['A','F','G'],
    'D': ['B','H'],
    'E': ['B','I'],
    'F': ['C'],
    'G': ['C','J','K'],
    'H': ['D'],
    'I': ['E'],
    'J': ['G'],
    'K': ['G','L'],
    'L': ['K'],
}

def bfs(graph_penelusuran, mulai, akhir):
    antre = [[mulai]]
    visited = set()

    while antre:
        #Jalur pertama dalam antre
        jalur = antre.pop(0)
        #Node terakhir di jalur
        vertex = jalur[-1]
        #Kroscek jalur apakah sampai akhir
        if vertex == akhir:
            return jalur
        #Kroscek node sudah berada di node yang dikunjungi supaya tidak mengulang
        elif vertex not in visited:
            #Mencari node yang berdekatan, membangun jalur baru dan memasukkannya ke dalam antre
            for current_neighbour in graph_penelusuran.get(vertex, []):
                new_jalur = list(jalur)
                new_jalur.append(current_neighbour)
                antre.append(new_jalur)
            #Tandai simpul yang sudah dikunjungi
            visited.add(vertex)
#Mencetak BFS
print (bfs(graph, 'K', 'D'))