Penjelasan Depth-First Search (DFS): cara kerja, kode, dan kompleksitas

Masalah yang diselesaikan DFS

DFS menjawab pertanyaan "apa saja yang bisa dicapai dari sini?" dengan menjelajahi satu cabang sampai tuntas sebelum mencoba cabang berikutnya. Urutan ini berguna ketika struktur jalur lebih penting daripada panjangnya: mencari jalan keluar labirin, memeriksa apakah graf memiliki siklus, mengurutkan tugas yang saling bergantung, atau mendaftar semua solusi sebuah puzzle.

Berbeda dengan breadth-first search, DFS tidak menemukan jalur terpendek. Kekuatannya: ia hanya menyimpan jalur saat ini di memori dan secara alami mencatat kapan sebuah node dimasuki dan kapan selesai diproses.

Ide dasar dengan kata-kata sederhana

1. Tandai node saat ini sebagai sudah dikunjungi.
2. Untuk setiap tetangga yang belum dikunjungi, pindah ke tetangga itu dan ulangi langkah 1 dari sana.
3. Ketika sebuah node tidak punya tetangga yang belum dikunjungi, node itu selesai: kembali ke node asal Anda datang.
4. Ketika Anda kembali ke node awal dan ia tidak punya tetangga yang belum dikunjungi, pencarian selesai.

Kembali ke node sebelumnya disebut backtracking. Pada rekursi, call stack yang melakukannya untuk Anda.

Contoh langkah demi langkah

Pakai graf tak berarah yang sama seperti di artikel BFS: A–B, A–C, B–D, C–D, C–E, D–F. Mulai dari A dan coba tetangga sesuai urutan abjad.

Urutan kunjungannya adalah A, B, D, C, E, F. Urutan selesainya adalah E, C, F, D, B, A. Urutan selesai inilah yang dipakai oleh topological sort dan algoritma strongly connected component.

Implementasi Python

Versi rekursif adalah yang paling singkat dan paling dekat dengan idenya:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

List membuat contoh mudah dibaca tetapi menjadikan in pemeriksaan O(n). Untuk graf besar, simpan set terpisah untuk pengecekan keanggotaan. Versi iteratif memakai stack eksplisit dan menghindari batas rekursi Python. Tetangga dimasukkan dalam urutan terbalik agar keluar dalam urutan aslinya:

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

Perhatikan perbedaannya dengan BFS: di sini node ditandai saat di-pop, sehingga bisa berada di stack lebih dari sekali. Itu benar untuk DFS dan mempertahankan urutan depth-first yang sebenarnya.

Mendeteksi siklus pada graf berarah

Aplikasi klasik DFS memberi warna pada setiap node: putih (belum terlihat), abu-abu (ada di jalur saat ini), dan hitam (selesai). Mencapai node abu-abu berarti ada edge kembali ke jalur saat ini, yaitu sebuah siklus.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

Kompleksitas waktu dan ruang

Varian dan kesalahan umum

• Pre-order dan post-order: catat node saat masuk (pre-order) atau saat selesai (post-order). Reverse post-order pada graf berarah tanpa siklus adalah urutan topologis.
• Komponen terhubung: mulai DFS baru dari setiap node yang masih belum dikunjungi; setiap awal adalah satu komponen.
• Iterative deepening DFS: jalankan DFS dengan batas kedalaman 0, 1, 2, … Ia menemukan jalur terpendek seperti BFS dengan memori rendah seperti DFS.
• Flood fill pada grid (alat paint bucket) adalah DFS atau BFS pada sel-sel bertetangga yang berwarna sama.

Bug lain yang sering terjadi: lupa membuat himpunan visited (loop tak berujung pada siklus apa pun), memakai argumen default yang mutable seperti visited=[] (dipakai bersama antar pemanggilan), dan menganggap edge tak berarah kembali ke parent sebagai siklus.

Kapan memakai DFS dan penggunaannya di dunia nyata

• Gunakan DFS untuk reachability, deteksi siklus, topological sort, komponen terhubung dan strongly connected, bridge dan articulation point, serta pencarian menyeluruh dengan backtracking.
• Gunakan BFS jika Anda butuh langkah paling sedikit, dan Dijkstra atau A* jika edge berbobot.
• Soal wawancara: number of islands, clone a graph, course schedule (deteksi siklus), path sum pada pohon biner, membangkitkan permutasi.
• Dunia nyata: build system dan package manager yang menentukan urutan dependensi, compiler yang menganalisis control flow, pembuatan labirin, dan penelusuran pohon pada sistem file atau dokumen HTML.