BFS pada graf

Lintasan tak berbobot terpendek dan penelusuran per level dengan antrian.

Daftar isi

BFS (breadth-first search) menelusuri graf lapis demi lapis dari satu simpul sumber dengan bantuan antrian, dan sifat itulah yang menjadikannya algoritma lintasan terpendek bawaan untuk graf tak berbobot. Topik ini membangun BFS di atas collections.deque, menghitung jarak terpendek dari sumber ke seluruh simpul, merekonstruksi lintasannya lewat rantai induk, lalu mengulang versi ringkasnya dalam Java dengan ArrayDeque. Graf enam simpul dengan tepi (0, 1), (0, 2), (1, 3), (2, 3), (3, 4), dan (4, 5) dipakai lagi sebagai contoh, sehingga urutan kunjungannya dapat ditebak sebelum kode dijalankan.

Antrian menghasilkan penelusuran per level#

BFS menyimpan simpul yang menunggu giliran pada antrian (queue) berprinsip first in, first out. Setiap putaran mengeluarkan simpul paling depan, lalu memasukkan semua tetangganya yang belum dikunjungi. Simpul level 1 masuk antrian sebelum simpul level 2 sempat masuk, dan pola ini berulang pada setiap pasangan lapisan berurutan. Seluruh lapisan berjarak k dari sumber karenanya pasti habis diproses lebih dahulu daripada lapisan berjarak k + 1. Urutan keluaran BFS pun terbaca sebagai sapuan per level, bukan penurunan satu cabang sampai dalam.

Diagram berikut membagi graf contoh menjadi lima level berdasarkan jarak dari simpul 0. Garis putus-putus dari 2 menuju 3 adalah tepi yang tidak menghasilkan kunjungan baru karena 3 sudah dimasukkan antrian oleh 1 lebih dahulu. Jumlah level dikurangi satu sama dengan jarak terjauh dari sumber, yaitu 4 pada simpul 5.

Level BFS pada graf contoh, dari level 0 berisi simpul 0 sampai level 4 berisi simpul 5

Implementasi BFS dengan deque#

Berkas berikut menjalankan BFS dari simpul 0 sambil mencatat jarak dan induk setiap simpul. Penanda kunjungan berupa array jarak yang diisi -1 sebelum penelusuran dimulai, dan simpul ditandai justru saat masuk antrian, bukan saat keluar. Detail kedua inilah yang mencegah satu simpul masuk antrian lebih dari sekali.

python bfs_graf.py

# BFS pada graf tak berarah: urutan kunjungan, jarak, dan lintasan.
from collections import deque

# Graf contoh enam simpul dari daftar tepi yang tetap.
tepi = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5)]
n = 6

tetangga = [[] for _ in range(n)]
for u, v in tepi:
    tetangga[u].append(v)
    tetangga[v].append(u)

mulai = 0
jarak = [-1] * n  # -1 berarti belum dikunjungi
induk = [-1] * n  # simpul asal saat pertama kali dicapai
urutan = []

antrian = deque([mulai])
jarak[mulai] = 0  # tandai saat masuk antrian, bukan saat keluar
while antrian:
    simpul = antrian.popleft()
    urutan.append(simpul)
    for t in tetangga[simpul]:
        if jarak[t] == -1:
            jarak[t] = jarak[simpul] + 1
            induk[t] = simpul
            antrian.append(t)

print("Urutan kunjungan:", urutan)
print("Jarak dari 0    :", jarak)

# Rekonstruksi lintasan 0 -> 5 dengan menyusuri rantai induk.
lintasan = []
posisi = 5
while posisi != -1:
    lintasan.append(posisi)
    posisi = induk[posisi]
lintasan.reverse()
print("Lintasan 0 -> 5 :", lintasan)

text Keluaran

Urutan kunjungan: [0, 1, 2, 3, 4, 5]
Jarak dari 0    : [0, 1, 1, 2, 3, 4]
Lintasan 0 -> 5 : [0, 1, 3, 4, 5]

Baris pertama menunjukkan sapuan 0, 1, 2, 3, 4, 5 yang menghabiskan level demi level, dan baris kedua memuat jarak terpendek dari 0 ke setiap simpul. Simpul 3 misalnya dicapai dengan dua tepi, baik lewat 1 maupun lewat 2, dan nilainya tidak tergantung urutan yang dipilih. Baris ketiga berupa lintasan yang sudah dibalik dari rantai induk, dan mekanismenya dibedah pada bagian berikutnya.

Jarak terpendek dan rekonstruksi lintasan#

