Adjacency List

Sebagian besar graph di dunia nyata bersifat sparse — jumlah edge jauh lebih kecil dari V². Pada social network dengan 1 miliar pengguna, rata-rata tiap orang punya ~100 koneksi, sehingga E ≈ 10¹¹ padahal V² ≈ 10¹⁸. Memori adjacency matrix akan meledak menjadi triliunan gigabyte. Adjacency list menyelesaikan masalah ini dengan hanya menyimpan edge yang ada: untuk setiap vertex u, kita simpan daftar vertex tujuan yang dapat dicapai dari u. Memori menjadi O(V+E), iterasi neighbor menjadi O(degree(u)), dan inisialisasi hanya O(V). Pada Chapter ini kita akan mengimplementasikan adjacency list dengan tiga variasi (vector, list, set) lalu membandingkan trade-off masing-masing.

Struktur Adjacency List #

Adjacency list adalah array (atau vector) berukuran V di mana adj[u] berisi himpunan vertex tujuan dari u. Pada representasi standar:

• Directed graph: adj[u] berisi v untuk setiap edge (u, v). Memori O(V+E).
• Undirected graph: adj[u] berisi v dan adj[v] berisi u untuk setiap edge {u, v}. Memori O(V+2E) = O(V+E).
• Weighted graph: adj[u] berisi pasangan (v, weight).

Pilihan container untuk adj[u] memengaruhi operasi yang efisien:

vector adalah pilihan default karena paling cepat untuk iterasi (cache-friendly) dan insert. set / unordered_set dipakai bila kita perlu cek/hapus edge sering selain insert.

Implementasi Dasar #

Kode: Adjacency List dengan vector<vector<int>> #

#include <iostream>
#include <vector>

class AdjList {
public:
    explicit AdjList(int n) : adj_(n) {}

    void add_edge_directed(int u, int v) {
        adj_[u].push_back(v);
    }

    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }

    bool has_edge(int u, int v) const {
        for (int x : adj_[u]) if (x == v) return true;
        return false;
    }

    const std::vector<int>& neighbors(int u) const { return adj_[u]; }

    int v_count() const { return adj_.size(); }

    int edge_count() const {
        int total = 0;
        for (const auto& lst : adj_) total += lst.size();
        return total;
    }

    void print() const {
        for (int u = 0; u < v_count(); ++u) {
            std::cout << u << " ->";
            for (int v : adj_[u]) std::cout << " " << v;
            std::cout << '\n';
        }
    }

private:
    std::vector<std::vector<int>> adj_;
};

int main() {
    // Directed graph
    AdjList dg(4);   // A=0, B=1, C=2, D=3
    dg.add_edge_directed(0, 1);
    dg.add_edge_directed(0, 2);
    dg.add_edge_directed(1, 2);
    dg.add_edge_directed(2, 0);
    dg.add_edge_directed(2, 3);

    std::cout << "Directed graph:\n";
    dg.print();
    std::cout << "Total edge = " << dg.edge_count() << '\n';

    // Undirected graph
    AdjList ug(4);
    ug.add_edge_undirected(0, 1);
    ug.add_edge_undirected(0, 2);
    ug.add_edge_undirected(1, 2);
    ug.add_edge_undirected(2, 3);

    std::cout << "\nUndirected graph:\n";
    ug.print();
    std::cout << "Total elemen adjacency list = " << ug.edge_count() << " (2x |E|)\n";

    // Edge check
    std::cout << "\nEdge check (directed):\n";
    std::cout << "  has_edge(0,1) = " << dg.has_edge(0, 1) << '\n';
    std::cout << "  has_edge(1,0) = " << dg.has_edge(1, 0) << '\n';
    std::cout << "  has_edge(2,3) = " << dg.has_edge(2, 3) << '\n';

    return 0;
}

Output yang Dihasilkan:

Directed graph:
0 -> 1 2
1 -> 2
2 -> 0 3
3 ->
Total edge = 5

Undirected graph:
0 -> 1 2
1 -> 0 2
2 -> 0 1 3
3 -> 2
Total elemen adjacency list = 8 (2x |E|)

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

