BFS vs DFS: Perbedaan dan Kapan Menggunakannya dalam Traversal Graf

Pendahuluan

Saat bekerja dengan struktur data graf atau tree, dua algoritma traversal paling fundamental yang wajib dikuasai setiap developer adalah Breadth-First Search (BFS) dan Depth-First Search (DFS). Keduanya digunakan untuk menjelajahi setiap node dalam sebuah graf, namun dengan strategi yang sangat berbeda.

Bayangkan kamu sedang mencari sebuah buku di perpustakaan. BFS seperti mencari rak per rak secara horizontal — kamu selesaikan seluruh rak baris pertama dulu, baru pindah ke baris berikutnya. DFS seperti mengikuti satu lorong sampai ujung, lalu kembali dan mencoba lorong lain.

Pemahaman mendalam tentang kapan menggunakan masing-masing algoritma sangat penting di dunia nyata — mulai dari fitur pencarian di aplikasi seperti Tokopedia, sistem rekomendasi di Gojek, hingga deteksi fraud di platform pembayaran seperti Dana.

Contoh Graf

Kita akan menggunakan graf berikut sepanjang artikel ini untuk menjalankan kedua algoritma:

    A
   / \
  B   C
 / \   \
D   E   F

Dalam bentuk adjacency list (Python dictionary):

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": [],
}

Graf ini merepresentasikan hubungan seperti hierarki kategori produk: A adalah kategori utama, B dan C adalah subkategori, dan D, E, F adalah item daun.

Memahami Breadth-First Search (BFS)

BFS menjelajahi graf level per level. Dimulai dari node asal, algoritma ini mengunjungi semua tetangga terdekat terlebih dahulu sebelum bergerak ke node yang lebih jauh.

Mekanisme kerja BFS menggunakan Queue (antrian):

from collections import deque


def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = set()              # Menyimpan node yang sudah dikunjungi
    queue = deque([start])       # Antrian untuk proses BFS
    order = []                   # Urutan kunjungan node

    visited.add(start)           # Tandai node awal sebagai sudah dikunjungi

    while queue:
        node = queue.popleft()   # Ambil node paling depan dari antrian
        order.append(node)       # Simpan node ke hasil traversal

        # Periksa semua tetangga dari node saat ini
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)    # Tandai tetangga sebagai dikunjungi
                queue.append(neighbor)   # Masukkan ke antrian

    return order

Menjalankan BFS pada contoh graf:

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": [],
}

hasil = bfs(graph, "A")
print(hasil)
# Output: ['A', 'B', 'C', 'D', 'E', 'F']

BFS mengunjungi A → lalu semua tetangga A yaitu B, C → baru kemudian tetangga dari B dan C yaitu D, E, F. Urutan ini menjamin node terdekat selalu dikunjungi lebih dulu.

Memahami Depth-First Search (DFS)

DFS menjelajahi graf sedalam mungkin di satu jalur sebelum mundur (backtrack) dan mencoba jalur lain. Ada dua cara implementasi: rekursif dan iteratif menggunakan Stack.

DFS Rekursif

def dfs_rekursif(
    graph: dict[str, list[str]],
    node: str,
    visited: set | None = None,
    order: list | None = None,
) -> list[str]:
    if visited is None:
        visited = set()
    if order is None:
        order = []

    visited.add(node)       # Tandai node saat ini sebagai sudah dikunjungi
    order.append(node)      # Simpan ke hasil traversal

    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs_rekursif(graph, neighbor, visited, order)  # Rekursi ke tetangga

    return order

DFS Iteratif (menggunakan Stack)

def dfs_iteratif(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = set()
    stack = [start]          # Stack menggantikan rekursi
    order = []

    while stack:
        node = stack.pop()   # Ambil node paling atas dari stack

        if node not in visited:
            visited.add(node)
            order.append(node)

            # Masukkan tetangga ke stack (dibalik agar urutan konsisten)
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

Menjalankan DFS pada contoh graf:

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": [],
}

hasil_rekursif = dfs_rekursif(graph, "A")
print(hasil_rekursif)
# Output: ['A', 'B', 'D', 'E', 'C', 'F']

hasil_iteratif = dfs_iteratif(graph, "A")
print(hasil_iteratif)
# Output: ['A', 'B', 'D', 'E', 'C', 'F']

