Kembali

Memahami Algoritma Depth-First Search (DFS)

Selami dunia penjelajahan grafik secara mendalam.

Apa itu Algoritma Depth-First Search (DFS)?

Depth-First Search (DFS) adalah algoritma untuk melintasi atau mencari elemen dalam struktur data seperti pohon atau grafik. Algoritma ini memulai penjelajahan dari sebuah node akar (atau node yang dipilih) dan menjelajahi sejauh mungkin di sepanjang setiap cabang sebelum melakukan *backtrack*. Ini seperti menjelajahi sebuah labirin: Anda memilih satu jalur dan mengikutinya sejauh mungkin hingga Anda menemui jalan buntu atau menemukan yang Anda cari, baru kemudian Anda kembali (backtrack) dan mencoba jalur lain.

DFS memiliki berbagai aplikasi penting dalam ilmu komputer, di antaranya:

  • Pencarian jalur: Menemukan jalur antara dua node dalam grafik.
  • Deteksi siklus: Mengidentifikasi apakah ada siklus dalam grafik.
  • Pengurutan topologis: (Alternatif untuk Algoritma Kahn) untuk grafik asiklik terarah (DAG).
  • Menemukan komponen terhubung: Mengidentifikasi semua node yang dapat dijangkau dari node tertentu.
  • Penyelesaian puzzle: Seperti memecahkan labirin atau Sudoku.
  • Analisis jaringan: Menjelajahi struktur jaringan.

Cara Kerja Algoritma Depth-First Search (DFS)

DFS biasanya diimplementasikan menggunakan tumpukan (stack) atau secara rekursif (yang secara implisit menggunakan stack panggilan sistem). Berikut adalah langkah-langkah intinya:

  1. Inisialisasi:
    • Buat sebuah set (atau array boolean) untuk melacak node yang sudah dikunjungi.
    • Mulai dari sebuah node awal (start node). Tandai node ini sebagai dikunjungi dan tambahkan ke tumpukan (jika menggunakan implementasi iteratif).
  2. Penjelajahan:
    • Selama tumpukan tidak kosong (atau jika fungsi rekursif dipanggil):
      • Ambil (pop) node teratas dari tumpukan (atau dari parameter fungsi rekursif, yaitu node saat ini).
      • Proses node ini (misalnya, cetak, tambahkan ke daftar hasil).
      • Untuk setiap tetangga dari node saat ini yang belum dikunjungi:
        • Tandai tetangga tersebut sebagai dikunjungi.
        • Tambahkan tetangga tersebut ke tumpukan (jika iteratif) atau panggil fungsi DFS secara rekursif pada tetangga tersebut.
  3. Backtracking:
    • Ketika semua tetangga dari sebuah node telah dikunjungi atau tidak ada tetangga yang belum dikunjungi, algoritma secara otomatis akan "kembali" (backtrack) ke node sebelumnya di tumpukan (atau kembali dari panggilan rekursif) dan melanjutkan penjelajahan dari sana.

Contoh Permasalahan

Mari kita gunakan contoh grafik sederhana untuk memahami DFS:

Grafik:

    A
   / \
  B   C
 / \   \
D   E   F

Tujuan: Jelajahi grafik ini menggunakan DFS, dimulai dari Node A.

Langkah-langkah dengan Algoritma DFS (rekursif):

  1. Mulai DFS(A).
    • Output: A
    • Tandai A sebagai dikunjungi.
    • Tetangga A adalah B, C.
  2. Panggil DFS(B). (DFS menjelajahi ke dalam dari A)
    • Output: B
    • Tandai B sebagai dikunjungi.
    • Tetangga B adalah A, D, E. A sudah dikunjungi.
    • Tetangga D belum dikunjungi.
  3. Panggil DFS(D). (DFS menjelajahi ke dalam dari B)
    • Output: D
    • Tandai D sebagai dikunjungi.
    • Tidak ada tetangga D yang belum dikunjungi.
    • *Backtrack* ke B.
  4. Kembali ke DFS(B).
    • Tetangga E belum dikunjungi.
  5. Panggil DFS(E). (DFS menjelajahi ke dalam dari B)
    • Output: E
    • Tandai E sebagai dikunjungi.
    • Tidak ada tetangga E yang belum dikunjungi.
    • *Backtrack* ke B.
  6. Kembali ke DFS(B).
    • Semua tetangga B sudah dikunjungi.
    • *Backtrack* ke A.
  7. Kembali ke DFS(A).
    • Tetangga C belum dikunjungi.
  8. Panggil DFS(C). (DFS menjelajahi ke dalam dari A)
    • Output: C
    • Tandai C sebagai dikunjungi.
    • Tetangga C adalah A, F. A sudah dikunjungi.
    • Tetangga F belum dikunjungi.
  9. Panggil DFS(F). (DFS menjelajahi ke dalam dari C)
    • Output: F
    • Tandai F sebagai dikunjungi.
    • Tidak ada tetangga F yang belum dikunjungi.
    • *Backtrack* ke C.
  10. Kembali ke DFS(C).
    • Semua tetangga C sudah dikunjungi.
    • *Backtrack* ke A.
  11. Kembali ke DFS(A).
    • Semua tetangga A sudah dikunjungi.
    • DFS selesai.

Urutan Penjelajahan (Output): A, B, D, E, C, F

Implementasi Kode (C++)

Berikut adalah contoh implementasi Algoritma DFS sederhana menggunakan C++. Dalam konteks Next.js, Anda mungkin akan berinteraksi dengan algoritma ini melalui API atau library yang ditulis dalam bahasa lain (misalnya Python atau JavaScript untuk backend), atau mengimplementasikannya dalam JavaScript/TypeScript jika grafiknya kecil dan di sisi klien.

