Graph Traversal

Setelah graph tersimpan dalam memori, tugas berikutnya adalah mengunjungi vertex satu per satu. Dua algoritma traversal utama, Breadth First Search (BFS) dan Depth First Search (DFS), menjadi fondasi hampir seluruh algoritma graph lainnya: shortest path, connected components, cycle detection, topological sort, dan bipartite check semuanya dibangun di atas BFS atau DFS. Pada Chapter ini kita akan mengimplementasikan keduanya, memvisualisasikan urutan kunjungan, lalu menganalisis kapan masing-masing cocok dipakai. Pemahaman mendalam terhadap kedua traversal ini adalah gerbang menuju algoritma graph yang lebih kompleks.

Inti BFS dan DFS #

Kedua algoritma traversal berbagi kerangka umum:

Mulai dari vertex sumber s.
Tandai s sebagai visited.
Loop: ambil vertex berikutnya dari struktur data, kunjungi semua neighbor-nya yang belum visited, masukkan ke struktur data.
Berhenti bila struktur data kosong.

Perbedaan utama adalah struktur data yang dipakai:

BFS memakai queue (FIFO) — vertex pertama dimasukkan akan pertama diproses. Hasil: traversal level-by-level.
DFS memakai stack (LIFO) — vertex terakhir dimasukkan akan pertama diproses. Hasil: traversal mendalam lebih dulu (sampai ujung sebelum backtracking).
DFS rekursif memakai call stack — implementasi paling ringkas.

flowchart LR A[1] --- B[2] A --- C[3] B --- D[4] B --- E[5] C --- F[6] C --- G[7]

Untuk graph di atas dengan sumber 1:

BFS order: 1, 2, 3, 4, 5, 6, 7 (per level: level 0 = {1}, level 1 = {2,3}, level 2 = {4,5,6,7}).
DFS order (rekursif): 1, 2, 4, 5, 3, 6, 7 (turun ke 2, lalu ke 4, backtrack ke 5, backtrack ke 1, lalu ke 3 dan seterusnya).

Implementasi BFS #

Aturan #

Pakai std::queue<int>.
Tandai vertex sebagai visited saat dimasukkan ke queue (bukan saat di-pop). Ini mencegah vertex sama dimasukkan beberapa kali.
Untuk shortest path pada unweighted graph, simpan dist[u] = jarak dari sumber.

Kode: BFS dengan Tracking Jarak #

cpp
#include <iostream>
#include <vector>
#include <queue>

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

// BFS: return (order, distance) dari source
std::pair<std::vector<int>, std::vector<int>> bfs(const Graph& g, int src) {
    int n = g.v_count();
    std::vector<int> order, dist(n, -1);
    std::vector<bool> visited(n, false);
    std::queue<int> q;

    visited[src] = true;
    dist[src] = 0;
    q.push(src);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : g.neighbors(u)) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return {order, dist};
}

