Pengertian Algoritma BFS
BFS, atau Breadth First Search, adalah algoritma yang digunakan untuk menelusuri atau menjelajahi semua node pada graf secara berurutan, dimulai dari node awal dan menyebar ke node tetangga sebelum melanjutkan ke node yang lebih jauh. Algoritma ini menggunakan pendekatan lebar, sehingga disebut juga dengan Breadth First.
Tujuan Algoritma BFS
1. Efisiensi Pencarian Jalur Terpendek
Algoritma BFS adalah salah satu alat terbaik untuk mencari jalur terpendek antara dua titik dalam graf. Dalam pemodelan transportasi, navigasi, atau jaringan komunikasi, BFS membantu dalam menemukan rute tercepat, menghemat waktu dan sumber daya.
2. Identifikasi Komponen Terhubung
BFS digunakan untuk mengidentifikasi komponen terhubung dalam graf. Ini berguna dalam analisis jaringan sosial, pemodelan jaringan komputer, dan bahkan dalam pemahaman hubungan antara objek dalam berbagai konteks.
3. Solusi untuk Teka-Teki dan Permainan
Dalam permainan teka-teki dan masalah kombinatorial, BFS membantu menemukan semua solusi yang mungkin. Ini memberikan pemain atau penyelesaian masalah gambaran lengkap tentang berbagai pilihan yang dapat diambil dan membantu dalam mengambil keputusan yang tepat.
Cara Kerja Algoritma BFS
1. Inisialisasi
Langkah pertama adalah menginisialisasi pencarian dengan menentukan simpul awal yang akan menjadi titik awal kita dalam menjelajahi graf. Simpul awal ini akan dimasukkan ke dalam antrian (queue) untuk memulai perjalanan.
2. Antrian (Queue)
Antrian berperan penting dalam algoritma BFS. Simpul awal dimasukkan ke dalam antrian, dan selanjutnya, simpul tetangga dari simpul awal akan secara berurutan dimasukkan ke dalam antrian. Ini memastikan bahwa BFS menjelajahi simpul pada kedalaman yang sama terlebih dahulu.
3. Perjalanan Menjelajah Graf
Saat simpul-simpul dimasukkan ke dalam antrian, BFS akan mengunjungi mereka satu per satu. Proses ini berlanjut hingga seluruh graf telah dijelajahi. Penting untuk diingat bahwa BFS akan mengunjungi semua simpul pada kedalaman yang sama sebelum melanjutkan ke tingkat kedalaman berikutnya.
4. Pemutakhiran Status Node
Selama pencarian, status setiap simpul akan diperbarui untuk menandai bahwa mereka telah dikunjungi. Hal ini penting untuk mencegah BFS dari mengunjungi simpul yang sama lagi dan lagi, yang dapat menyebabkan pengulangan tak terbatas.
Contoh Penerapan Algoritma BFS dengan Python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# Contoh graf
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B'],
'E': ['C', 'F'],
'F': ['E']
}
# Memanggil fungsi bfs
print("Jalur BFS:")
bfs(graph, 'A')