Cycle Detection

Deteksi cycle adalah salah satu masalah graph paling fundamental. Pada dependency graph modul software, cycle berarti circular dependency yang menyebabkan build gagal. Pada deadlock detection sistem operasi, cycle pada wait-for graph menandakan deadlock. Pada currency arbitrage, negative cycle adalah peluang arbitrage tak terbatas. Algoritma deteksi cycle berbeda untuk undirected dan directed graph — yang pertama cukup melacak parent, yang kedua memerlukan pewarnaan tiga warna. Pada Chapter ini kita akan mengimplementasikan keduanya, memahami mengapa directed graph lebih sulit, lalu mengaplikasikannya pada soal topological sort prerequisite.

Definisi Cycle #

Cycle adalah path (v₀, v₁, v₂, ..., vₖ) di mana:

v₀ == vₖ (kembali ke titik awal).
Semua edge (vᵢ, vᵢ₊₁) ada di graph.
Semua vertex antara v₁, ..., vₖ₋₁ unik.

Pada undirected graph, cycle sederhana minimum adalah triangle (3 vertex, 3 edge). Self-loop (u, u) juga dihitung sebagai cycle. Pada directed graph, cycle seperti A → B → C → A (panah satu arah) berbeda dari cycle pada undirected graph.

Cycle Detection pada Undirected Graph #

Aturan #

Pada undirected graph, DFS alami menemukan cycle: bila kita menemukan neighbor yang sudah visited dan bukan parent, maka ada cycle. Karena undirected graph menyimpan setiap edge dua kali (sebagai (u,v) dan (v,u)), kita harus mengabaikan parent saat iterasi neighbor.

flowchart LR A --- B B --- C A --- C C --- D

Pada graph di atas, DFS dari A: kunjungi A → kunjungi B → kunjungi C. Saat di C, kita menemukan neighbor A — A sudah visited dan bukan parent dari C (parent dari C adalah B). Inilah indikasi cycle: A → B → C → A.

Kode: Cycle Detection pada Undirected Graph #

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_;
};

// DFS rekursif: return true bila ada cycle
bool dfs_cycle(const Graph& g, int u, int parent,
               std::vector<bool>& visited) {
    visited[u] = true;
    for (int v : g.neighbors(u)) {
        if (!visited[v]) {
            if (dfs_cycle(g, v, u, visited)) return true;
        } else if (v != parent) {
            // neighbor visited dan BUKAN parent -> cycle ditemukan
            return true;
        }
    }
    return false;
}

bool has_cycle_undirected(const Graph& g) {
    int n = g.v_count();
    std::vector<bool> visited(n, false);
    for (int s = 0; s < n; ++s) {
        if (!visited[s]) {
            if (dfs_cycle(g, s, -1, visited)) return true;
        }
    }
    return false;
}

int main() {
    // Test 1: graph dengan triangle A-B-C-A
    Graph g1(4);
    g1.add_edge_undirected(0, 1);   // A-B
    g1.add_edge_undirected(1, 2);   // B-C
    g1.add_edge_undirected(0, 2);   // A-C (membentuk cycle)
    g1.add_edge_undirected(2, 3);   // C-D
    std::cout << "Graph 1 (ada cycle A-B-C): "
              << (has_cycle_undirected(g1) ? "ADA cycle" : "TIDAK ada cycle") << '\n';

    // Test 2: tree (tidak ada cycle)
    Graph g2(5);
    g2.add_edge_undirected(0, 1);
    g2.add_edge_undirected(0, 2);
    g2.add_edge_undirected(1, 3);
    g2.add_edge_undirected(1, 4);
    std::cout << "Graph 2 (tree 5 vertex): "
              << (has_cycle_undirected(g2) ? "ADA cycle" : "TIDAK ada cycle") << '\n';

    // Test 3: self-loop
    Graph g3(3);
    g3.add_edge_undirected(0, 1);
    g3.add_edge_undirected(2, 2);   // self-loop
    std::cout << "Graph 3 (self-loop di vertex 2): "
              << (has_cycle_undirected(g3) ? "ADA cycle" : "TIDAK ada cycle") << '\n';

    return 0;
}

Output yang Dihasilkan:

