Depth First Search

BFS memilih lebar — semua node pada level k sebelum level k+1. Depth First Search (DFS) memilih kedalaman: dari node awal, DFS menelusuri satu cabang sebanyak mungkin sampai mentok (dead end), lalu mundur (backtrack) dan mencoba cabang lain. Pendekaran ini membuat DFS cocok untuk masalah yang membutuhkan eksplorasi menyeluruh terhadap struktur: deteksi siklus, topological sort pada DAG, penemuan Strongly Connected Components, dan pencarian path dalam maze. Pada Chapter ini kita akan melihat dua bentuk implementasi DFS — rekursif dan iteratif dengan stack eksplisit — serta kapan masing-masing lebih tepat dipakai.

Aturan: Telusuri Sedalam Mungkin #

Diberikan graph G = (V, E) dan node sumber src, DFS mengunjungi src, lalu memilih satu tetangga yang belum dikunjungi dan menjalankan DFS di sana secara rekursif. Saat sebuah node tidak punya tetangga yang belum dikunjungi, algoritma kembali (backtrack) ke node sebelumnya dan mencoba tetangga lainnya.

Mekanisme: Call Stack vs Explicit Stack #

Implementasi rekursif DFS memanfaatkan call stack bawaan compiler — setiap panggilan rekursif menambah satu frame stack yang menyimpan state pemanggil. Implementasi iteratif meniru perilaku tersebut dengan std::stack eksplisit. Keduanya menghasilkan traversal yang sama asalkan urutan push tetangga diatur konsisten.

Karena DFS memprioritaskan kedalaman, traversal tidak menjamin jalur terpendek. Sebagai gantinya, DFS efisien untuk struktur tree-like pada graph dan menjadi tulang punggung banyak algoritma tingkat lanjut.

Implementasi DFS Rekursif dan Iteratif #

#include <iostream>
#include <vector>
#include <stack>

class Graph {
    int n;
    std::vector<std::vector<int>> adj;
public:
    explicit Graph(int n) : n(n), adj(n) {}
    void add_edge(int u, int v) { adj[u].push_back(v); }

    void dfs_recursive(int src) {
        std::vector<bool> visited(n, false);
        std::cout << "DFS rekursif dari " << src << ": ";
        dfs_helper(src, visited);
        std::cout << '\n';
    }

    void dfs_iterative(int src) {
        std::vector<bool> visited(n, false);
        std::stack<int> st;
        st.push(src);
        std::cout << "DFS iteratif dari " << src << ": ";
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            if (visited[u]) continue;
            visited[u] = true;
            std::cout << u << ' ';
            // Push dalam urutan terbalik agar traversal sama dengan rekursif
            for (int i = static_cast<int>(adj[u].size()) - 1; i >= 0; --i) {
                int v = adj[u][i];
                if (!visited[v]) st.push(v);
            }
        }
        std::cout << '\n';
    }

private:
    void dfs_helper(int u, std::vector<bool>& visited) {
        visited[u] = true;
        std::cout << u << ' ';
        for (int v : adj[u]) {
            if (!visited[v]) dfs_helper(v, visited);
        }
    }
};

int main() {
    // Graph (directed):
    //   0 -> 1 -> 2
    //   |    |
    //   v    v
    //   3    4 -> 5
    Graph g(6);
    g.add_edge(0, 1);
    g.add_edge(0, 3);
    g.add_edge(1, 2);
    g.add_edge(1, 4);
    g.add_edge(4, 5);

    g.dfs_recursive(0);
    g.dfs_iterative(0);
    return 0;
}

Output yang Dihasilkan:

DFS rekursif dari 0: 0 1 2 4 5 3 
DFS iteratif dari 0: 0 1 2 4 5 3 

Bedah Kode Baris-per-Baris #

1. void add_edge(int u, int v): graph berarah. Untuk graph tak berarah, tambahkan adj[v].push_back(u) juga.
2. dfs_helper(int u, std::vector<bool>& visited): fungsi rekursif. Tandai u sebagai visited saat masuk, lalu untuk setiap tetangga belum dikunjungi, rekursi. Rekursi inilah yang “menyelam” ke kedalaman.
3. visited[u] = true di awal fungsi: penting dilakukan sebelum loop rekursi untuk mencegah panggilan berulang ke node yang sama dalam satu path.
4. std::stack<int> st; st.push(src);: inisialisasi stack eksplisit dengan node sumber. Stack LIFO meniru call stack versi rekursif.
5. int u = st.top(); st.pop();: ambil node paling atas. Perhatikan: belum tentu u belum dikunjungi — bisa jadi u sudah di-push beberapa kali sebelum diproses.
6. if (visited[u]) continue;: lazy skip. Karena kita push v ke stack tanpa menandainya (untuk meniru perilaku rekursif yang “menunggu giliran”), kita perlu skip jika u ternyata sudah diproses.
7. for (int i = ... ; i >= 0; --i): push tetangga dalam urutan terbalik. Stack LIFO berarti tetangga pertama yang di-push akan diproses terakhir — dengan membalik urutan, tetangga pertama dalam adjacency list akan diproses pertama, sama seperti rekursif.
8. Hasil identik: baik rekursif maupun iteratif menghasilkan 0 1 2 4 5 3, menunjukkan kedua implementasi setara bila urutan push diatur benar.

Kapan Pakai Rekursif vs Iteratif #

Penerapan DFS #

• Deteksi siklus (graph berarah): selama DFS, jika menemukan edge ke node GRAY (sedang diproses), maka ada siklus.
• Topological sort: DFS post-order reversed menghasilkan urutan topologis pada DAG.
• Strongly Connected Components: algoritma Kosaraju dan Tarjan memanfaatkan DFS.
• Articulation points dan bridges: DFS lowlink dengan array disc[] dan low[].
• Connected components (undirected): setiap inisialisasi DFS menemukan satu komponen.
• Path finding pada maze: backtracking dengan DFS menemukan satu path (belum tentu terpendek).

Kompleksitas #

Ringkasan #

• DFS menelusuri graph sedalam mungkin sebelum backtrack ke cabang lain.
• Rekursif memanfaatkan call stack; iteratif memakai std::stack eksplisit.
• Untuk hasil identik, push tetangga dalam urutan terbalik pada versi iteratif.
• DFS tidak menjamin jalur terpendek, namun menjadi fondasi topological sort, SCC, articulation points, dan deteksi siklus.
• Kompleksitas O(V + E) waktu; ruang O(V).

Bab berikutnya akan membahas salah satu penerapan langsung DFS: topological sorting pada Directed Acyclic Graph (DAG).