Dalam sebuah jaringan komputer, server mana yang bila gagal akan memutus komunikasi antar segmen? Dalam jalan raya, jembatan mana yang bila runtuh membuat dua kota terisolasi? Pertanyaan-pertanyaan ini memetakan ke persoalan Articulation Points (titik kritis) dan Bridges (jembatan kritis) pada graph. Articulation point adalah node yang bila dihapus meningkatkan jumlah komponen terhubung. Bridge adalah edge yang bila dihapus menyebabkan hal serupa. Algoritma klasik menggunakan DFS dengan dua array kunci — disc[] (discovery time) dan low[] (lowlink) — yang sama seperti pada Tarjan SCC. Pada Chapter ini kita akan membedah mekanisme lowlink, mengimplementasikan dalam C++, dan melihat kapan sebuah edge adalah bridge dan kapan sebuah node adalah articulation point.

Aturan: Definisi Formal #

Pada graph tak berarah terhubung G = (V, E):

  • Articulation Point (cut vertex): node u sehingga menghapus u (dan semua edge terkait) meningkatkan jumlah connected component.
  • Bridge (cut edge): edge e sehingga menghapus e meningkatkan jumlah connected component.
  • Articulation point dan bridge hanya bermakna pada graph tak berarah. Untuk graph berarah, konsep ekuivalen adalah strong bridge dan strong articulation point — jauh lebih kompleks (varian algoritma lowlink).

Inisialisasi DFS dari setiap node belum dikunjungi. Untuk setiap node u:

  • disc[u] = discovery time (urutan kunjungan, incrementing counter).
  • low[u] = discovery time minimum yang dapat dicapai dari subtree u melalui paling banyak satu back edge (edge ke ancestor di DFS tree).

Selama DFS dari u, untuk setiap tetangga v:

  1. v belum dikunjungi → tree edge. Rekursi ke v, lalu update low[u] = min(low[u], low[v]).
  2. v sudah dikunjungi dan v != parent[u] → back edge. Update low[u] = min(low[u], disc[v]).

Kondisi Articulation Point #

Node u adalah articulation point jika:

  • Root dengan ≥ 2 anak tree (children dalam DFS tree), ATAU
  • Non-root dengan anak v sehingga low[v] >= disc[u] — subtree v tidak punya back edge ke ancestor u.

Kondisi Bridge #

Edge (u, v) adalah bridge jika dan hanya jika low[v] > disc[u] (subtree v tidak punya back edge ke u atau ancestor-nya; bahkan tidak ke u sendiri). Perhatikan > bukan >= — bila low[v] == disc[u], ada edge balik ke u sendiri, sehingga u masih bisa diakses tanpa edge (u,v).

cpp 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

class Graph {
    int n;
    std::vector<std::vector<int>> adj;
    int timer = 0;
    std::vector<int> disc, low;
    std::vector<bool> visited;
    std::set<int> articulation_pts;
    std::vector<std::pair<int,int>> bridges;

public:
    explicit Graph(int n) : n(n), adj(n), disc(n, -1), low(n, -1), visited(n, false) {}
    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void find_ap_bridges() {
        for (int u = 0; u < n; ++u) {
            if (!visited[u]) {
                dfs(u, -1);
            }
        }
    }

