DFS pada graf

DFS (depth-first search) menelusuri graf dengan menuruni satu cabang sedalam mungkin sebelum mundur, sebuah pola yang tumbuh secara alami dari rekursi. Topik ini membangun DFS rekursif dan versi stack eksplisitnya, lalu memakainya untuk dua pekerjaan klasik, yaitu menghitung komponen terhubung dan mendeteksi siklus pada graf tak berarah. Pola yang sama ditutup dengan flood fill, bentuk DFS yang paling sering muncul pada soal kisi dua dimensi.

Kerangka DFS rekursif#

Inti DFS adalah satu aturan, yaitu tandai simpul saat masuk, lalu kunjungi setiap tetangga yang belum ditandai. Penandaan dilakukan di awal pemanggilan, bukan setelah perulangan tetangga selesai, karena penandaan yang terlambat membuat rekursi tidak pernah berhenti pada graf bersiklus. Tidak ada struktur data baru yang diperlukan di sini, sebab call stack dari rekursi sudah berperan sebagai tumpukan (stack) penyimpan simpul yang penelusurannya belum selesai. Total biayanya $O(V + E)$ karena setiap simpul dipanggil paling sekali dan setiap tepi disentuh paling dua kali.

Berkas berikut menjalankan tiga hal pada graf contoh tanpa tepi (3, 4), yaitu menelusuri dari simpul 0, menghitung komponen terhubung, dan memeriksa keberadaan siklus. Graf yang sama dipakai sepanjang topik ini agar perubahan antar versi mudah diamati. Setiap bagian keluarannya dibedah pada tiga bagian berikutnya.

# DFS rekursif: penelusuran, komponen terhubung, dan deteksi siklus.

# Graf contoh modul ini tanpa tepi (3, 4), sehingga terpisah dua komponen.
tepi = [(0, 1), (0, 2), (1, 3), (2, 3), (4, 5)]
n = 6

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

def dfs(simpul, dikunjungi, jejak):
    dikunjungi[simpul] = True  # tandai saat masuk, bukan setelah perulangan
    jejak.append(simpul)
    for t in tetangga[simpul]:
        if not dikunjungi[t]:
            dfs(t, dikunjungi, jejak)

# Penelusuran DFS dari simpul 0.
dikunjungi = [False] * n
jejak = []
dfs(0, dikunjungi, jejak)
print("DFS dari 0     :", jejak)

# Komponen terhubung: lanjutkan DFS dari setiap simpul yang belum dikunjungi.
komponen = 1  # komponen pertama sudah tercakup oleh DFS dari 0
for s in range(n):
    if not dikunjungi[s]:
        komponen += 1
        dfs(s, dikunjungi, jejak)
print("Jumlah komponen:", komponen)
print("Urutan lengkap :", jejak)

# Siklus tak berarah: tepi ke tetangga yang sudah dikunjungi selain induk.
def ada_siklus(simpul, induk, dikunjungi):
    dikunjungi[simpul] = True
    for t in tetangga[simpul]:
        if not dikunjungi[t]:
            if ada_siklus(t, simpul, dikunjungi):
                return True
        elif t != induk:
            return True
    return False

print("Ada siklus     :", ada_siklus(0, -1, [False] * n))

DFS dari 0     : [0, 1, 3, 2]
Jumlah komponen: 2
Urutan lengkap : [0, 1, 3, 2, 4, 5]
Ada siklus     : True

Urutan kunjungan dan komponen terhubung#

Baris pertama keluaran menunjukkan jejak 0, 1, 3, 2. Penelusuran masuk ke 0, turun ke 1, lalu ke 3, dan baru menyentuh 2, karena tetangga diproses sesuai urutan pencatatannya di adjacency list. Dari 2, kedua tetangganya sudah dikunjungi sehingga rekursi mundur total ke 0. Diagram berikut menggambarkan jalur itu beserta tepi 2 menuju 0 yang menjadi tanda siklus.

Baris kedua dan ketiga menjawab pertanyaan komponen. DFS dari 0 hanya menjangkau {0, 1, 2, 3}, sehingga perulangan atas seluruh simpul menemukan 4 yang belum dikunjungi, memulai DFS baru dari sana, dan penghitung komponen bertambah. Hasil akhirnya dua komponen dengan jejak lengkap 0, 1, 3, 2, 4, 5. Kerangka ini adalah jawaban standar untuk menghitung komponen, dan banyaknya DFS yang dimulai sama persis dengan banyaknya komponen yang ada.

Deteksi siklus pada graf tak berarah#

Aturan deteksinya satu kalimat, yaitu saat menyisir tetangga, temuan simpul yang sudah dikunjungi selain induk penelusuran berarti ada siklus. Induk (parent) adalah simpul yang memanggil, dan tepi menuju induk hanyalah tepi yang sama dilihat dari arah sebaliknya, bukan siklus. Pada graf contoh, ketika DFS berada di 2, tetangga 0 sudah dikunjungi dan bukan induknya, sehingga fungsi segera mengembalikan True. Baris keempat keluaran menegaskan siklus 0-1-3-2-0 yang tersusun dari empat tepi graf contoh.

Pola ini berlaku untuk graf tak berarah saja. Graf berarah membutuhkan penanda tambahan yang membedakan simpul sedang diproses dari simpul yang sudah selesai, karena tepi menuju simpul yang sudah selesai bukan siklus. Kasus ini ditemui kembali pada pembahasan urutan topologis. Untuk graf tak berarah, aturan induk saja sudah cukup dan mudah diingat.

