Terminologi Graph

Graph memiliki kosa kata teknis yang ringkas namun wajib dikuasai. Tanpa istilah seperti degree, path, cycle, dan connected component, kita tidak akan bisa membaca pseudocode algoritma graph maupun menganalisis kompleksitasnya. Pada Chapter ini kita akan memetakan seluruh terminologi inti dalam satu tempat, lengkap dengan contoh visual dan kode C++ yang menghitung property-property tersebut. Setelah membaca Chapter ini, kita diharapkan dapat membaca deskripsi algoritma apapun di Wikipedia maupun buku CLRS tanpa terhenti oleh jargon.

Degree dan Variannya #

Degree sebuah vertex adalah jumlah edge yang incident ke vertex tersebut. Pada graph berarah, degree dipecah menjadi dua:

• In-degree — jumlah edge yang masuk ke vertex (panah menuju vertex).
• Out-degree — jumlah edge yang keluar dari vertex (panah meninggalkan vertex).

Pada graph tak berarah, degree = jumlah edge yang terhubung ke vertex. Sebuah loop (edge dari vertex ke dirinya sendiri) menyumbang 2 pada degree (masuk dan keluar dari vertex yang sama).

Pada directed graph di atas:

• A: out-degree 2 (ke B, ke C), in-degree 1 (dari C)
• B: out-degree 1 (ke C), in-degree 1 (dari A)
• C: out-degree 1 (ke A), in-degree 2 (dari A, dari B)

Kode: Menghitung In-degree dan Out-degree #

#include <iostream>
#include <vector>

int main() {
    // Directed graph dengan 3 vertex (A=0, B=1, C=2)
    const int V = 3;
    std::vector<std::vector<int>> adj = {
        {1, 2},   // A -> B, A -> C
        {2},      // B -> C
        {0},      // C -> A
    };

    std::vector<int> indeg(V, 0), outdeg(V, 0);

    for (int u = 0; u < V; ++u) {
        outdeg[u] = adj[u].size();              // out-degree = jumlah edge keluar
        for (int v : adj[u]) {
            indeg[v]++;                          // hitung edge yang masuk ke v
        }
    }

    std::cout << "Vertex | In-degree | Out-degree | Total\n";
    std::cout << "-------+-----------+------------+------\n";
    for (int u = 0; u < V; ++u) {
        std::cout << "  " << (char)('A' + u) << "   |"
                  << "     " << indeg[u] << "     |"
                  << "      " << outdeg[u] << "     |"
                  << "   " << indeg[u] + outdeg[u] << '\n';
    }

    // Pada directed graph, total in-degree == total out-degree == |E|
    int total_in = 0, total_out = 0;
    for (int u = 0; u < V; ++u) { total_in += indeg[u]; total_out += outdeg[u]; }
    std::cout << "\nTotal in-degree  = " << total_in << '\n';
    std::cout << "Total out-degree = " << total_out << '\n';
    std::cout << "Jumlah edge |E| = " << total_in << '\n';
    return 0;
}

Output yang Dihasilkan:

Vertex | In-degree | Out-degree | Total
-------+-----------+------------+------
  A   |     1     |      2     |   3
  B   |     1     |      1     |   2
  C   |     2     |      1     |   3

Total in-degree  = 4
Total out-degree = 4
Jumlah edge |E| = 4

1. Baris std::vector<std::vector<int>> adj: representasi adjacency list sederhana. adj[u] berisi daftar vertex tujuan dari u. Ini akan dibahas tuntas pada Chapter Adjacency List.
2. Baris outdeg[u] = adj[u].size();: pada directed graph, out-degree adalah jumlah elemen pada adjacency list vertex u.
3. Baris for (int v : adj[u]) indeg[v]++;: untuk setiap edge u → v, increment in-degree v. Satu loop O(V+E) menghitung kedua degree sekaligus.
4. Hasil Total in-degree = Total out-degree = 4: ini adalah handshaking lemma versi directed. Setiap edge menyumbang 1 ke total in-degree dan 1 ke total out-degree, sehingga keduanya selalu sama dan sama dengan |E|.

Path, Walk, Trail, dan Cycle #

Empat istilah ini sering tertukar. Tabel berikut menjelaskan perbedaannya secara presisi:

Beberapa konsekuensi penting:

• Path tidak boleh mengunjungi vertex yang sama dua kali.
• Cycle adalah path tertutup — vertex awal = vertex akhir, semua vertex antara unik, semua edge unik.
• Panjang path = jumlah edge (bukan jumlah vertex).

Kode: Mendeteksi Cycle pada Path #

Sebelum algoritma cycle detection lengkap, mari kita lihat pemeriksaan sederhana: apakah path yang diberikan pengguna merupakan cycle?

#include <iostream>
#include <vector>
#include <unordered_set>

bool is_cycle_path(const std::vector<int>& path) {
    if (path.size() < 3) return false;            // cycle minimal 3 vertex
    if (path.front() != path.back()) return false; // harus kembali ke awal

    std::unordered_set<int> seen(path.begin(), path.end() - 1);
    // path[0..size-2] harus unik; path[size-1] == path[0] diizinkan
    return seen.size() == path.size() - 1;
}