1. Baris adj_(n): konstruktor vector-of-vector dengan n baris kosong. Inisialisasi O(V) — jauh lebih cepat dari matriks O(V²).
2. Baris void add_edge_directed: push back vertex tujuan ke adj_[u]. Amortized O(1) karena vector mengalokasikan kapasitas ekstra.
3. Baris void add_edge_undirected: push back dua kali — ke adj_[u] dan ke adj_[v]. Inilah mengapa undirected graph memakai 2|E| slot memori.
4. Baris bool has_edge(int u, int v): linear scan pada adj_[u] — O(degree(u)). Lebih lambat dari matriks O(1), tetapi acceptable bila operasi ini jarang.
5. Hasil Total edge = 5 untuk directed: jumlah seluruh elemen adjacency list = jumlah edge, karena setiap edge disimpan satu kali.
6. Hasil Total = 8 untuk undirected dengan 4 edge: 4 × 2 = 8 entri. Setiap edge {u,v} disimpan dua kali.

Weighted Adjacency List #

Untuk weighted graph, kita ganti vector<int> menjadi vector<pair<int,int>> atau vector<Edge>.

Kode: Weighted Adjacency List #

#include <iostream>
#include <vector>

struct WeightedEdge {
    int to;
    long long weight;
};

class WeightedAdjList {
public:
    explicit WeightedAdjList(int n) : adj_(n) {}

    void add_edge_directed(int u, int v, long long w) {
        adj_[u].push_back({v, w});
    }

    void add_edge_undirected(int u, int v, long long w) {
        adj_[u].push_back({v, w});
        adj_[v].push_back({u, w});
    }

    const std::vector<WeightedEdge>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }

    void print() const {
        for (int u = 0; u < v_count(); ++u) {
            std::cout << u << " ->";
            for (const auto& e : adj_[u]) {
                std::cout << " (" << e.to << ", w=" << e.weight << ")";
            }
            std::cout << '\n';
        }
    }

private:
    std::vector<std::vector<WeightedEdge>> adj_;
};

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

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

    // Hitung total weight seluruh edge
    long long total_weight = 0;
    for (int u = 0; u < g.v_count(); ++u) {
        for (const auto& e : g.neighbors(u)) total_weight += e.weight;
    }
    std::cout << "\nTotal weight seluruh edge = " << total_weight << '\n';

    // Iterasi neighbor dari vertex 1
    std::cout << "\nNeighbors dari vertex 1:\n";
    for (const auto& e : g.neighbors(1)) {
        std::cout << "  -> " << e.to << " (w=" << e.weight << ")\n";
    }
    return 0;
}

Output yang Dihasilkan:

Weighted adjacency list:
0 -> (1, w=5) (2, w=9)
1 -> (2, w=2) (3, w=12)
2 -> (3, w=7)
3 ->

Total weight seluruh edge = 35

Neighbors dari vertex 1:
  -> 2 (w=2)
  -> 3 (w=12)

1. Baris struct WeightedEdge { int to; long long weight; };: struct eksplisit lebih mudah dibaca daripada pair<int, long long>. Field to jelas menyatakan vertex tujuan; field weight menyatakan bobot edge.
2. Baris adj_[u].push_back({v, w});: aggregate initialization C++17 — {v, w} otomatis dikonversi menjadi WeightedEdge{v, w}.
3. Baris for (const auto& e : g.neighbors(u)): iterasi dengan const auto& menghindari copy struct. Sangat penting bila WeightedEdge berukuran besar atau punya banyak field.
4. Hasil Total weight = 35: 5+9+2+7+12 = 35. Loop menjumlahkan bobot seluruh edge.
5. Iterasi neighbor vertex 1: hanya 2 edge keluar, yaitu ke 2 (bobot 2) dan ke 3 (bobot 12). Iterasi O(degree(1)) = O(2), jauh lebih cepat dari matriks yang harus scan V sel.

Variant: Sorted Adjacency List #

Beberapa algoritma memerlukan neighbor terurut (mis. Dijkstra dengan priority queue). Kita dapat menjaga adj_[u] terurut dengan:

• Insert + sort: push_back lalu std::sort setelah semua insert. Kompleksitas O(E log E).
• std::set: terurut otomatis, tetapi insert O(log deg).
• std::multiset bila membolehkan parallel edges.

Kode: Adjacency List dengan set untuk Multigraph #

#include <iostream>
#include <vector>
#include <set>

class SetAdjList {
public:
    explicit SetAdjList(int n) : adj_(n) {}

    void add_edge(int u, int v) {
        adj_[u].insert(v);
    }

    bool has_edge(int u, int v) const {
        return adj_[u].find(v) != adj_[u].end();
    }

    void remove_edge(int u, int v) {
        adj_[u].erase(v);
    }

    void print() const {
        for (int u = 0; u < (int)adj_.size(); ++u) {
            std::cout << u << " ->";
            for (int v : adj_[u]) std::cout << " " << v;
            std::cout << '\n';
        }
    }

private:
    std::vector<std::set<int>> adj_;
};

int main() {
    SetAdjList g(3);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(0, 1);  // duplikat — diabaikan oleh set
    g.add_edge(1, 2);
    g.add_edge(2, 0);

    std::cout << "Set-based adjacency list (auto-dedup):\n";
    g.print();

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

    g.remove_edge(0, 1);
    std::cout << "\nSetelah remove(0,1):\n";
    g.print();
    return 0;
}

Output yang Dihasilkan:

Set-based adjacency list (auto-dedup):
0 -> 1 2
1 -> 2
2 -> 0

has_edge(0,1) = 1
has_edge(1,0) = 0

Setelah remove(0,1):
0 -> 2
1 -> 2
2 -> 0

1. Baris std::vector<std::set<int>> adj_;: vector of std::set. Setiap adj_[u] adalah std::set<int> yang otomatis terurut dan unik.
2. Baris adj_[u].insert(v);: insert ke set — O(log degree(u)). Bila v sudah ada, insert diabaikan (deduplikasi otomatis).
3. Baris bool has_edge(int u, int v) const: set::find adalah O(log degree(u)) — lebih cepat dari linear scan pada vector untuk degree besar.
4. Baris g.remove_edge(0, 1);: set::erase adalah O(log degree(u)). Pada vector, kita butuh std::find + erase yang O(degree(u)).
5. Hasil 0 -> 1 2 (bukan 1 2 1): set otomatis membuang duplikat. Cocok untuk simple graph di mana edge duplikat tidak diinginkan.

Kompleksitas dan Pemilihan Container #

Tabel berikut merangkum kompleksitas operasi pada berbagai container:

Batasan dan Tips #

• Iterasi neighbor: lebih cepat dari matrix karena hanya melewati vertex yang benar-benar adjacent. Penting untuk BFS/DFS.
• Cache locality: vector menempati memori kontigu → cache-friendly. std::set dan unordered_set memakai pointer yang tersebar → lebih banyak cache miss.
• Penambahan edge dinamis: vector dengan push_back sangat cepat. Bila Anda sering menghapus edge selama runtime, set lebih bersih.
• Memori edge duplikat (undirected): setiap edge disimpan 2×. Bila ini menjadi masalah, simpan adj[u] berisi v untuk v > u saja — tetapi ini menyulitkan iterasi.

Ringkasan #

• Adjacency list menyimpan daftar tetangga per vertex — adj[u] berisi vertex tujuan dari u.
• Memori O(V+E) untuk directed, O(V+2E) = O(V+E) untuk undirected.
• Iterasi neighbor O(degree(u)) — keunggulan utama, jauh lebih cepat dari matrix O(V) pada sparse graph.
• Cek edge O(degree(u)) pada vector — lebih lambat dari matriks O(1).
• vector<vector<int>> adalah pilihan default; set / unordered_set untuk operasi hapus/cek edge dinamis.
• Weighted adjacency list memakai vector<pair<int,int>> atau vector<Edge{to, weight}>.
• Ideal untuk graph berukuran besar bersifat sparse — BFS, DFS, Dijkstra semuanya efisien pada representasi ini.