Bila kita memetakan graph ke dalam memori, pertanyaan pertama yang muncul: bagaimana cara cepat menjawab “apakah ada edge dari u ke v?” Adjacency matrix menjawab pertanyaan ini dalam O(1) — sebuah matriks V×V di mana sel (u,v) bernilai 1 (ada edge) atau 0 (tidak ada). Keunggulan ini dibayar dengan memori O(V²), yang menjadi masalah saat graph memiliki jutaan vertex tetapi sedikit edge. Pada Chapter ini kita akan mengimplementasikan adjacency matrix untuk directed, undirected, maupun weighted graph, lalu menganalisis kapan pendekatan ini layak dipakai.

Struktur Adjacency Matrix #

Adjacency matrix A untuk graph G = (V, E) didefinisikan sebagai matriks V×V dengan:

  • A[u][v] = 1 bila terdapat edge (u, v) pada directed graph, atau {u, v} pada undirected graph.
  • A[u][v] = 0 bila tidak ada edge.

Untuk weighted graph, A[u][v] menyimpan bobot edge; tidak ada edge dilambangkan dengan ∞ (misal 1e9 atau 1e15).

Beberapa property langsung dari representasi ini:

  • Undirected graph: matriks simetris — A[u][v] == A[v][u].
  • Directed graph: matriks tidak perlu simetris.
  • Self-loop: A[u][u] = 1 (atau bobot loop pada weighted).
  • In-degree v: jumlah kolom v yang bernilai 1.
  • Out-degree u: jumlah baris u yang bernilai 1.

Implementasi Dasar #

Kode: Adjacency Matrix untuk Directed Graph #

cpp 
#include <iostream>
#include <vector>

class AdjMatrix {
public:
    explicit AdjMatrix(int n) : n_(n), mat_(n, std::vector<int>(n, 0)) {}

    void add_edge(int u, int v) { mat_[u][v] = 1; }

    bool has_edge(int u, int v) const { return mat_[u][v] == 1; }

    int out_degree(int u) const {
        int deg = 0;
        for (int v = 0; v < n_; ++v) if (mat_[u][v]) deg++;
        return deg;
    }

    int in_degree(int v) const {
        int deg = 0;
        for (int u = 0; u < n_; ++u) if (mat_[u][v]) deg++;
        return deg;
    }

    int v_count() const { return n_; }

    void print() const {
        std::cout << "    ";
        for (int j = 0; j < n_; ++j) std::cout << j << ' ';
        std::cout << '\n';
        for (int i = 0; i < n_; ++i) {
            std::cout << i << " : ";
            for (int j = 0; j < n_; ++j) std::cout << mat_[i][j] << ' ';
            std::cout << '\n';
        }
    }

private:
    int n_;
    std::vector<std::vector<int>> mat_;
};

