Beberapa algoritma tidak peduli dengan struktur neighbor — yang penting adalah daftar edge itu sendiri. Kruskal’s algorithm untuk minimum spanning tree, misalnya, hanya perlu mengurutkan edge berdasarkan bobot lalu memproses satu per satu. Untuk kasus seperti ini, edge list menjadi representasi paling natural: simpan seluruh edge sebagai array of struct {u, v, weight}, lalu iterasi. Memori sangat hemat O(E), sorting mudah, dan paralelisasi trivial. Pada Chapter ini kita akan mengimplementasikan edge list, melihat kapan ia unggul dibanding adjacency list/matrix, lalu mempraktikkan penggunaannya pada algoritma Kruskal preview.

Struktur Edge List #

Edge list adalah array (atau vector) berisi seluruh edge graph. Setiap elemen menyimpan:

  • u — vertex sumber (atau salah satu endpoint untuk undirected).
  • v — vertex tujuan (atau endpoint lainnya).
  • w — bobot edge (opsional, untuk weighted graph).

Pada C++, pilihan implementasi:

  1. vector<pair<int,int>> — untuk unweighted graph.
  2. vector<tuple<int,int,long long>> — untuk weighted graph.
  3. vector<Edge> dengan struct Edge { int u, v; long long w; } — paling deskriptif.

Keunggulan utama edge list:

  • Memori minimum: O(E), tidak menyimpan vertex yang tidak punya edge.
  • Sortir edge trivial: langsung std::sort(edges.begin(), edges.end(), cmp).
  • Iterasi edge trivial: satu loop sederhana for (auto& e : edges).
  • Cocok untuk algoritma edge-centric: Kruskal, Bellman-Ford, Borůvka.

Implementasi Dasar #

Kode: Edge List untuk Weighted Graph #

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

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

    // Operator < untuk sorting default ascending by weight
    bool operator<(const Edge& o) const {
        if (w != o.w) return w < o.w;
        if (u != o.u) return u < o.u;
        return v < o.v;
    }
};

class EdgeList {
public:
    void add_edge(int u, int v, long long w) {
        edges_.push_back({u, v, w});
    }

    void sort_by_weight() {
        std::sort(edges_.begin(), edges_.end());
    }

    const std::vector<Edge>& edges() const { return edges_; }
    int edge_count() const { return edges_.size(); }

    // Hitung jumlah vertex unik
    int vertex_count() const {
        int max_v = -1;
        for (const auto& e : edges_) {
            max_v = std::max(max_v, std::max(e.u, e.v));
        }
        return max_v + 1;  // asumsi vertex 0..max_v
    }

    void print() const {
        std::cout << "Edges (u, v, w):\n";
        for (const auto& e : edges_) {
            std::cout << "  (" << e.u << ", " << e.v << ", " << e.w << ")\n";
        }
    }

private:
    std::vector<Edge> edges_;
};

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

    std::cout << "Sebelum sort:\n";
    g.print();
    std::cout << "Vertex count = " << g.vertex_count() << '\n';
    std::cout << "Edge count = " << g.edge_count() << '\n';

    g.sort_by_weight();
    std::cout << "\nSetelah sort by weight ascending:\n";
    g.print();

    return 0;
}

Output yang Dihasilkan:

text 
Sebelum sort:
Edges (u, v, w):
  (0, 1, 5)
  (0, 2, 9)
  (1, 2, 2)
  (2, 3, 7)
  (1, 3, 12)
Vertex count = 4
Edge count = 5