DFS dengan stack eksplisit#

Rekursi dapat diganti tumpukan eksplisit, dan versi ini penting saat kedalaman graf melebihi batas rekursi bawaan Python. Mekanismenya, keluarkan simpul dari stack, lewati bila sudah dikunjungi, tandai, lalu dorong seluruh tetangga yang belum dikunjungi. Simpul boleh berada di stack lebih dari satu kali, dan pengecekan ulang saat keluar itulah yang menjaga setiap simpul tetap diproses sekali. Supaya tetangga bernilai kecil diproses lebih dahulu, tetangga didorong dalam urutan terbalik.

# DFS dengan stack eksplisit, tanpa pemanggilan rekursif.

# Graf contoh modul ini tanpa tepi (3, 4), sehingga terpisah dua komponen.
tepi = [(0, 1), (0, 2), (1, 3), (2, 3), (4, 5)]
n = 6

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

def dfs_stack(mulai):
    dikunjungi = [False] * n
    jejak = []
    tumpukan = [mulai]
    while tumpukan:
        simpul = tumpukan.pop()
        if dikunjungi[simpul]:
            continue  # simpul bisa masuk tumpukan lebih dari satu kali
        dikunjungi[simpul] = True
        jejak.append(simpul)
        # dimasukkan terbalik agar tetangga terkecil diproses lebih dahulu
        for t in reversed(tetangga[simpul]):
            if not dikunjungi[t]:
                tumpukan.append(t)
    return jejak

print("DFS dari 0 via stack:", dfs_stack(0))

DFS dari 0 via stack: [0, 1, 3, 2]

Keluarannya sama dengan versi rekursif, yaitu 0, 1, 3, 2. Kesamaan ini wajar karena kedua versi hanya berbeda tempat menyimpan simpul yang menunggu giliran. Bila urutan dorong tidak dibalik, hasilnya tetap penelusuran DFS yang sah, hanya jejaknya berbeda dan pembandingan keluaran antar versi menjadi sulit.

Flood fill pada kisi#

Flood fill adalah DFS yang grafnya tidak ditulis eksplisit, melainkan disimpulkan dari kisi (grid). Setiap sel adalah simpul, dan dua sel bertetangga searah empat arah saling terhubung bila nilainya sama. Karena satu sel hanya memiliki empat tetangga, tumpukan dapat menggantikan rekursi dengan aman, dan polanya sama persis dengan versi stack di atas.

# Flood fill dengan DFS stack: menandai seluruh sel terhubung pada kisi.
kisi = [list("..##."),
        list(".#..#"),
        list(".#..#"),
        list("..###")]
baris_n, kolom_n = len(kisi), len(kisi[0])

def isi(baris, kolom, pengganti):
    asal = kisi[baris][kolom]
    if asal == pengganti:
        return
    tumpukan = [(baris, kolom)]
    while tumpukan:
        b, k = tumpukan.pop()
        if not (0 <= b < baris_n and 0 <= k < kolom_n):
            continue  # keluar dari kisi
        if kisi[b][k] != asal:
            continue  # bukan sel yang boleh dirambah
        kisi[b][k] = pengganti
        for db, dk in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            tumpukan.append((b + db, k + dk))

print("Sebelum:")
for baris in kisi:
    print("".join(baris))

isi(0, 0, "o")
print("Sesudah isi(0, 0, 'o'):")
for baris in kisi:
    print("".join(baris))

Sebelum:
..##.
.#..#
.#..#
..###
Sesudah isi(0, 0, 'o'):
oo##.
o#..#
o#..#
oo###

Isi dimulai dari sel kiri atas dan hanya merambah sel titik yang terhubung, sehingga kantong titik di tengah yang terkurung pagar tetap utuh. Inilah perilaku yang membedakan flood fill dari sekadar mengganti seluruh nilai yang sama. Pola kisi seperti ini mendasari soal pulau, yaitu menghitung komponen sel daratan dengan menjalankan flood fill berulang kali.

Kesalahan umum#

Kesalahan ini muncul ketika penanda dikunjungi ditaruh di akhir fungsi alih-alih di awalnya. Pada pohon, urutan tersebut bahkan tampak benar karena pohon tidak punya siklus, sehingga bug baru terungkap begitu graf pertama yang bersiklus diuji. Perbaikannya sekaligus menjadi konvensi, yaitu tandai segera setelah masuk fungsi, sebelum menyisir tetangga. Versi stack eksplisit punya jebakan serupa, yaitu lupa melewati simpul yang sudah dikunjungi saat dikeluarkan dari tumpukan.

Ringkasan#

• DFS menandai simpul saat masuk lalu merekursi setiap tetangga yang belum ditandai, dengan biaya $O(V + E)$.
• Banyaknya DFS yang dimulai dari simpul yang belum dikunjungi sama dengan banyaknya komponen terhubung.
• Pada graf tak berarah, tepi menuju simpul yang sudah dikunjungi selain induk menandakan siklus.
• Versi stack eksplisit menggantikan rekursi, dan flood fill menerapkan pola yang sama pada kisi.

Referensi#

• Depth-first search — Wikipedia — Mekanisme DFS rekursif dan iteratif beserta penerapannya.
• Algorithms, 4th Edition — Princeton University — Bab graf berisi implementasi referensi DFS, komponen terhubung, dan siklus.