#include <iostream>
#include <vector>
#include <stack>   // Untuk implementasi iteratif
#include <set>     // Atau std::vector<bool> visited;

// Representasi graf menggunakan adjacency list
// adj[u] akan berisi daftar node yang terhubung dari u
std::vector<std::vector<int>> adj;
std::vector<bool> visited; // Untuk melacak node yang sudah dikunjungi

// Fungsi DFS Rekursif
void dfsRecursive(int u) {
    visited[u] = true;
    std::cout << u << " "; // Proses node (misalnya, cetak)

    // Iterasi melalui semua tetangga dari node u
    // Asumsi graf tidak berarah, jadi sisi A-B berarti A->B dan B->A
    // Untuk graf berarah, hanya tambahkan sisi sekali sesuai arah.
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfsRecursive(v); // Panggil DFS rekursif untuk tetangga yang belum dikunjungi
        }
    }
}

// Fungsi DFS Iteratif (menggunakan stack eksplisit)
void dfsIterative(int startNode) {
    // Inisialisasi visited khusus untuk iteratif agar bisa di-run terpisah
    std::vector<bool> localVisited(adj.size(), false);
    std::stack<int> s;

    s.push(startNode); // Masukkan node awal ke stack
    localVisited[startNode] = true; // Tandai sebagai dikunjungi

    while (!s.empty()) {
        int u = s.top(); // Ambil node teratas
        s.pop();         // Hapus dari stack

        std::cout << u << " "; // Proses node

        // Penting: Masukkan tetangga ke stack dalam urutan terbalik
        // agar node dengan indeks lebih kecil (atau sesuai urutan adj)
        // diproses lebih dulu saat pop. Ini meniru perilaku rekursif
        // yang secara implisit memproses anak pertama yang ditemui.
        for (int i = adj[u].size() - 1; i >= 0; --i) {
            int v = adj[u][i];
            if (!localVisited[v]) {
                localVisited[v] = true;
                s.push(v);
            }
        }
    }
}

int main() {
    int numNodes = 6; // Node 0 hingga 5 (A=0, B=1, C=2, D=3, E=4, F=5)
    adj.resize(numNodes);
    visited.resize(numNodes, false); // Global visited untuk fungsi rekursif

    // Membangun graf (sesuai contoh di atas)
    // Asumsi graf tidak berarah untuk contoh ini (sisi dua arah)
    adj[0].push_back(1); // A <-> B
    adj[1].push_back(0);
    adj[0].push_back(2); // A <-> C
    adj[2].push_back(0);
    adj[1].push_back(3); // B <-> D
    adj[3].push_back(1);
    adj[1].push_back(4); // B <-> E
    adj[4].push_back(1);
    adj[2].push_back(5); // C <-> F
    adj[5].push_back(2);

    std::cout << "DFS Rekursif (mulai dari node 0): ";
    dfsRecursive(0); // Panggil DFS rekursif dari node 0 (A)
    std::cout << "\n";

    // Untuk menjalankan DFS iteratif, kita perlu membersihkan state global visited
    // jika kita menggunakan visited global untuk kedua fungsi.
    // Namun, karena dfsIterative menggunakan localVisited, ini tidak perlu.
    // Baris ini opsional jika Anda ingin me-reset visited global untuk tujuan lain:
    // std::fill(visited.begin(), visited.end(), false);

    std::cout << "DFS Iteratif (mulai dari node 0): ";
    dfsIterative(0); // Panggil DFS iteratif dari node 0 (A)
    std::cout << "\n";

    return 0;
}

Kelebihan dan Kekurangan

Kelebihan Algoritma DFS:

  • Sederhana: Konsepnya mudah dipahami, terutama implementasi rekursifnya.
  • Penggunaan Memori Lebih Rendah: Untuk graf yang luas dan dangkal, DFS bisa menggunakan memori yang lebih sedikit dibandingkan BFS (Breadth-First Search) karena tidak perlu menyimpan semua node pada level yang sama dalam antrean.
  • Banyak Aplikasi: Efektif untuk mendeteksi siklus, pengurutan topologis, dan menemukan komponen terhubung.
  • Menemukan Jalur: Bagus untuk menemukan *salah satu* jalur antara dua node (tidak harus yang terpendek).

Kekurangan Algoritma DFS:

  • Tidak Optimal untuk Jalur Terpendek: DFS tidak menjamin penemuan jalur terpendek dalam graf yang tidak berbobot atau berbobot, karena ia menjelajahi "sedalam mungkin" terlebih dahulu. Untuk jalur terpendek, BFS atau Dijkstra lebih cocok.
  • Bisa Terjebak dalam Loop (jika tidak ada `visited`): Jika graf memiliki siklus dan kita tidak melacak node yang sudah dikunjungi, DFS bisa terjebak dalam loop tak terbatas.
  • Kompleksitas Waktu: Kompleksitas waktu DFS adalah O(V + E), di mana V adalah jumlah node dan E adalah jumlah sisi, yang efisien. Namun, performa aktual dapat bervariasi tergantung pada struktur graf.

Kesimpulan

Algoritma Depth-First Search adalah alat yang sangat fundamental dan serbaguna dalam dunia algoritma grafik. Kemampuannya untuk menjelajahi graf secara mendalam membuatnya ideal untuk tugas-tugas seperti deteksi siklus dan pengurutan topologis. Meskipun bukan pilihan terbaik untuk mencari jalur terpendek, kesederhanaan dan efisiensinya dalam banyak kasus menjadikannya algoritma yang harus Anda kuasai.