Setelah sort by weight ascending:
Edges (u, v, w):
  (1, 2, 2)
  (0, 1, 5)
  (2, 3, 7)
  (0, 2, 9)
  (1, 3, 12)
  1. Baris struct Edge { int u, v; long long w; bool operator<(...) ... };: struct dengan operator< agar bisa di-sort langsung tanpa komparator eksternal. Tie-breaker u lalu v memastikan urutan deterministik untuk edge dengan bobot sama.
  2. Baris void add_edge(int u, int v, long long w): push_back({u, v, w}) memanfaatkan aggregate initialization. Amortized O(1).
  3. Baris void sort_by_weight(): std::sort memakai operator< yang sudah didefinisikan — O(E log E).
  4. Baris int vertex_count() const: cari max(u, v) maksimum lalu tambahkan 1. Catatan: asumsi vertex diberi ID 0..max_v. Vertex tanpa edge tidak terhitung — sesuai dengan filosofi edge list yang hanya peduli pada edge.
  5. Hasil sort: edge dengan weight terkecil (2: edge 1→2) muncul pertama, weight terbesar (12: edge 1→3) terakhir. Persis yang dibutuhkan Kruskal.

Aplikasi: Kruskal’s Algorithm Preview #

Kruskal adalah algoritma minimum spanning tree (MST) yang memproses edge dari yang terkecil. Karena fokusnya adalah edge, edge list menjadi representasi ideal.

Kode: Kruskal Preview dengan Edge List #

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

struct Edge {
    int u, v;
    long long w;
    bool operator<(const Edge& o) const {
        if (w != o.w) return w < o.w;
        return std::make_pair(u, v) < std::make_pair(o.u, o.v);
    }
};

// Disjoint Set Union (Union-Find) untuk deteksi cycle
class DSU {
public:
    explicit DSU(int n) : parent_(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent_[i] = i;
    }
    int find(int x) {
        if (parent_[x] != x) parent_[x] = find(parent_[x]);  // path compression
        return parent_[x];
    }
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;  // sudah satu set, edge akan membentuk cycle
        if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        return true;
    }
private:
    std::vector<int> parent_, rank_;
};

int main() {
    // Graph weighted undirected
    std::vector<Edge> edges = {
        {0, 1, 5}, {0, 2, 9}, {1, 2, 2}, {2, 3, 7}, {1, 3, 12}
    };
    const int V = 4;

    // Kruskal: sort edge ascending by weight, tambahkan edge bila tidak membentuk cycle
    std::sort(edges.begin(), edges.end());

    DSU dsu(V);
    long long total_cost = 0;
    int edges_used = 0;
    std::vector<Edge> mst;

    std::cout << "MST edges:\n";
    for (const auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {  // bila berhasil unite (tidak cycle)
            mst.push_back(e);
            total_cost += e.w;
            edges_used++;
            std::cout << "  (" << e.u << ", " << e.v << ", w=" << e.w << ")\n";
            if (edges_used == V - 1) break;  // MST lengkap
        }
    }

    std::cout << "\nTotal MST cost = " << total_cost << '\n';
    std::cout << "Edges in MST  = " << edges_used << " (V-1 = " << V - 1 << ")\n";
    return 0;
}

Output yang Dihasilkan:

text 
MST edges:
  (1, 2, w=2)
  (0, 1, w=5)
  (2, 3, w=7)

Total MST cost = 14
Edges in MST  = 3 (V-1 = 3)
  1. Baris class DSU: struktur data Union-Find untuk mengecek apakah dua vertex sudah berada dalam satu connected component. Detail lengkap pada Chapter Disjoint Set Union.
  2. Baris std::sort(edges.begin(), edges.end());: sort edge ascending by weight menggunakan operator< yang sudah didefinisikan. Kruskal memerlukan edge terurut.
  3. Baris if (dsu.unite(e.u, e.v)): coba gabungkan komponen e.u dan e.v. Bila berhasil (return true), edge ditambahkan ke MST. Bila gagal (return false), kedua vertex sudah satu komponen — edge ini akan membentuk cycle → skip.
  4. Baris if (edges_used == V - 1) break;: MST selalu punya tepat V - 1 edge. Bila sudah mencapai angka ini, hentikan iterasi lebih awal — optimasi kecil.
  5. Hasil Total MST cost = 14: edge 1-2 (2) + 0-1 (5) + 2-3 (7) = 14. Ini adalah minimum spanning tree — bobot minimum untuk menghubungkan seluruh 4 vertex tanpa cycle.
  6. Edge 0-2 (9) di-skip: saat dipertimbangkan, vertex 0 dan 2 sudah terhubung melalui 0-1-2, jadi edge langsung akan membentuk cycle.