text
Graph 1 (ada cycle A-B-C): ADA cycle
Graph 2 (tree 5 vertex): TIDAK ada cycle
Graph 3 (self-loop di vertex 2): ADA cycle

Baris bool dfs_cycle(const Graph& g, int u, int parent, ...): parameter parent menyimpan vertex yang memanggil DFS saat ini. Tanpa ini, DFS akan menandai edge (u, parent) sebagai cycle (karena parent sudah visited).
Baris if (!visited[v]): rekursi ke neighbor yang belum dikunjungi — kasus normal.
Baris else if (v != parent): neighbor sudah visited tetapi bukan parent — inilah indikasi cycle. Edge (u, v) menghubungkan dua vertex yang sudah dalam pohon DFS saat ini, membentuk cycle.
Baris dfs_cycle(g, s, -1, visited): root DFS tidak punya parent — kirim -1 sebagai sentinel.
Hasil Graph 1: triangle A-B-C terdeteksi sebagai cycle. DFS dari A → B → C → kembali ke A (sudah visited, bukan parent dari C yang adalah B) → cycle terdeteksi.
Hasil Graph 2: tree tidak punya cycle. Setiap edge hanya menghubungkan parent-child, jadi v != parent tidak pernah true.
Hasil Graph 3: self-loop (2, 2) — saat DFS di vertex 2, neighbor 2 sama dengan diri sendiri. Karena 2 != parent (parent bukan 2), kondisi terpenuhi → cycle. Catatan: implementasi ini menangkap self-loop, tetapi beberapa definisi menganggap self-loop sebagai “loop” terpisah dari cycle.

Cycle Detection pada Directed Graph #

Aturan: Tiga Warna (White/Gray/Black) #

Directed graph lebih sulit. Mengapa? Pada undirected, “neighbor visited yang bukan parent” selalu cycle. Pada directed, neighbor visited bisa jadi:

Ancestor dalam stack DFS saat ini → cycle.
Vertex di sub-DFS tree berbeda yang sudah selesai diproses → bukan cycle (hanya forward/cross edge).

Solusinya: pakai pewarnaan tiga warna:

WHITE (0) — belum dikunjungi.
GRAY (1) — sedang dalam stack DFS (anterior sedang diproses).
BLACK (2) — selesai diproses (seluruh subtree sudah dieksplorasi).

Saat DFS menemukan neighbor v dari u:

v == WHITE → rekursi.
v == GRAY → back edge → cycle ditemukan (v adalah ancestor u di stack).
v == BLACK → cross/forward edge → bukan cycle, skip.

flowchart LR A --> B B --> C C --> A B --> D

Pada directed graph di atas: DFS dari A: A (GRAY) → B (GRAY) → C (GRAY) → neighbor A (GRAY) → back edge → cycle!

Kode: Cycle Detection pada Directed Graph #

cpp
#include <iostream>
#include <vector>

enum Color { WHITE = 0, GRAY = 1, BLACK = 2 };

class DirectedGraph {
public:
    explicit DirectedGraph(int n) : adj_(n) {}
    void add_edge(int u, int v) { adj_[u].push_back(v); }
    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_;
};

bool dfs_cycle_directed(const DirectedGraph& g, int u, std::vector<int>& color) {
    color[u] = GRAY;
    for (int v : g.neighbors(u)) {
        if (color[v] == WHITE) {
            if (dfs_cycle_directed(g, v, color)) return true;
        } else if (color[v] == GRAY) {
            // Back edge: v adalah ancestor yang masih dalam stack
            return true;
        }
        // color[v] == BLACK: skip (cross/forward edge, bukan cycle)
    }
    color[u] = BLACK;
    return false;
}

bool has_cycle_directed(const DirectedGraph& g) {
    int n = g.v_count();
    std::vector<int> color(n, WHITE);
    for (int s = 0; s < n; ++s) {
        if (color[s] == WHITE) {
            if (dfs_cycle_directed(g, s, color)) return true;
        }
    }
    return false;
}