    void print_results() {
        std::cout << "Articulation Points: ";
        if (articulation_pts.empty()) std::cout << "(tidak ada)";
        for (int x : articulation_pts) std::cout << x << ' ';
        std::cout << '\n';

        std::cout << "Bridges: ";
        if (bridges.empty()) std::cout << "(tidak ada)";
        for (auto [u, v] : bridges) std::cout << "(" << u << "-" << v << ") ";
        std::cout << '\n';
    }

private:
    void dfs(int u, int parent) {
        visited[u] = true;
        disc[u] = low[u] = timer++;
        int children = 0;
        bool is_articulation = false;

        for (int v : adj[u]) {
            if (!visited[v]) {
                children++;
                dfs(v, u);
                low[u] = std::min(low[u], low[v]);

                // Articulation point (non-root)
                if (parent != -1 && low[v] >= disc[u]) {
                    is_articulation = true;
                }
                // Bridge
                if (low[v] > disc[u]) {
                    bridges.push_back({u, v});
                }
            } else if (v != parent) {
                // Back edge
                low[u] = std::min(low[u], disc[v]);
            }
        }

        // Root dengan >= 2 children = articulation point
        if (parent == -1 && children >= 2) {
            is_articulation = true;
        }
        if (is_articulation) articulation_pts.insert(u);
    }
};

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

    g.find_ap_bridges();
    g.print_results();

    std::cout << "\nPenjelasan:\n";
    std::cout << "  AP 0: menghapus 0 memutus 6 dari graph (0 satu-satunya tetangga 6)\n";
    std::cout << "  AP 1: menghapus 1 memutus {0,6} dari {2,3,4,5}\n";
    std::cout << "  AP 2: menghapus 2 memutus {0,1,6} dari {3,4,5}\n";
    std::cout << "  Bridge (0,6): satu-satunya edge ke 6\n";
    std::cout << "  Bridge (0,1): 0 hanya terhubung ke 1 dan 6; hapus ini isolasi {0,6}\n";
    std::cout << "  Bridge (1,2): hapus ini memutus {0,1,6} dari {2,3,4,5}\n";
    std::cout << "  Edge (2,3),(2,4),(3,5),(4,5) bukan bridge karena cycle 2-3-5-4-2\n";
    return 0;
}

Output yang Dihasilkan:

text 
Articulation Points: 0 1 2 
Bridges: (1-2) (0-1) (0-6) 

Penjelasan:
  AP 0: menghapus 0 memutus 6 dari graph (0 satu-satunya tetangga 6)
  AP 1: menghapus 1 memutus {0,6} dari {2,3,4,5}
  AP 2: menghapus 2 memutus {0,1,6} dari {3,4,5}
  Bridge (0,6): satu-satunya edge ke 6
  Bridge (0,1): 0 hanya terhubung ke 1 dan 6; hapus ini isolasi {0,6}
  Bridge (1,2): hapus ini memutus {0,1,6} dari {2,3,4,5}
  Edge (2,3),(2,4),(3,5),(4,5) bukan bridge karena cycle 2-3-5-4-2

Bedah Kode Baris-per-Baris #

  1. std::vector<int> disc, low;: dua array kunci. disc[u] = discovery time, low[u] = lowlink. Inisialisasi -1 = belum dikunjungi.
  2. std::set<int> articulation_pts: gunakan set untuk menghindari duplikasi (node bisa dideteksi beberapa kali dari anak yang berbeda).
  3. std::vector<std::pair<int,int>> bridges: list bridge. Edge unik karena DFS tree edge unik.
  4. disc[u] = low[u] = timer++: set discovery time dan lowlink awal. Lowlink awalnya = discovery (belum ada back edge).
  5. int children = 0; bool is_articulation = false;: hitung anak tree dan status articulation. Untuk root, anak ≥ 2 = AP; untuk non-root, periksa kondisi low[v] >= disc[u].
  6. if (!visited[v]) → tree edge: rekursi ke v, lalu perbarui low[u] dengan low[v]. Subtree v mungkin memiliki back edge yang menjangkau ancestor u — infonya diteruskan ke u.
  7. if (parent != -1 && low[v] >= disc[u]): kondisi AP non-root. low[v] >= disc[u] berarti subtree v tidak punya back edge ke ancestor u — hapus u akan memutus v dari graph.
  8. if (low[v] > disc[u]): kondisi bridge. Strict > (bukan >=): bila low[v] == disc[u], ada edge balik ke u sendiri, jadi hapus edge (u,v) masih meninggalkan jalur alternatif.
  9. else if (v != parent) → back edge: v sudah dikunjungi tapi bukan parent → edge balik ke ancestor u. Update low[u] = min(low[u], disc[v]) — pakai disc[v] bukan low[v] (penting untuk kebenaran).
  10. if (parent == -1 && children >= 2) is_articulation = true;: kondisi root. Root dengan ≥ 2 anak tree pasti AP karena hapus root → dua subtree tidak terhubung.
  11. Hasil: 3 AP {0, 1, 2} dan 3 bridge {(0,6), (0,1), (1,2)}. Edge-edge dalam cycle 2-3-5-4-2 tidak terdeteksi sebagai bridge karena ada jalur alternatif.