int main() {
    Graph g(8);  // vertex 0..7 (vertex 0 sebagai dummy)
    // edges: 1-2, 1-3, 2-4, 2-5, 3-6, 3-7
    g.add_edge_undirected(1, 2);
    g.add_edge_undirected(1, 3);
    g.add_edge_undirected(2, 4);
    g.add_edge_undirected(2, 5);
    g.add_edge_undirected(3, 6);
    g.add_edge_undirected(3, 7);

    auto [order, dist] = bfs(g, 1);

    std::cout << "BFS order from vertex 1:\n  ";
    for (int u : order) std::cout << u << ' ';
    std::cout << '\n';

    std::cout << "\nDistance from vertex 1:\n";
    for (int u = 1; u < g.v_count(); ++u) {
        std::cout << "  d(1," << u << ") = " << dist[u] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
BFS order from vertex 1:
  1 2 3 4 5 6 7

Distance from vertex 1:
  d(1,1) = 0
  d(1,2) = 1
  d(1,3) = 1
  d(1,4) = 2
  d(1,5) = 2
  d(1,6) = 2
  d(1,7) = 2

Baris visited[src] = true; dist[src] = 0; q.push(src);: inisialisasi. Penting: tandai visited sebelum push, agar vertex tidak diduplikasi di queue.
Baris int u = q.front(); q.pop();: ambil vertex paling depan queue. FIFO memastikan urutan level-by-level.
Baris if (!visited[v]): hanya proses neighbor yang belum dikunjungi. Tanpa cek ini, BFS bisa infinite loop pada graph dengan cycle.
Baris visited[v] = true; dist[v] = dist[u] + 1; q.push(v);: tandai visited saat push, simpan jarak (parent’s distance + 1), lalu push. Inilah inti BFS shortest path untuk unweighted graph.
Hasil BFS order: 1 2 3 4 5 6 7: urutan kunjungan persis level-by-level. Vertex 1 (level 0) → 2,3 (level 1) → 4,5,6,7 (level 2).
Hasil d(1,4) = 2: jalur 1→2→4, 2 edge. BFS menjamin ini adalah shortest path pada unweighted graph.

Implementasi DFS #

DFS dapat diimplementasikan dua cara: rekursif (memakai call stack) atau iteratif (memakai std::stack eksplisit). Versi rekursif lebih ringkas; versi iteratif menghindari stack overflow pada graph dalam.

Kode: DFS Rekursif #

cpp
#include <iostream>
#include <vector>

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

void dfs_rec(const Graph& g, int u, std::vector<bool>& visited, std::vector<int>& order) {
    visited[u] = true;
    order.push_back(u);
    for (int v : g.neighbors(u)) {
        if (!visited[v]) dfs_rec(g, v, visited, order);
    }
}

int main() {
    Graph g(8);  // vertex 0 dummy, 1..7 dipakai
    g.add_edge_undirected(1, 2);
    g.add_edge_undirected(1, 3);
    g.add_edge_undirected(2, 4);
    g.add_edge_undirected(2, 5);
    g.add_edge_undirected(3, 6);
    g.add_edge_undirected(3, 7);

    std::vector<bool> visited(g.v_count(), false);
    std::vector<int> order;
    dfs_rec(g, 1, visited, order);

    std::cout << "DFS order (recursive) from vertex 1:\n  ";
    for (int u : order) std::cout << u << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

DFS order (recursive) from vertex 1:
  1 2 4 5 3 6 7

Baris void dfs_rec(...): fungsi rekursif. Setiap pemanggilan menyimpan state (vertex saat ini, iterator) pada call stack.
Baris visited[u] = true; order.push_back(u);: tandai visited dan catat urutan saat pertama kali memasuki vertex. Inilah pre-order traversal.
Baris if (!visited[v]) dfs_rec(...): rekursi ke neighbor yang belum visited. Karena neighbor 2 ada sebelum 3 pada adjacency list, DFS turun ke 2 dulu, lalu ke 4, lalu ke 5, baru backtrack ke 1 lalu ke 3.
Hasil 1 2 4 5 3 6 7: urutan DFS menunjukkan pola “turun sampai ujung, baru backtrack”. Vertex 4 (leaf) dikunjungi sebelum vertex 3 meski 3 ada di level 1 — inilah perbedaan mendasar dari BFS.

Kode: DFS Iteratif dengan Stack Eksplisit #

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

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

std::vector<int> dfs_iter(const Graph& g, int src) {
    int n = g.v_count();
    std::vector<bool> visited(n, false);
    std::vector<int> order;
    std::stack<int> st;

    st.push(src);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;        // bisa saja sudah dikunjungi
        visited[u] = true;
        order.push_back(u);

        // Push neighbors dalam urutan terbalik agar output konsisten dengan rekursif
        const auto& nbrs = g.neighbors(u);
        for (auto it = nbrs.rbegin(); it != nbrs.rend(); ++it) {
            if (!visited[*it]) st.push(*it);
        }
    }
    return order;
}

int main() {
    Graph g(8);
    g.add_edge_undirected(1, 2);
    g.add_edge_undirected(1, 3);
    g.add_edge_undirected(2, 4);
    g.add_edge_undirected(2, 5);
    g.add_edge_undirected(3, 6);
    g.add_edge_undirected(3, 7);

    auto order = dfs_iter(g, 1);
    std::cout << "DFS order (iterative) from vertex 1:\n  ";
    for (int u : order) std::cout << u << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

DFS order (iterative) from vertex 1:
  1 2 4 5 3 6 7

Baris st.push(src);: inisialisasi stack dengan sumber. Catatan: kita belum tandai visited di sini — penandaan dilakukan saat pop untuk menghindari duplikasi.
Baris if (visited[u]) continue;: cek saat pop. Bila vertex sudah visited (karena dipush beberapa kali sebelum di-pop), skip. Ini berbeda dari BFS yang menandai saat push.
Baris for (auto it = nbrs.rbegin(); ... ): iterasi terbalik sehingga neighbor pertama (mis. 2) di-pop pertama. Tanpa reverse, urutan output akan terbalik dari versi rekursif.
Hasil identik dengan rekursif: 1 2 4 5 3 6 7. Kedua versi DFS memberi urutan yang sama bila traversal neighbor konsisten.

Perbandingan BFS vs DFS #

Aspek	BFS	DFS
Struktur data	Queue (FIFO)	Stack (LIFO) / Call stack
Pola kunjungan	Level-by-level	Mendalam lebih dulu
Memori worst case	O(V) (queue lebar)	O(V) (stack dalam)
Shortest path unweighted	Ya, optimal	Tidak menjamin
Mendeteksi cycle	Ya	Ya, lebih natural
Topological sort	Ya (Kahn’s algorithm)	Ya (post-order)
Bipartite check	Ya	Ya
Connected component	Ya	Ya
Iterasi dalam tree (preorder)	Kurang natural	Natural

Aplikasi BFS: Shortest Path pada Unweighted Graph #

Salah satu aplikasi paling langsung BFS adalah mencari shortest path pada unweighted graph. Mari kita lihat rekonstruksi path:

Kode: Rekonstruksi Path BFS #

cpp
#include <iostream>
#include <vector>
#include <queue>

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

// BFS yang menyimpan parent untuk rekonstruksi path
std::vector<int> bfs_path(const Graph& g, int src, int dst, bool& found) {
    int n = g.v_count();
    std::vector<int> parent(n, -1);
    std::vector<bool> visited(n, false);
    std::queue<int> q;

    visited[src] = true;
    q.push(src);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == dst) { found = true; break; }
        for (int v : g.neighbors(u)) {
            if (!visited[v]) {
                visited[v] = true;
                parent[v] = u;
                q.push(v);
            }
        }
    }

    if (!found) return {};

    std::vector<int> path;
    for (int cur = dst; cur != -1; cur = parent[cur]) path.push_back(cur);
    std::reverse(path.begin(), path.end());
    return path;
}

int main() {
    Graph g(8);
    g.add_edge_undirected(1, 2);
    g.add_edge_undirected(1, 3);
    g.add_edge_undirected(2, 4);
    g.add_edge_undirected(2, 5);
    g.add_edge_undirected(3, 6);
    g.add_edge_undirected(3, 7);
    g.add_edge_undirected(4, 7);   // shortcut

    bool found = false;
    auto path = bfs_path(g, 1, 7, found);

    if (found) {
        std::cout << "Shortest path 1 -> 7:\n  ";
        for (size_t i = 0; i < path.size(); ++i) {
            if (i) std::cout << " -> ";
            std::cout << path[i];
        }
        std::cout << "\nLength = " << path.size() - 1 << '\n';
    } else {
        std::cout << "Tidak ada path\n";
    }
    return 0;
}

Output yang Dihasilkan:

text
Shortest path 1 -> 7:
  1 -> 3 -> 7
Length = 2

Baris std::vector<int> parent(n, -1);: simpan parent setiap vertex. -1 artinya tidak ada parent (vertex belum visited atau merupakan sumber).
Baris parent[v] = u;: saat menemukan neighbor baru, catat vertex yang menemukannya sebagai parent. Ini membangun implicit tree BFS.
Baris if (u == dst) { found = true; break; }: early exit saat destinasi tercapai. BFS menjamin ini terjadi pada level minimum, jadi path yang ditemukan pasti shortest.
Baris for (int cur = dst; cur != -1; cur = parent[cur]) path.push_back(cur);: telusuri parent dari destinasi ke sumber. Path terbalik (dari dst ke src).
Baris std::reverse(path.begin(), path.end());: balik urutan agar path dari src ke dst.
Hasil 1 -> 3 -> 7: jalur langsung melalui vertex 3, panjang 2 edge. Edge shortcut 4-7 tidak membantu karena 1-2-4-7 panjang 3.

Ringkasan #

BFS memakai queue (FIFO), traversal level-by-level, menemukan shortest path pada unweighted graph dalam O(V+E).
DFS memakai stack (LIFO) atau call stack, traversal mendalam lebih dulu.
Tandai visited saat push pada BFS (mencegah duplikasi); saat pop pada DFS iteratif (karena vertex bisa di-push beberapa kali sebelum diproses).
Rekonstruksi path BFS: simpan array parent, telusuri dari destinasi ke sumber, lalu reverse.
Pilih BFS bila butuh shortest path atau kunjungan level. Pilih DFS bila butuh struktur tree-like atau exhaustive exploration.
Hindari DFS rekursif pada graph sangat dalam (V > 10⁵) — gunakan versi iteratif untuk menghindari stack overflow.
Kompleksitas keduanya O(V+E) pada adjacency list, O(V²) pada adjacency matrix.