int main() {
    // Test 1: directed cycle A->B->C->A
    DirectedGraph g1(4);
    g1.add_edge(0, 1);
    g1.add_edge(1, 2);
    g1.add_edge(2, 0);  // back to A -> cycle
    g1.add_edge(1, 3);
    std::cout << "Graph 1 (directed cycle A->B->C->A): "
              << (has_cycle_directed(g1) ? "ADA cycle" : "TIDAK ada cycle") << '\n';

    // Test 2: DAG (Directed Acyclic Graph)
    DirectedGraph g2(5);
    g2.add_edge(0, 1);
    g2.add_edge(0, 2);
    g2.add_edge(1, 3);
    g2.add_edge(2, 3);
    g2.add_edge(3, 4);
    std::cout << "Graph 2 (DAG 5 vertex): "
              << (has_cycle_directed(g2) ? "ADA cycle" : "TIDAK ada cycle") << '\n';

    // Test 3: cross edge (bukan cycle)
    DirectedGraph g3(4);
    g3.add_edge(0, 1);
    g3.add_edge(0, 2);
    g3.add_edge(1, 3);
    g3.add_edge(2, 3);  // cross edge (3 sudah BLACK saat ini diproses dari 2)
    std::cout << "Graph 3 (cross edge, no cycle): "
              << (has_cycle_directed(g3) ? "ADA cycle" : "TIDAK ada cycle") << '\n';

    return 0;
}

Output yang Dihasilkan:

text
Graph 1 (directed cycle A->B->C->A): ADA cycle
Graph 2 (DAG 5 vertex): TIDAK ada cycle
Graph 3 (cross edge, no cycle): TIDAK ada cycle

Baris enum Color { WHITE = 0, GRAY = 1, BLACK = 2 };: enum untuk tiga warna. WHITE = belum diproses, GRAY = dalam stack DFS, BLACK = selesai.
Baris color[u] = GRAY;: tandai vertex sebagai “sedang diproses” saat pertama masuk.
Baris if (color[v] == WHITE): rekursi ke neighbor yang belum dikunjungi — kasus normal.
Baris else if (color[v] == GRAY): back edge — v sedang dalam stack DFS (ancestor dari u). Edge u → v menutup cycle.
Baris // color[v] == BLACK: skip: cross edge atau forward edge — v sudah selesai diproses (di subtree lain), tidak membentuk cycle.
Baris color[u] = BLACK;: setelah seluruh neighbor selesai, tandai u sebagai “selesai” — tidak lagi dalam stack DFS.
Hasil Graph 1: directed cycle A→B→C→A terdeteksi. Saat DFS di C, neighbor A berwarna GRAY (sedang dalam stack) → back edge → cycle.
Hasil Graph 3 (cross edge): DFS dari A → B → 3 (BLACK, selesai), lalu A → C → 3 (saat DFS ke C, vertex 3 sudah BLACK karena selesai diproses dari B). Kondisi color[3] == GRAY tidak terpenuhi → bukan cycle. Benar: cross edge C→3 bukan cycle.

Aplikasi: Topological Sort Prerequisite #

Topological sort adalah pengurutan vertex pada DAG sehingga setiap edge u → v menjamin u muncul sebelum v dalam urutan. Prerequisite: graph harus berupa DAG. Bila ada cycle, topological sort tidak terdefinisi.

Kode: Topological Sort dengan Deteksi Cycle #

cpp
#include <iostream>
#include <vector>

enum Color { WHITE = 0, GRAY = 1, BLACK = 2 };

class DirectedGraph {
public:
    explicit DirectedGraph(int n) : adj_(n) {}
    void add_edge(int u, int v) { adj_[u].push_back(v); }
    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_;
};

// DFS post-order: tambahkan vertex ke stack setelah seluruh neighbor selesai
bool dfs_topo(const DirectedGraph& g, int u, std::vector<int>& color, std::vector<int>& order) {
    color[u] = GRAY;
    for (int v : g.neighbors(u)) {
        if (color[v] == WHITE) {
            if (!dfs_topo(g, v, color, order)) return false;
        } else if (color[v] == GRAY) {
            // cycle ditemukan -> topological sort tidak mungkin
            return false;
        }
    }
    color[u] = BLACK;
    order.push_back(u);   // post-order
    return true;
}

std::vector<int> topo_sort(const DirectedGraph& g, bool& ok) {
    int n = g.v_count();
    std::vector<int> color(n, WHITE), order;
    ok = true;
    for (int s = 0; s < n; ++s) {
        if (color[s] == WHITE) {
            if (!dfs_topo(g, s, color, order)) { ok = false; return {}; }
        }
    }
    std::reverse(order.begin(), order.end());
    return order;
}

