Graph Representation

Kita telah mempelajari tiga representasi graph: adjacency matrix (matriks V×V), adjacency list (vector of vector per vertex), dan edge list (array edge). Ketiganya menyimpan graph yang sama persis — perbedaan hanya pada efisiensi operasi. Pada Chapter ini kita akan menyatukan ketiga representasi dalam satu program, membandingkan performa mereka pada operasi-operasi umum, dan memilih representasi yang tepat untuk kasus berbeda. Pemilihan representasi yang tepat di awal sering kali menjadi penentu apakah solusi kompetisi atau sistem produksi dapat berjalan dalam batas waktu.

Tabel Perbandingan Menyeluruh #

Tabel berikut merangkum kompleksitas ketiga representasi pada operasi-operasi standar:

Operasi	Adjacency Matrix	Adjacency List	Edge List
Inisialisasi	O(V²)	O(V)	O(1)
Memori	O(V²)	O(V+E)	O(E)
Cek edge `(u,v)`	O(1)	O(deg(u))	O(E)
Tambah edge	O(1)	O(1) amortized	O(1) amortized
Hapus edge	O(1)	O(deg(u))	O(E)
Iterasi neighbor `u`	O(V)	O(deg(u))	O(E)
In-degree `v`	O(V)	O(V+E)	O(E)
Out-degree `u`	O(V)	O(1) (simpan size)	O(E)
Sort edge by weight	O(V² log V²)	O(E log E)	O(E log E)

Beberapa implikasi langsung dari tabel:

Matrix unggul pada: cek edge O(1), hapus edge O(1), algoritma Floyd-Warshall.
List unggul pada: iterasi neighbor (BFS, DFS, Dijkstra), memori untuk sparse graph.
Edge list unggul pada: Kruskal, Bellman-Ford, menghitung statistik edge, format input.

Ketiga Representasi dalam Satu Program #

Kode: Implementasi Ketiganya dan Pengujian Performa #

cpp
#include <iostream>
#include <vector>
#include <chrono>
#include <random>