Pada graf tak berbobot, jarak antar simpul diukur dari jumlah tepinya, dan BFS menjamin nilai tersebut optimal. Alasannya sederhana, yaitu simpul hanya masuk antrian satu kali dari tetangga yang jaraknya sudah final, sehingga tidak ada jalur pendek yang lolos. Sifat ini berlaku hanya bila setiap tepi berbobot sama, karena satu langkah antrian berarti satu satuan jarak. Graf berbobot membutuhkan perlakuan lain, misalnya algoritma Dijkstra.

Rekonstruksi lintasan tidak menuntut perulangan tambahan, cukup array induk yang mencatat simpul asal saat sebuah simpul pertama dimasukkan antrian. Untuk mencapai simpul 5, susuri rantainya mundur, yaitu 5 dari 4, 4 dari 3, 3 dari 1, dan 1 dari 0, lalu balikkan hasilnya. Prosedur mundur lalu balik inilah yang dikerjakan perulangan terakhir pada berkas di atas. Bentuknya sama persis ketika dipakai pada Dijkstra, sehingga pola ini layak diingat sekali saja.

Versi Java dengan ArrayDeque#

Versi Java memakai ArrayDeque sebagai antrian, kelas standar dengan add() dan poll() yang sama-sama berbiaya $O(1)$ . Rekonstruksi lintasan sengaja dipangkas agar fokusnya tetap pada inti BFS, yaitu antrian, penanda kunjungan, dan jarak. Isi larik jarak dicetak dengan Arrays.toString agar formatnya mirip versi Python.

java BfsGraf.java

// BFS dengan ArrayDeque: jarak terpendek pada graf tak berbobot.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class BfsGraf {
    public static void main(String[] args) {
        int n = 6;
        int[][] tepi = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}};

        List<List<Integer>> tetangga = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tetangga.add(new ArrayList<>());
        }
        for (int[] e : tepi) {
            tetangga.get(e[0]).add(e[1]);
            tetangga.get(e[1]).add(e[0]);
        }

        int[] jarak = new int[n];
        Arrays.fill(jarak, -1); // -1 berarti belum dikunjungi
        Deque<Integer> antrian = new ArrayDeque<>();
        antrian.add(0);
        jarak[0] = 0; // tandai saat masuk antrian
        List<Integer> urutan = new ArrayList<>();
        while (!antrian.isEmpty()) {
            int simpul = antrian.poll();
            urutan.add(simpul);
            for (int t : tetangga.get(simpul)) {
                if (jarak[t] == -1) {
                    jarak[t] = jarak[simpul] + 1;
                    antrian.add(t);
                }
            }
        }
        System.out.println("Urutan kunjungan: " + urutan);
        System.out.println("Jarak dari 0    : " + Arrays.toString(jarak));
    }
}

text Keluaran

Urutan kunjungan: [0, 1, 2, 3, 4, 5]
Jarak dari 0    : [0, 1, 1, 2, 3, 4]

Urutan kunjungan dan isi jarak identik dengan keluaran Python, menegaskan bahwa algoritmanya sama dan yang berubah hanya wadah antriannya. Kompleksitas waktunya $O(V + E)$ karena setiap simpul masuk antrian paling sekali dan setiap tepi diperiksa paling dua kali. Memori tambahannya juga $O(V + E)$ untuk adjacency list, ditambah $O(V)$ untuk antrian dan larik bantu.

Kesalahan umum#

Kesalahan ini sulit terlihat pada graf kecil karena keluarannya sering tetap benar, sekaligus mahal pada graf besar. Perbaikannya berupa satu baris, yaitu tandai simpul atau isi jaraknya tepat sebelum ia ditambahkan ke antrian. Dengan begitu satu simpul hanya punya satu tiket masuk antrian, dan jaraknya ditetapkan sekali oleh tetangga terdekatnya. Pemeriksaan cepatnya, ukuran antrian tidak boleh melebihi jumlah simpul pada graf.

Ringkasan#

BFS memakai antrian FIFO sehingga simpul diproses level demi level berdasarkan jarak dari sumber.
Pada graf tak berbobot, jarak yang ditetapkan saat simpul masuk antrian adalah jarak terpendek, dengan total biaya $O(V + E)$ .
Rantai induk yang dicatat selama penelusuran cukup untuk merekonstruksi lintasan tanpa perulangan tambahan.
Simpul ditandai dikunjungi saat masuk antrian agar tidak pernah masuk dua kali.

Referensi#

Breadth-first search — Wikipedia — Mekanisme BFS beserta sifat lintasan terpendeknya pada graf tak berbobot.
collections — Container datatypes — Python Docs — Dokumentasi deque yang dipakai sebagai antrian berbiaya $O(1)$ .