Penelusuran berdasarkan level

Penelusuran berdasarkan level, atau breadth-first search (BFS), menelusuri pohon dari atas ke bawah dengan menghabiskan seluruh node di satu level sebelum turun ke level berikutnya. Topik ini membangun penelusuran tersebut di atas antrian (queue) dari collections.deque, menampilkan keluaran per level, lalu membandingkannya dengan DFS untuk menentukan kapan masing-masing lebih cocok. Pohon contohnya adalah pohon enam node yang sama dengan penelusuran DFS, sehingga perbedaan urutan dapat diprediksi sebelum kode dijalankan. Versi Java menyusul dengan ArrayDeque yang berperilaku setara.

Antrian mengubah urutan kunjungan#

DFS menyimpan node-node yang menunggu giliran pada stack, baik sengaja maupun tidak, karena rekursi memakai call stack secara diam-diam. BFS menggantinya dengan antrian berprinsip first in, first out, sehingga node yang masuk lebih dulu juga keluar lebih dulu. Prosedurnya tetap pendek, yaitu keluarkan node paling depan antrian, catat nilainya, lalu masukkan anak kirinya dan anak kanannya bila ada. Karena anak-anak level 1 masuk sebelum cucu-cucu level 2 sempat masuk, seluruh level 1 pasti habis diproses sebelum level 2 dimulai.

Diagram berikut membagi pohon contoh menjadi tiga pita level. Urutan kunjungan 1 hingga 6 menyapu setiap pita dari kiri ke kanan, berbeda dengan preorder 1, 2, 4, 5, 3, 6 yang menuruni cabang kiri sampai habis lebih dahulu.

Anak kiri dimasukkan sebelum anak kanan agar urutan dalam satu level tetap kiri ke kanan. Menukar dua baris tersebut tidak merusak kebenaran penelusuran, tetapi membalik urutan antar node yang bersaudara dan membuat keluaran per level ikut terbalik. Kesepakatan kiri-dahulu inilah yang membuat keluaran BFS dapat diucapkan tanpa membaca kodenya. Jaga konsistensinya dari uji pertama hingga terakhir.

Implementasi dengan deque#

Modul collections menyediakan deque, struktur baris dua ujung dengan popleft() dan append() sama-sama berbiaya $O(1)$. Dua fungsi ditulis berdampingan pada berkas yang sama, satu menghasilkan urutan kunjungan datar dan satu mengelompokkan nilai per level.

"""Penelusuran pohon per level menggunakan antrian deque."""

from collections import deque

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def bfs_urutan(akar):
    # urutan kunjungan antarnode tanpa memandang level
    if akar is None:
        return []
    urutan = []
    antrian = deque([akar])
    while antrian:
        node = antrian.popleft()          # keluarkan node paling depan
        urutan.append(node.nilai)
        if node.kiri is not None:
            antrian.append(node.kiri)     # anak kiri masuk lebih dahulu
        if node.kanan is not None:
            antrian.append(node.kanan)
    return urutan

def bfs_per_level(akar):
    # kelompokkan nilai per level dengan menghitung isi antrian di awal level
    if akar is None:
        return []
    kelompok = []
    antrian = deque([akar])
    while antrian:
        ukuran = len(antrian)             # seluruh isi antrian berada di satu level
        level = []
        for _ in range(ukuran):
            node = antrian.popleft()
            level.append(node.nilai)
            if node.kiri is not None:
                antrian.append(node.kiri)
            if node.kanan is not None:
                antrian.append(node.kanan)
        kelompok.append(level)
    return kelompok

n = {v: Node(v) for v in [1, 2, 3, 4, 5, 6]}
n[1].kiri, n[1].kanan = n[2], n[3]
n[2].kiri, n[2].kanan = n[4], n[5]
n[3].kanan = n[6]
akar = n[1]

print("urutan kunjungan :", bfs_urutan(akar))
print("per level        :", bfs_per_level(akar))

urutan kunjungan : [1, 2, 3, 4, 5, 6]
per level        : [[1], [2, 3], [4, 5, 6]]

Kunci versi per level ada pada baris ukuran = len(antrian) yang dibaca sebelum perulangan dalam dimulai. Seluruh isi antrian pada saat itu memang berada di satu level yang sama, sehingga cukup diproses sebanyak ukuran kali sebelum turun ke level berikutnya. Anak-anak yang dimasukkan selama perulangan menumpuk di belakang dan menjadi isi penuh antrian untuk level berikutnya. Tanpa penghitung ini, nilai tetap keluar dalam urutan BFS tetapi batas antar level hilang, padahal banyak soal menuntut batas itu, misalnya soal yang menanyakan node terakhir setiap level.

Memilih antara DFS dan BFS#