int main() {
    // 6 mata kuliah dengan prerequisite
    // 0: Calulus, 1: Linear Algebra, 2: Discrete Math,
    // 3: Algorithm (perlu 2), 4: ML (perlu 1 dan 3), 5: Thesis (perlu 4)
    DirectedGraph g(6);
    g.add_edge(1, 4);   // Linear -> ML
    g.add_edge(3, 4);   // Algorithm -> ML
    g.add_edge(2, 3);   // Discrete -> Algorithm
    g.add_edge(4, 5);   // ML -> Thesis

    bool ok;
    auto order = topo_sort(g, ok);
    if (!ok) {
        std::cout << "Cycle terdeteksi, topological sort tidak mungkin\n";
    } else {
        std::cout << "Topological order:\n  ";
        for (int u : order) std::cout << u << ' ';
        std::cout << '\n';

        // Verifikasi: untuk setiap edge u->v, u muncul sebelum v
        bool valid = true;
        std::vector<int> pos(order.size());
        for (size_t i = 0; i < order.size(); ++i) pos[order[i]] = i;
        for (int u = 0; u < g.v_count(); ++u) {
            for (int v : g.neighbors(u)) {
                if (pos[u] > pos[v]) { valid = false; break; }
            }
        }
        std::cout << "Verifikasi valid: " << (valid ? "YA" : "TIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Topological order:
  2 3 1 4 5 0
Verifikasi valid: YA

Baris order.push_back(u); dalam dfs_topo: post-order — vertex ditambahkan setelah seluruh neighbor selesai. Ini memastikan u muncul setelah semua vertex yang bergantung padanya dalam list (yang nanti akan di-reverse).
Baris std::reverse(order.begin(), order.end());: balik urutan post-order menjadi topological order. Vertex tanpa dependen akan di-push terakhir → muncul pertama setelah reverse.
Baris if (pos[u] > pos[v]) { valid = false; break; }: verifikasi topological order — untuk setiap edge u → v, posisi u harus lebih kecil dari v. Bila ada pelanggaran, urutan salah.
Hasil 2 3 1 4 5 0: vertex 2 (Discrete Math) muncul pertama karena tidak punya prerequisite. Vertex 3 (Algorithm, butuh Discrete) mengikuti. Vertex 1 (Linear Algebra, tidak punya prerequisite) juga bisa lebih awal. Vertex 5 (Thesis) muncul setelah 4 (ML). Vertex 0 (Calculus, terisolasi tanpa edge) muncul terakhir karena DFS dari s = 0 dijalankan lebih dulu, lalu di-reverse ke posisi akhir.
Catatan: bila terdapat cycle, fungsi topo_sort akan return ok = false dan main akan mencetak pesan error.

Kompleksitas dan Perbandingan #

Tabel perbandingan algoritma cycle detection:

Aspek	Undirected	Directed
Struktur data tambahan	`parent` saja	array `color[3]`
Kompleksitas	O(V+E)	O(V+E)
Memori tambahan	O(1) per call	O(V) untuk color array
Self-loop detection	Ya (via parent != vertex)	Ya (via GRAY)
Back edge detection	`visited[v] && v != parent`	`color[v] == GRAY`
Topological sort support	Tidak (undirected)	Ya

Ringkasan #

Undirected: DFS dengan parent tracking. Neighbor visited yang bukan parent → cycle.
Directed: DFS dengan tiga warna (WHITE/GRAY/BLACK). Back edge (GRAY neighbor) → cycle. Cross/forward edge (BLACK) → bukan cycle.
Kompleksitas keduanya O(V+E) pada adjacency list.
Self-loop terdeteksi pada kedua algoritma — undirected karena v != parent (parent tidak sama dengan vertex saat ini), directed karena vertex saat ini berwarna GRAY saat melihat dirinya sendiri.
Topological sort = post-order DFS yang di-reverse; prerequisite graph harus DAG (tidak ada cycle).
Variasi: Kahn’s algorithm (BFS dengan in-degree) untuk topological sort alternatif tanpa rekursi.
Aplikasi: dependency resolution, deadlock detection, deadlock avoidance, scheduling, currency arbitrage.