Penjelasan Breadth-First Search (BFS): cara kerja, kode, dan kompleksitas

Masalah yang diselesaikan BFS

Banyak masalah ternyata adalah graf: halaman web dan tautannya, teman dalam jejaring sosial, kotak pada papan permainan, keadaan sebuah puzzle. BFS menjawab dua pertanyaan umum pada graf semacam itu: node mana saja yang bisa dicapai dari node awal, dan berapa jumlah langkah paling sedikit untuk mencapai masing-masing node?

Karena BFS menjelajah dalam lingkaran berjarak makin jauh, saat pertama kali mencapai suatu node ia selalu lewat jalur dengan edge paling sedikit. Inilah yang menjadikan BFS algoritma standar untuk jalur terpendek ketika setiap edge berbiaya sama.

Ide dasar dengan kata-kata sederhana

1. Masukkan node awal ke dalam queue dan tandai sebagai sudah dikunjungi.
2. Ambil node di depan queue.
3. Untuk setiap tetangga yang belum dikunjungi, tandai sebagai sudah dikunjungi dan tambahkan ke belakang queue.
4. Ulangi langkah 2 dan 3 sampai queue kosong.

Tandai node sebagai sudah dikunjungi saat memasukkannya ke queue, bukan saat mengambilnya. Kalau tidak, node yang sama bisa ditambahkan berkali-kali sebelum diproses.

Contoh langkah demi langkah

Ambil graf tak berarah ini: A–B, A–C, B–D, C–D, C–E, D–F. Mulai dari A dan kunjungi tetangga sesuai urutan abjad.

Urutan kunjungannya adalah A, B, C, D, E, F. D bisa dicapai dari B maupun C, tetapi hanya ditemukan sekali, dari B, karena pada saat itu D sudah ditandai sebagai dikunjungi.

Implementasi Python

Gunakan collections.deque sebagai queue: popleft() berkompleksitas O(1), sedangkan list.pop(0) O(n). Graf direpresentasikan sebagai dictionary yang memetakan setiap node ke list tetangganya (adjacency list).

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

Di sini dictionary dist punya dua fungsi: sebagai himpunan node yang dikunjungi sekaligus penyimpan jawaban. Untuk merekonstruksi jalurnya, simpan juga parent dari setiap node lalu telusuri mundur dari target.

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

Time and space complexity

V adalah jumlah vertex (node) dan E jumlah edge. Dengan adjacency matrix alih-alih list, waktunya menjadi O(V²) karena mencari tetangga sebuah node membutuhkan O(V).

Varian dan kesalahan umum

• BFS pada grid: anggap setiap sel sebagai node dan empat (atau delapan) sel di sekitarnya sebagai edge. Periksa batas dan dinding sebelum menambahkan sel.
• BFS multi-sumber: masukkan beberapa node awal ke queue dengan jarak 0. Hasilnya adalah jarak ke sumber terdekat, misalnya pintu keluar terdekat dalam labirin.
• BFS 0-1: jika bobot edge hanya 0 atau 1, gunakan deque dan dorong tetangga berbobot 0 ke depan. Hasilnya jalur terpendek dalam O(V + E).
• BFS dua arah: cari dari node awal dan dari tujuan secara bersamaan, lalu berhenti saat kedua frontier bertemu. Cara ini sering menjelajah jauh lebih sedikit node.
• Pemrosesan per level: catat len(queue) di awal setiap putaran dan ambil tepat sebanyak itu node untuk menangani satu level sekaligus.

Kapan memakai BFS dan penggunaannya di dunia nyata

• Soal wawancara: jalur terpendek dalam labirin atau grid, word ladder, rotting oranges (BFS multi-sumber), penelusuran level-order pohon biner, jumlah langkah minimum kuda catur.
• Jaringan: mencari semua perangkat dalam k hop, broadcast di jaringan peer-to-peer, "orang yang mungkin Anda kenal" pada jarak 2 di graf sosial.
• Web crawler yang mengunjungi halaman berdasarkan jarak tautan dari halaman awal.
• Garbage collector (misalnya copying collector Cheney) dan pemecah puzzle yang membutuhkan langkah paling sedikit.