int main() {
    std::vector<std::vector<int>> tests = {
        {0, 1, 2, 0},    // cycle 0-1-2-0
        {0, 1, 2, 3},    // path biasa, bukan cycle
        {0, 1, 0},       // cycle 3 vertex (triangle-ish)
        {0, 1, 2, 1, 0}, // edge diulang -> bukan cycle sederhana
        {0, 0},          // loop self, terlalu pendek
    };

    for (const auto& p : tests) {
        std::cout << "Path ";
        for (int x : p) std::cout << x << ' ';
        std::cout << "-> " << (is_cycle_path(p) ? "cycle" : "bukan cycle") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

Path 0 1 2 0 -> cycle
Path 0 1 2 3 -> bukan cycle
Path 0 1 0 -> cycle
Path 0 1 2 1 0 -> bukan cycle
Path 0 0 -> bukan cycle

1. Baris if (path.size() < 3) return false;: cycle sederhana minimum melibatkan 3 vertex (triangle). Self-loop dengan 2 vertex (0, 0) dianggap loop, bukan cycle dalam definisi simple graph.
2. Baris if (path.front() != path.back()) return false;: cycle harus kembali ke titik awal. Tanpa syarat ini, path biasa akan lolos.
3. Baris std::unordered_set<int> seen(path.begin(), path.end() - 1);: masukkan semua vertex kecuali vertex terakhir ke himpunan. Vertex terakhir (path.back()) sengaja diabaikan karena memang sama dengan path.front().
4. Baris return seen.size() == path.size() - 1;: jika semua vertex path[0..size-2] unik, himpunan punya ukuran size-1. Bila ada duplikat, ukuran himpunan lebih kecil → bukan cycle.
5. Hasil {0, 1, 2, 1, 0} ditolak: vertex 1 diulang di tengah path — itu trail, bukan cycle.

Connected, Component, dan Subgraph #

Pada graph tak berarah, dua vertex u dan v disebut connected bila terdapat path dari u ke v. Hubungan connected bersifat equivalence relation (refleksif, simetris, transitif), sehingga vertex-vertex dapat dipartisi menjadi connected component: kelompok-kelompok maksimal yang saling connected.

Graph di atas memiliki 3 connected component. Vertex G sendirian disebut isolated vertex — sebuah komponen berukuran 1.

Untuk directed graph, kita membedakan:

• Strongly connected — ada path dari u ke v dan dari v ke u untuk setiap pasangan.
• Weakly connected — graph yang dianggap undirected (semua panah diabaikan) bersifat connected.
• Strongly connected component (SCC) — kelompok maksimal yang strongly connected.

Algoritma untuk menemukan SCC (Kosaraju, Tarjan) akan dibahas pada Chapter Strongly Connected Components di Section algoritma graph.

Weight, Cost, dan Capacity #

Pada weighted graph, setiap edge memiliki nilai numerik yang disebut weight (atau cost). Interpretasi weight bergantung domain:

• Peta jalan → jarak (km) atau waktu tempuh (menit).
• Jaringan listrik → kapasitas (ampere).
• Penerbangan → tarif tiket (rupiah).
• Dependency graph → bobot sering 1 (uniform).

Penggunaan istilah:

• Path length (unweighted) = jumlah edge pada path.
• Path cost (weighted) = jumlah weight edge pada path.
• Shortest path = path dengan cost minimum (atau, pada unweighted graph, dengan jumlah edge minimum).

Tabel Ringkasan Terminologi #

Diameter dan Jarak Graph #

Distance d(u, v) = panjang path terpendek antara u dan v. Bila tidak ada path, d(u, v) = ∞. Diameter graph = max d(u, v) untuk semua pasangan vertex yang connected. Contoh:

• Path graph A-B-C-D: diameter = 3 (dari A ke D).
• Complete graph Kₙ: diameter = 1 (semua vertex terhubung langsung).
• Tree: diameter dapat dihitung dengan dua BFS dalam O(V).

Menghitung diameter adalah masalah klasik yang akan kita selesaikan dengan BFS dua kali pada Chapter Graph Traversal dan Graph Problems.

Ringkasan #

• Degree menghitung edge incident ke vertex; pada directed graph dipecah menjadi in-degree dan out-degree.
• Handshaking lemma: jumlah degree pada undirected graph = 2|E|.
• Walk → trail → path → cycle: masing-masing memiliki aturan pengulangan vertex/edge yang berbeda.
• Connected component adalah partisi equivalence vertex berdasarkan hubungan connected.
• Weighted graph memberi nilai numerik pada edge; cost path = jumlah weight edge.
• Sparse vs dense menentukan representasi memori yang efisien.
• Tabel terminologi di atas dapat dipakai sebagai referensi cepat saat membaca Chapter-Chaapter algoritma graph selanjutnya.