Operasi pada Edge List #

Tabel kompleksitas operasi pada edge list:

OperasiKompleksitasCatatan
Tambah edgeO(1) amortizedpush_back
Hapus edgeO(E)cari lalu hapus
Cek edge (u,v)O(E)scan linear
Iterasi semua edgeO(E)satu loop
Sort edgeO(E log E)std::sort
InisialisasiO(1)hanya membuat vector kosong
MemoriO(E)paling hemat

Konversi Antar Representasi #

Edge list sering menjadi format input (mis. soal kompetisi memberi E baris edge). Kita perlu konversi ke adjacency list/matrix sebelum menjalankan algoritma traversal.

Kode: Konversi Edge List ke Adjacency List #

cpp 
#include <iostream>
#include <vector>

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

int main() {
    std::vector<Edge> edges = {
        {0, 1, 5}, {0, 2, 9}, {1, 2, 2}, {2, 3, 7}, {1, 3, 12}
    };
    const int V = 4;

    // Konversi ke weighted adjacency list (undirected)
    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});   // undirected: dua arah
    }

    std::cout << "Adjacency list hasil konversi:\n";
    for (int u = 0; u < V; ++u) {
        std::cout << u << " ->";
        for (auto [v, w] : adj[u]) {
            std::cout << " (" << v << ", w=" << w << ")";
        }
        std::cout << '\n';
    }

    // Konversi ke adjacency matrix (undirected weighted)
    const long long INF = 1e15;
    std::vector<std::vector<long long>> mat(V, std::vector<long long>(V, INF));
    for (int i = 0; i < V; ++i) mat[i][i] = 0;
    for (const auto& e : edges) {
        mat[e.u][e.v] = e.w;
        mat[e.v][e.u] = e.w;   // undirected
    }

    std::cout << "\nAdjacency matrix hasil konversi:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (mat[i][j] == INF) std::cout << "INF ";
            else                   std::cout << mat[i][j] << "   ";
        }
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Adjacency list hasil konversi:
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)

Adjacency matrix hasil konversi:
0    5    9    INF
5    0    2    12
9    2    0    7
INF  12   7    0
  1. Baris adj[e.u].push_back({e.v, e.w}); dan adj[e.v].push_back({e.u, e.w});: untuk konversi ke undirected adjacency list, tambahkan edge ke kedua arah.
  2. Baris mat[e.u][e.v] = e.w; dan mat[e.v][e.u] = e.w;: untuk undirected matrix, matriks simetris. Set kedua sel ke bobot yang sama.
  3. Hasil matriks simetris: mat[0][1] = 5 = mat[1][0]. Ini adalah property dari undirected graph yang direpresentasikan sebagai adjacency matrix.
  4. Kompleksitas konversi: O(E) untuk adjacency list, O(V² + E) untuk matriks (karena inisialisasi matriks).

Kapan Memakai Edge List #

  • Input graph dari soal kompetisi: biasanya diberikan sebagai daftar edge — gunakan edge list untuk membaca, lalu konversi bila perlu.
  • Kruskal / Borůvka: algoritma MST yang fokus pada edge.
  • Bellman-Ford: iterasi seluruh edge V-1 kali.
  • Kadane-style edge processing: misalnya mencari edge dengan bobot tertentu (max, min).
  • Statistik graph: distribusi bobot, histogram degree.

Ringkasan #

  • Edge list adalah array berisi seluruh edge — vector<Edge{u, v, w}>.
  • Memori O(E) — paling hemat dari semua representasi.
  • Sort edge trivial dengan std::sort — Kruskal, Bellman-Ford.
  • Cek edge O(E) — lemah dibanding matrix O(1).
  • Iterasi neighbor O(E) — lemah dibanding adjacency list O(degree).
  • Ideal untuk algoritma edge-centric (Kruskal, Bellman-Ford) dan sebagai format input.
  • Konversi edge list → adjacency list = O(E); edge list → adjacency matrix = O(V² + E).