int main() {
    // Directed graph: 0->1, 0->2, 1->2, 2->0
    AdjMatrix g(3);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 2);
    g.add_edge(2, 0);

    std::cout << "Adjacency matrix (directed):\n";
    g.print();

    std::cout << "\nEdge check:\n";
    std::cout << "  has_edge(0,1) = " << g.has_edge(0, 1) << '\n';
    std::cout << "  has_edge(1,0) = " << g.has_edge(1, 0) << '\n';
    std::cout << "  has_edge(2,0) = " << g.has_edge(2, 0) << '\n';

    std::cout << "\nDegree:\n";
    for (int u = 0; u < g.v_count(); ++u) {
        std::cout << "  vertex " << u
                  << " | in=" << g.in_degree(u)
                  << " out=" << g.out_degree(u) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Adjacency matrix (directed):
    0 1 2
0 : 0 1 1
1 : 0 0 1
2 : 1 0 0

Edge check:
  has_edge(0,1) = 1
  has_edge(1,0) = 0
  has_edge(2,0) = 1

Degree:
  vertex 0 | in=1 out=2
  vertex 1 | in=1 out=1
  vertex 2 | in=2 out=1
  1. Baris mat_(n, std::vector<int>(n, 0)): inisialisasi matriks n×n berisi 0. Inisialisasi ini membutuhkan O(V²) waktu dan memori.
  2. Baris void add_edge(int u, int v): untuk directed graph, hanya set mat_[u][v] = 1. Untuk undirected, tambahkan mat_[v][u] = 1 juga.
  3. Baris bool has_edge(int u, int v): akses langsung sel matriks — O(1). Inilah keunggulan utama adjacency matrix.
  4. Baris int out_degree(int u): loop sepanjang baris u — O(V). Pada adjacency list ini bisa O(1) bila kita simpan degree terpisah.
  5. Baris int in_degree(int v): loop sepanjang kolom v — O(V). Pada adjacency list kita perlu loop seluruh adjacency list untuk menghitung in-degree, O(V+E).
  6. Hasil vertex 2 | in=2 out=1: ada 2 edge masuk ke vertex 2 (dari 0 dan 1) dan 1 edge keluar (ke 0).

Weighted Adjacency Matrix #

Untuk weighted graph, ganti tipe elemen dari int (0/1) menjadi long long yang menyimpan bobot. Konvensi:

  • mat[u][v] = w — edge dengan bobot w.
  • mat[u][v] = INF — tidak ada edge (gunakan INF besar agar penjumlahan tetap aman, misal 1e15).
  • mat[u][u] = 0 — jarak ke diri sendiri = 0.

Kode: Weighted Adjacency Matrix #

cpp 
#include <iostream>
#include <vector>

class WeightedMatrix {
public:
    static constexpr long long INF = 1000000000000000LL;  // 1e15

    explicit WeightedMatrix(int n)
        : n_(n), mat_(n, std::vector<long long>(n, INF)) {
        for (int i = 0; i < n; ++i) mat_[i][i] = 0;
    }

    void add_edge(int u, int v, long long w) { mat_[u][v] = w; }

    long long weight(int u, int v) const { return mat_[u][v]; }

    bool has_edge(int u, int v) const { return u != v && mat_[u][v] != INF; }

    void print() const {
        std::cout << "       ";
        for (int j = 0; j < n_; ++j) std::cout << j << "    ";
        std::cout << '\n';
        for (int i = 0; i < n_; ++i) {
            std::cout << "  " << i << " : ";
            for (int j = 0; j < n_; ++j) {
                if (mat_[i][j] == INF) std::cout << "INF  ";
                else if (mat_[i][j] < 10) std::cout << mat_[i][j] << "    ";
                else std::cout << mat_[i][j] << "   ";
            }
            std::cout << '\n';
        }
    }

private:
    int n_;
    std::vector<std::vector<long long>> mat_;
};

int main() {
    WeightedMatrix g(4);
    g.add_edge(0, 1, 5);
    g.add_edge(1, 2, 2);
    g.add_edge(0, 2, 9);
    g.add_edge(2, 3, 7);
    g.add_edge(1, 3, 12);

    std::cout << "Weighted adjacency matrix:\n";
    g.print();

    auto print_w = [&](int u, int v) {
        long long w = g.weight(u, v);
        if (w == WeightedMatrix::INF) std::cout << "INF";
        else                          std::cout << w;
    };
    std::cout << "\nEdge check:\n";
    std::cout << "  weight(0,1) = "; print_w(0, 1); std::cout << '\n';
    std::cout << "  weight(1,0) = "; print_w(1, 0); std::cout << " (INF = no edge)\n";
    std::cout << "  weight(0,0) = "; print_w(0, 0); std::cout << " (self = 0)\n";
    return 0;
}

Output yang Dihasilkan:

text 
Weighted adjacency matrix:
       0    1    2    3
  0 : 0    5    9    INF
  1 : INF  0    2    12
  2 : INF  INF  0    7
  3 : INF  INF  INF  0

Edge check:
  weight(0,1) = 5
  weight(1,0) = INF (INF = no edge)
  weight(0,0) = 0 (self = 0)
  1. Baris static constexpr long long INF = 1e15;: konstanta INF dibuat static member agar dapat diakses dari luar kelas sebagai WeightedMatrix::INF. Nilai 1e15 cukup besar sehingga INF + 1e9 tidak overflow long long (maksimum ~9.2×10¹⁸).
  2. Baris mat_(n, std::vector<long long>(n, INF)): inisialisasi seluruh sel ke INF, lalu set diagonal ke 0. Pada weighted graph, jarak ke diri sendiri selalu 0 (bukan 1, bukan INF).
  3. Baris bool has_edge(int u, int v) const { return u != v && mat_[u][v] != INF; }: definisi “ada edge” mengecualikan diagonal — mat[u][u] = 0 bukan edge, melainkan jarak ke diri sendiri.
  4. Baris if (mat_[i][j] == INF) std::cout << "INF ";: cetak literal INF agar matriks mudah dibaca manusia. Tanpa ini, angka 1e15 akan tampil sebagai 1000000000000000 yang memenuhi layar.
  5. Lambda print_w: helper untuk mencetak weight atau INF bergantian — menghindari duplikasi logika di tiga baris berikutnya.
  6. Hasil weight(1,0) = INF: tidak ada edge dari 1 ke 0; matriks tidak simetris karena graph directed.

Kompleksitas dan Kapan Dipakai #

Tabel berikut merangkum operasi-operasi penting pada adjacency matrix:

OperasiKompleksitasCatatan
InisialisasiO(V²)alokasi V×V sel
Cek edge (u,v)O(1)akses sel tunggal
Tambah edgeO(1)satu assignment
Hapus edgeO(1)satu assignment
Iterasi neighbor uO(V)scan sepanjang baris
Out-degree uO(V)scan baris
In-degree vO(V)scan kolom
MemoriO(V²)terlepas dari jumlah edge

Batasan Praktis #

Memori O(V²) menjadi penghalang utama:

  • V = 1000 → 1 juta sel → ~4 MB (int) atau ~8 MB (long long). Masih oke.
  • V = 10⁴ → 100 juta sel → ~800 MB. Hampir tidak feasible untuk kompetisi.
  • V = 10⁵ → 10 milyar sel → ~80 GB. Tidak mungkin.

Sebagai pedoman praktis: adjacency matrix aman dipakai hingga V ≤ 2000. Di atas itu, sebaiknya beralih ke adjacency list.

Ringkasan #

  • Adjacency matrix adalah matriks V×V dengan A[u][v] = 1 (ada edge) atau 0 (tidak ada).
  • Untuk weighted graph, A[u][v] menyimpan bobot; tidak ada edge = INF; A[u][u] = 0.
  • Operasi cek edge O(1) — keunggulan utama adjacency matrix.
  • Operasi iterasi neighbor O(V) — kekurangan utama; adjacency list O(degree).
  • Memori O(V²) — cocok untuk dense graph kecil-sedang (V ≤ 2000), tidak feasible untuk sparse graph besar.
  • Pilihan natural untuk algoritma Floyd-Warshall, transitive closure, dan matrix-based graph algorithms.