// ===== Adjacency Matrix =====
class AdjMatrix {
public:
    explicit AdjMatrix(int n) : n_(n), mat_(n, std::vector<char>(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 count_neighbors(int u) const {
        int c = 0;
        for (int v = 0; v < n_; ++v) if (mat_[u][v]) c++;
        return c;
    }
private:
    int n_;
    std::vector<std::vector<char>> mat_;
};

// ===== Adjacency List =====
class AdjList {
public:
    explicit AdjList(int n) : adj_(n) {}
    void add_edge(int u, int v) { adj_[u].push_back(v); }
    bool has_edge(int u, int v) const {
        for (int x : adj_[u]) if (x == v) return true;
        return false;
    }
    int count_neighbors(int u) const { return adj_[u].size(); }
private:
    std::vector<std::vector<int>> adj_;
};

// ===== Edge List =====
struct Edge { int u, v; };

class EdgeList {
public:
    void add_edge(int u, int v) { edges_.push_back({u, v}); }
    bool has_edge(int u, int v) const {
        for (const auto& e : edges_) if (e.u == u && e.v == v) return true;
        return false;
    }
    int count_neighbors(int target) const {
        int c = 0;
        for (const auto& e : edges_) if (e.u == target) c++;
        return c;
    }
    size_t size() const { return edges_.size(); }
private:
    std::vector<Edge> edges_;
};

int main() {
    // Graph: V=5, 10 directed edges
    const int V = 5;
    std::vector<std::pair<int,int>> edges = {
        {0,1}, {0,2}, {1,2}, {1,3}, {2,3},
        {3,4}, {4,0}, {4,1}, {2,4}, {0,3}
    };

    AdjMatrix m(V);
    AdjList   l(V);
    EdgeList  e;

    for (auto [u, v] : edges) {
        m.add_edge(u, v);
        l.add_edge(u, v);
        e.add_edge(u, v);
    }

    // === Verifikasi konsistensi ===
    std::cout << "Verifikasi konsistensi:\n";
    std::cout << "  has_edge(0,1) matrix=" << m.has_edge(0,1)
              << " list=" << l.has_edge(0,1)
              << " edgelist=" << e.has_edge(0,1) << '\n';
    std::cout << "  has_edge(1,0) matrix=" << m.has_edge(1,0)
              << " list=" << l.has_edge(1,0)
              << " edgelist=" << e.has_edge(1,0) << '\n';
    std::cout << "  neighbors(0)  matrix=" << m.count_neighbors(0)
              << " list=" << l.count_neighbors(0)
              << " edgelist=" << e.count_neighbors(0) << '\n';
    std::cout << "  total edges   edgelist=" << e.size() << '\n';

    return 0;
}

Output yang Dihasilkan:

text
Verifikasi konsistensi:
  has_edge(0,1) matrix=1 list=1 edgelist=1
  has_edge(1,0) matrix=0 list=0 edgelist=0
  neighbors(0)  matrix=3 list=3 edgelist=3
  total edges   edgelist=10

Baris std::vector<std::vector<char>> mat_; pada AdjMatrix: pakai char (1 byte) bukan int (4 byte) untuk unweighted matrix — menghemat memori 4×. Untuk weighted, pakai long long.
Baris bool has_edge(int u, int v) const pada AdjList: linear scan pada adj_[u]. Pada graf dense, ini menjadi O(V) — sama dengan matrix. Pada graf sparse, ini O(small) — jauh lebih cepat.
Baris int count_neighbors(int target) pada EdgeList: scan seluruh edge — O(E). Inilah kelemahan utama edge list untuk operasi vertex-centric.
Hasil ketiganya konsisten: ketiga representasi menyimpan graph yang sama, sehingga has_edge, count_neighbors memberi jawaban identik. Perbedaan hanya pada kecepatan.
Catatan total edges edgelist=10: edge list menyimpan 10 edge — sesuai jumlah input. Matrix akan menyimpan 25 sel (5×5), list akan menyimpan 10 entri terbagi di 5 vector.

Microbenchmark: Operasi pada Graph Besar #

Mari kita ukur waktu eksekusi operasi has_edge dan iterasi neighbor pada graph dengan V=1000, E=5000 (sparse).

Kode: Benchmark Operasi #

cpp
#include <iostream>
#include <vector>
#include <chrono>
#include <random>

class AdjMatrix {
public:
    explicit AdjMatrix(int n) : n_(n), mat_(n, std::vector<char>(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 count_all_neighbors() const {
        int total = 0;
        for (int u = 0; u < n_; ++u)
            for (int v = 0; v < n_; ++v)
                if (mat_[u][v]) total++;
        return total;
    }
private:
    int n_;
    std::vector<std::vector<char>> mat_;
};

class AdjList {
public:
    explicit AdjList(int n) : adj_(n) {}
    void add_edge(int u, int v) { adj_[u].push_back(v); }
    bool has_edge(int u, int v) const {
        for (int x : adj_[u]) if (x == v) return true;
        return false;
    }
    int count_all_neighbors() const {
        int total = 0;
        for (const auto& lst : adj_) total += lst.size();
        return total;
    }
private:
    std::vector<std::vector<int>> adj_;
};

int main() {
    const int V = 1000, E = 5000;

    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(0, V - 1);

    // Build identical graphs in both representations
    AdjMatrix m(V);
    AdjList   l(V);
    int added = 0;
    while (added < E) {
        int u = dist(rng), v = dist(rng);
        if (u == v || m.has_edge(u, v)) continue;
        m.add_edge(u, v);
        l.add_edge(u, v);
        added++;
    }

    // Benchmark has_edge
    auto t1 = std::chrono::high_resolution_clock::now();
    volatile int dummy = 0;
    for (int i = 0; i < 100000; ++i) {
        int u = dist(rng), v = dist(rng);
        dummy += m.has_edge(u, v);
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        int u = dist(rng), v = dist(rng);
        dummy += l.has_edge(u, v);
    }
    auto t3 = std::chrono::high_resolution_clock::now();

    auto us_m = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    auto us_l = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();

    std::cout << "Benchmark has_edge (100k queries, V=" << V << " E=" << E << "):\n";
    std::cout << "  Adjacency Matrix = " << us_m << " us\n";
    std::cout << "  Adjacency List   = " << us_l << " us\n";

    // Benchmark iterasi neighbor (sum degrees)
    auto t4 = std::chrono::high_resolution_clock::now();
    int total_m = m.count_all_neighbors();
    auto t5 = std::chrono::high_resolution_clock::now();
    int total_l = l.count_all_neighbors();
    auto t6 = std::chrono::high_resolution_clock::now();

    auto us_m_iter = std::chrono::duration_cast<std::chrono::microseconds>(t5 - t4).count();
    auto us_l_iter = std::chrono::duration_cast<std::chrono::microseconds>(t6 - t5).count();

    std::cout << "\nBenchmark iterasi neighbor (count_all_neighbors):\n";
    std::cout << "  Adjacency Matrix = " << us_m_iter << " us (total=" << total_m << ")\n";
    std::cout << "  Adjacency List   = " << us_l_iter << " us (total=" << total_l << ")\n";
    std::cout << "\n(dummy=" << dummy << ")\n";
    return 0;
}

Output yang Dihasilkan:

text
Benchmark has_edge (100k queries, V=1000 E=5000):
  Adjacency Matrix = 926 us
  Adjacency List   = 2544 us

Benchmark iterasi neighbor (count_all_neighbors):
  Adjacency Matrix = 290 us (total=5000)
  Adjacency List   = 0 us (total=5000)

(dummy=940)

Baris volatile int dummy = 0;: mencegah compiler menghapus loop yang dianggap “hasil tidak terpakai”. volatile memaksa compiler membaca/menulis ulang dari memori.
Baris auto us_m = ... duration_cast<std::chrono::microseconds> ...: mengukur waktu dengan presisi mikrodetik. std::chrono adalah API standar C++11+.
Hasil has_edge: matrix unggul ~3× (926 µs vs 2544 µs) karena akses langsung sel. List memerlukan linear scan rata-rata E/V = 5 elemen per query.
Hasil iterasi neighbor: list hampir instan (0 us karena operasi 5000 terlalu cepat untuk mikrodetik) karena hanya melewati edge yang ada. Matrix harus scan V² = 1 juta sel — 290 us.
Catatan dummy=940: 100k query random, sekitar 0.94% menemukan edge (karena E/V² ≈ 0.005). Hasil dummy berbeda tiap run karena seed generator berbeda — ini wajar.

Panduan Pemilihan #

Berikut adalah panduan praktis berdasarkan karakteristik masalah:

Karakteristik masalah	Rekomendasi
`V` kecil (≤ 2000), graph dense	Adjacency Matrix
`V` besar (≥ 10⁵), graph sparse	Adjacency List
Cek edge sering (`O(1)` mutlak)	Adjacency Matrix
BFS / DFS / Dijkstra (iterasi neighbor)	Adjacency List
Kruskal / Bellman-Ford	Edge List
Floyd-Warshall, transitive closure	Adjacency Matrix
Format input soal kompetisi	Edge List → konversi sesuai algoritma
Memori sangat terbatas	Edge List

Kode: Pola Input Kompetisi Standar #

cpp
#include <iostream>
#include <vector>

struct Edge { int u, v; long long w; };

int main() {
    int V, E;
    std::cin >> V >> E;

    // Baca sebagai edge list (format umum soal)
    std::vector<Edge> edges(E);
    for (auto& e : edges) std::cin >> e.u >> e.v >> e.w;

    std::cout << "Dibaca: V=" << V << ", E=" << E << '\n';

    // Konversi ke adjacency list (undirected weighted) untuk Dijkstra/BFS
    std::vector<std::vector<std::pair<int,long long>>> adj(V);
    for (const auto& e : edges) {
        adj[e.u].push_back({e.v, e.w});
        adj[e.v].push_back({e.u, e.w});
    }

    // Verifikasi: cetak adjacency list
    for (int u = 0; u < std::min(V, 5); ++u) {
        std::cout << u << " ->";
        for (auto [v, w] : adj[u]) std::cout << " (" << v << ",w=" << w << ")";
        std::cout << '\n';
    }
    return 0;
}

Input yang Diuji (stdin):

Output yang Dihasilkan:

text
Dibaca: V=4, E=5
0 -> (1,w=5) (2,w=9)
1 -> (0,w=5) (2,w=2) (3,w=12)
2 -> (0,w=9) (1,w=2) (3,w=7)
3 -> (2,w=7) (1,w=12)

Baris std::cin >> V >> E;: format input standar kompetisi — V (jumlah vertex) dan E (jumlah edge) diberikan di baris pertama.
Baris std::vector<Edge> edges(E);: pre-allocate vector berukuran E. Hindari push_back berulang bila E diketahui dari awal — lebih cepat dan deterministik.
Baris for (auto& e : edges) std::cin >> e.u >> e.v >> e.w;: baca seluruh edge dalam satu loop. Referensi auto& menghindari copy struct.
Konversi ke adjacency list: tambahkan edge dua kali untuk undirected. Kompleksitas konversi O(E).
Hasil verifikasi: edge 1-2 (w=2) direpresentasikan dua kali — 1 -> 2 dan 2 -> 1. Sesuai dengan sifat undirected graph.

Kasus Khusus #

Beberapa skenario menuntut representasi hybrid:

Graph dengan banyak query edge tapi juga traversal: adjacency list + cache hasil cek edge. Atau adjacency matrix untuk subgraph yang sering di-query.
Dynamic graph (edge sering ditambah/hapus): set / unordered_set per vertex.
Graph dengan edge berlabel: vector<vector<struct Edge{to, weight, label, capacity}>>.
Tree: tree adalah graph dengan V-1 edge. Adjacency list selalu optimal (sparse).

Ringkasan #

Tiga representasi: adjacency matrix O(V²), adjacency list O(V+E), edge list O(E).
Matrix unggul pada cek edge O(1), hapus edge O(1), Floyd-Warshall.
List unggul pada iterasi neighbor O(deg), BFS/DFS/Dijkstra, sparse graph.
Edge list unggul pada memori minimum, sort edge, Kruskal/Bellman-Ford.
Benchmark V=1000, E=5000: matrix ~3× lebih cepat untuk has_edge, list nyaris instan untuk iterasi neighbor vs matrix 290 us.
Pola input kompetisi: baca sebagai edge list → konversi ke adjacency list untuk algoritma traversal.
Default aman untuk kompetisi: vector<vector<pair<int,long long>>> (weighted adjacency list).