DFS dari A langsung mendalami jalur A → B → D hingga ujung, lalu backtrack ke E, kemudian kembali ke A untuk melanjutkan ke C → F.

Perbandingan BFS vs DFS

Kapan Menggunakan BFS?

Gunakan BFS ketika:

• Mencari jalur terpendek pada graf tidak berbobot — misalnya fitur “teman terdekat” di aplikasi sosial
• Traversal level per level diperlukan — misalnya mencetak struktur organisasi tier per tier
• Target kemungkinan dekat dari node awal — misalnya pencarian produk di kategori terdekat

def cari_jalur_terpendek(
    graph: dict[str, list[str]], start: str, target: str
) -> list[str] | None:
    """Mencari jalur terpendek dari start ke target menggunakan BFS."""
    if start == target:
        return [start]

    visited = {start}
    queue = deque([[start]])  # Simpan jalur lengkap, bukan hanya node

    while queue:
        path = queue.popleft()
        node = path[-1]

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == target:
                    return new_path
                visited.add(neighbor)
                queue.append(new_path)

    return None  # Target tidak ditemukan


# Contoh penggunaan
graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": [],
}

jalur = cari_jalur_terpendek(graph, "A", "E")
print(jalur)
# Output: ['A', 'B', 'E']

Kapan Menggunakan DFS?

Gunakan DFS ketika:

• Mendeteksi siklus dalam graf — misalnya validasi dependensi package
• Topological sorting — menentukan urutan task yang saling bergantung
• Mencari semua jalur yang mungkin — misalnya pencarian rute alternatif
• Memori terbatas — DFS lebih hemat memori untuk graf yang sangat lebar

def deteksi_siklus(graph: dict[str, list[str]]) -> bool:
    """Mendeteksi apakah ada siklus dalam graf berarah menggunakan DFS."""
    visited = set()
    sedang_diproses = set()  # Node di call stack saat ini

    def dfs(node: str) -> bool:
        visited.add(node)
        sedang_diproses.add(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in sedang_diproses:
                return True  # Siklus ditemukan

        sedang_diproses.remove(node)
        return False

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True

    return False


# Graf tanpa siklus
graph_acyclic = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(deteksi_siklus(graph_acyclic))
# Output: False

# Graf dengan siklus
graph_cyclic = {"A": ["B"], "B": ["C"], "C": ["A"]}
print(deteksi_siklus(graph_cyclic))
# Output: True

FAQ

Q: Apakah BFS selalu lebih lambat dari DFS?

Tidak. Kompleksitas waktu keduanya sama, yaitu O(V + E) di mana V adalah jumlah vertex dan E adalah jumlah edge. Perbedaan performa biasanya terletak pada penggunaan memori dan apakah target berada dekat atau jauh dari node awal.

Q: Kapan DFS rekursif lebih baik dari DFS iteratif?

DFS rekursif lebih mudah dibaca dan ditulis untuk kebanyakan kasus. Namun, untuk graf yang sangat dalam (ribuan level), DFS rekursif berisiko menyebabkan stack overflow. Dalam kasus tersebut, gunakan versi iteratif dengan stack eksplisit.

Q: Bisakah BFS digunakan pada graf berbobot?

BFS hanya menjamin jalur terpendek berdasarkan jumlah edge, bukan bobot edge. Untuk graf berbobot, gunakan algoritma Dijkstra (bobot positif) atau Bellman-Ford (bobot negatif).

Q: Apakah BFS dan DFS bisa digunakan pada graf tidak terhubung (disconnected graph)?

Ya. Untuk menjelajahi seluruh node pada graf tidak terhubung, jalankan BFS atau DFS dari setiap node yang belum dikunjungi:

def bfs_semua_komponen(graph: dict[str, list[str]]) -> list[list[str]]:
    """BFS untuk graf tidak terhubung — mengembalikan semua komponen."""
    visited = set()
    komponen = []

    for node in graph:
        if node not in visited:
            komponen.append(bfs(graph, node))
            visited.update(komponen[-1])

    return komponen

Q: Mana yang lebih sering digunakan di industri?

Keduanya digunakan secara luas. BFS lebih umum untuk masalah shortest path dan level-order processing. DFS lebih umum untuk topological sort, deteksi siklus, dan pencarian dalam struktur tree seperti parsing ekspresi atau traversal file system.