Trace untuk Node 2 (Non-root) #

DFS dari 0: disc[0] = low[0] = 0. Anak: 1 (tree edge). DFS dari 1: disc[1] = low[1] = 1. Anak: 2 (tree edge). DFS dari 2: disc[2] = low[2] = 2. Anak: 3, 4 (tree edges).

  • DFS dari 3: disc[3] = low[3] = 3. Tetangga: 2 (parent, skip), 5 (tree edge).
    • DFS dari 5: disc[5] = low[5] = 4. Tetangga: 3 (parent, skip), 4 (tree edge).
      • DFS dari 4: disc[4] = low[4] = 5. Tetangga: 2 (visited, ≠ parent 5 → back edge). Update low[4] = min(5, disc[2]=2) = 2. Tetangga: 5 (parent, skip). Selesai, return.
    • Kembali ke 5: low[5] = min(4, low[4]=2) = 2. Kondisi AP non-root: low[4] = 2 >= disc[5] = 4? Tidak. Kondisi bridge: low[4] = 2 > disc[5] = 4? Tidak. Selesai.
  • Kembali ke 3: low[3] = min(3, low[5]=2) = 2. AP: low[5]=2 >= disc[3]=3? Tidak. Bridge: low[5]=2 > disc[3]=3? Tidak.
  • DFS dari 4: sudah visited, skip di iterasi 2.
  • Kembali ke 2: setelah kedua anak diproses, low[2] = min(2, low[3]=2, low[4]=2) = 2. Anak 3: AP non-root? low[3]=2 >= disc[2]=2? Ya → AP. Anak 4: AP non-root? low[4]=2 >= disc[2]=2? Ya → AP (duplikat, set menyatukan). Bridge: low[3]=2 > disc[2]=2? Tidak. low[4]=2 > disc[2]=2? Tidak. Edge (2,3) dan (2,4) bukan bridge.

✓ Sesuai hasil: 2 adalah AP, tetapi edge (2,3) dan (2,4) bukan bridge.

Kompleksitas #

AspekNilaiCatatan
WaktuO(V + E)DFS tunggal, setiap edge diperiksa konstan.
RuangO(V + E)Adj list + array disc, low, stack.
Multi-graphBekerjaPerlu hati-hati: edge paralel selalu bukan bridge.
Self-loopTidak masuk hitungan bridgev != parent skip.

Variasi dan Penerapan #

  • Biconnected components: kelompok edge di mana setiap dua edge berbagi cycle. Bridge = edge yang membentuk BCC sendirian.
  • 2-edge-connected: graph tanpa bridge. Tambah edge minimum untuk membuat 2-edge-connected.
  • 2-vertex-connected: graph tanpa articulation point.
  • Network reliability: AP dan bridge = titik/edge kritis yang gagalnya memutus layanan.
  • Topological analysis: pada graph terhubung, AP dan bridge mengidentifikasi weak points.

Aplikasi Nyata #

  • Network design: identifikasi server (AP) dan kabel (bridge) kritis.
  • Transportation: jembatan jalan raya yang runtuh mengisolasi daerah.
  • Circuit analysis: AP dan bridge pada PCB graph = komponen kritis.
  • Social network: AP = user yang menjadi penghubung dua komunitas.
  • Biological networks: AP = protein yang tanpanya jaringan rusak.

Ringkasan #

  • Articulation Point: node yang bila dihapus meningkatkan jumlah komponen.
  • Bridge: edge yang bila dihapus meningkatkan jumlah komponen.
  • Algoritma: DFS dengan disc[] dan low[] (lowlink).
  • AP non-root: low[v] >= disc[u] untuk suatu anak v. AP root: ≥ 2 anak tree.
  • Bridge: low[v] > disc[u] (strict >).
  • Kompleksitas O(V + E) waktu dan ruang.
  • Aplikasi: network reliability, transport, social network analysis.

Bab berikutnya akan membahas topik terakhir Section ini: Max-Flow dan Min-Cut — persoalan aliran maksimum pada jaringan dengan kapasitas, dan teorema max-flow min-cut yang menghubungkan dua konsep fundamental.