Aturan praktisnya menyangkut bentuk pertanyaan soal. Soal yang menanyakan sifat kedalaman, seperti kedalaman maksimum, diameter, atau kesamaan dua pohon, lebih alami diselesaikan dengan DFS karena jawabannya dirakit dari anak menuju induk. Soal yang menanyakan sesuatu per level, seperti kelompok nilai per level atau node terkanan setiap level, langsung cocok dengan BFS karena level memang satuan kerjanya. BFS juga jawaban baku untuk jarak minimum dari root, karena level pertama yang memuat target pasti yang paling dekat tanpa perlu membandingkan lintasan lain. Hafalan yang layak dibawa: DFS menyusuri satu garis keturunan, sedangkan BFS menyapu satu generasi.

Tabel berikut merangkum perbedaan keduanya pada pohon dengan $n$ node.

Varian Java#

import java.util.ArrayDeque;
import java.util.Queue;

public class PenelusuranLevel {
    static class Node {
        int nilai;
        Node kiri, kanan;
        Node(int nilai) { this.nilai = nilai; }
    }

    public static void main(String[] args) {
        // pohon contoh yang sama dengan penelusuran DFS
        Node akar = new Node(1);
        akar.kiri = new Node(2);
        akar.kanan = new Node(3);
        akar.kiri.kiri = new Node(4);
        akar.kiri.kanan = new Node(5);
        akar.kanan.kanan = new Node(6);

        Queue<Node> antrian = new ArrayDeque<>();
        antrian.add(akar);
        int level = 0;
        while (!antrian.isEmpty()) {
            int ukuran = antrian.size();   // seluruh isi antrian berada di satu level
            StringBuilder baris = new StringBuilder();
            for (int i = 0; i < ukuran; i++) {
                Node node = antrian.remove();
                if (i > 0) baris.append(", ");
                baris.append(node.nilai);
                if (node.kiri != null) antrian.add(node.kiri);
                if (node.kanan != null) antrian.add(node.kanan);
            }
            System.out.println("level " + level + " : " + baris);
            level++;
        }
    }
}

level 0 : 1
level 1 : 2, 3
level 2 : 4, 5, 6

Java menyediakan antarmuka Queue yang diimplementasikan ArrayDeque, dan pasangan ini menjadi pilihan baku antrian tanpa hambatan konkurensi. Method add() menaruh di belakang, remove() mengeluarkan dari depan, dan size() memberi penghitung level, ketiganya dipetakan langsung dari versi Python. StringBuilder merakit nilai satu level menjadi satu baris sehingga keluarannya langsung memperlihatkan batas antar level. Program dijalankan dengan java PenelusuranLevel.java dan berhenti sendiri ketika antrian kosong. Perhatikan juga bahwa tidak ada rekursi sama sekali di sini, seluruh perulangan berbentuk while dan for biasa, bukti bahwa BFS justru paling nyaman ditulis secara iteratif.

Kesalahan umum#

1. Memakai list sebagai antrian dengan pop(0). Operasi pengeluaran menggeser seluruh isi list sehingga penelusuran jatuh ke $O(n^2)$. Ganti dengan collections.deque dan popleft() yang berbiaya $O(1)$.
2. Membaca len(antrian) di posisi yang salah. Ukuran level wajib dibaca sebelum perulangan dalam dimulai, bukan di dalamnya, karena antrian terus bertambah selama level diproses dan penghitung menjadi tidak terkendali.
3. Menyisakan pemeriksaan None pada anak. Menambahkan node.kiri tanpa memeriksa None memasukkan nilai kosong ke antrian dan memicu AttributeError saat nilai itu dikeluarkan. Periksa anak sebelum memasukkannya.
4. Membalik urutan anak tanpa sengaja. Memasukkan anak kanan lebih dahulu tidak merusak kebenaran BFS, tetapi urutan dalam level terbalik dan keluaran tidak lagi cocok dengan ekspektasi soal yang lazim kiri ke kanan.

Ringkasan#

• BFS menelusuri pohon per level menggunakan antrian first in, first out dengan biaya waktu $O(n)$.
• Keluaran per level diperoleh dengan membaca ukuran antrian di awal setiap level lalu memproses sebanyak ukuran itu.
• deque.popleft() berbiaya $O(1)$, sedangkan list.pop(0) berbiaya $O(n)$ per panggilan.
• DFS cocok untuk soal kedalaman dan diameter, BFS cocok untuk soal per level dan jarak minimum dari root.

Referensi#

• collections — Python Software Foundation — dokumentasi deque yang dipakai sebagai antrian BFS dengan popleft berbiaya konstan.
• VisuAlgo — visualisasi interaktif BFS pada pohon biner untuk memeriksa urutan kunjungan.