Directed dan Undirected Graph

Sebuah jalan dua arah antara Jakarta dan Bandung berbeda dengan relasi “mengikuti” di Twitter — yang pertama simetris, yang kedua tidak. Pilihan antara directed (berarah) dan undirected (tidak berarah) adalah keputusan paling fundamental dalam memodelkan graph, karena ia mengubah notasi edge, mengubah definisi adjacency, dan menentukan algoritma mana yang valid. Pada Chapter ini kita akan membandingkan kedua jenis graph, melihat kapan masing-masing cocok dipakai, lalu mengimplementasikan keduanya dengan adjacency list yang sama tetapi berbeda aturan penyimpanan edge.

Definisi: Edge sebagai Pasangan #

Pada undirected graph, edge adalah pasangan tak berurut {u, v}. Edge {u, v} sama dengan {v, u} — keduanya menyatakan “u dan v saling terhubung”. Akibatnya, untuk graph undirected dengan V vertex, jumlah edge maksimum adalah V(V-1)/2 (kombinasi 2 dari V).

Pada directed graph (disingkat digraph), edge adalah pasangan berurut (u, v) yang menyatakan “dari u ke v”. Edge (u, v) berbeda dari (v, u) — keduanya boleh ada bersamaan dan dihitung sebagai dua edge terpisah. Akibatnya, jumlah edge maksimum adalah V(V-1) (permutasi 2 dari V).

Pada undirected graph di kiri, edge {A,B} berarti A dapat ke B dan B dapat ke A. Pada directed graph di kanan, ada edge X→Y tetapi tidak ada Y→X, sehingga Y tidak dapat kembali ke X langsung.

Aturan Penyimpanan Edge #

Aturan penulisan edge menentukan bagaimana kita menyimpan data:

• Undirected: setiap edge {u, v} disimpan dua kali — (u, v) pada adjacency list u, dan (v, u) pada adjacency list v. Akibatnya memori adjacency list O(2E) = O(E).
• Directed: setiap edge (u, v) disimpan satu kali — hanya pada adjacency list u. Memori adjacency list O(E).

Kode: Dua Graph dengan Data Sama, Aturan Berbeda #

#include <iostream>
#include <vector>

class UndirectedGraph {
public:
    explicit UndirectedGraph(int n) : adj_(n) {}
    void add_edge(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);   // dua arah
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

class DirectedGraph {
public:
    explicit DirectedGraph(int n) : adj_(n) {}
    void add_edge(int u, int v) {
        adj_[u].push_back(v);   // satu arah
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

void print_graph(const std::string& name, const auto& g) {
    std::cout << name << " (V=" << g.v_count() << "):\n";
    for (int u = 0; u < g.v_count(); ++u) {
        std::cout << "  " << u << " ->";
        for (int v : g.neighbors(u)) std::cout << " " << v;
        std::cout << '\n';
    }
}

int main() {
    // Daftar pasangan vertex
    std::vector<std::pair<int,int>> pairs = {{0,1}, {1,2}, {0,2}};

    UndirectedGraph ug(3);
    DirectedGraph   dg(3);
    for (auto [u, v] : pairs) {
        ug.add_edge(u, v);
        dg.add_edge(u, v);
    }

    print_graph("UndirectedGraph", ug);
    print_graph("DirectedGraph",   dg);

    // Hitung total elemen adjacency list
    int ug_total = 0, dg_total = 0;
    for (int u = 0; u < 3; ++u) {
        ug_total += ug.neighbors(u).size();
        dg_total += dg.neighbors(u).size();
    }
    std::cout << "\nTotal elemen adjacency list:\n";
    std::cout << "  Undirected = " << ug_total << " (2 * |E|)\n";
    std::cout << "  Directed   = " << dg_total << " (|E|)\n";
    return 0;
}

Output yang Dihasilkan:

UndirectedGraph (V=3):
  0 -> 1 2
  1 -> 0 2
  2 -> 1 0
DirectedGraph (V=3):
  0 -> 1 2
  1 -> 2
  2 ->

Total elemen adjacency list:
  Undirected = 6 (2 * |E|)
  Directed   = 3 (|E|)

1. Baris void add_edge(int u, int v) di UndirectedGraph: menambahkan edge dua kali — (u,v) dan (v,u). Akibatnya neighbors(u) selalu berisi v bila neighbors(v) berisi u.
2. Baris void add_edge(int u, int v) di DirectedGraph: menambahkan edge satu kali saja. Tidak ada jaminan simetri antar neighbors(u) dan neighbors(v).
3. Baris void print_graph(... const auto& g): parameter auto (C++20) memungkinkan satu fungsi template untuk kedua jenis graph. Pada C++17, ganti dengan template <class G>.
4. Hasil Undirected = 6, Directed = 3: dengan 3 edge, undirected menyimpan 6 entri (2× per edge) sedangkan directed hanya 3 (1× per edge). Ini adalah implikasi langsung dari definisi pasangan tak berurut vs berurut.

Kapan Memakai Directed vs Undirected #

Pilihan bergantung pada apakah hubungan bersifat simetris. Berikut panduan praktis:

Konsekuensi pada Algoritma #

Pilihan directed/undirected memengaruhi banyak aspek:

• Adjacency: pada undirected, neighbors(u) selalu symmetric. Pada directed, tidak ada jaminan.
• Reachability: pada undirected, bila v reachable dari u maka sebaliknya juga. Pada directed, bisa saja u dapat ke v tetapi tidak sebaliknya.
• Cycle detection: undirected cukup track parent; directed memerlukan pewarnaan tiga warna (white/gray/black) — dibahas pada Chapter Cycle Detection.
• Strongly connected: konsep ini hanya berlaku pada directed graph.
• Topological sort: hanya valid pada directed acyclic graph (DAG); tidak ada padanan pada undirected.

Konversi: Directed ke Undirected #

Terkadang kita perlu “mengabaikan arah” sebuah directed graph untuk menganalisis connectivity lemah. Operasi ini disebut underlying undirected graph: untuk setiap edge (u, v) pada directed graph, tambahkan {u, v} pada undirected graph.

Kode: Konversi Directed ke Undirected #

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

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

    // Konversi ke undirected dengan set untuk deduplikasi
    std::set<std::pair<int,int>> undirected_set;
    for (auto [u, v] : dir_edges) {
        if (u > v) std::swap(u, v);              // normalisasi: u selalu <= v
        undirected_set.insert({u, v});
    }

    std::cout << "Directed edges: " << dir_edges.size() << '\n';
    std::cout << "Undirected edges (unique): " << undirected_set.size() << '\n';

    std::cout << "\nDaftar edge undirected hasil konversi:\n";
    for (const auto& [u, v] : undirected_set) {
        std::cout << "  {" << u << ", " << v << "}\n";
    }

    // Weakly connected check: cukup cek connected component pada underlying undirected
    std::vector<std::vector<int>> und_adj(V);
    for (const auto& [u, v] : undirected_set) {
        und_adj[u].push_back(v);
        und_adj[v].push_back(u);
    }

    std::vector<bool> visited(V, false);
    int components = 0;
    for (int s = 0; s < V; ++s) {
        if (visited[s]) continue;
        components++;
        std::vector<int> stack = {s};
        visited[s] = true;
        while (!stack.empty()) {
            int u = stack.back(); stack.pop_back();
            for (int v : und_adj[u]) if (!visited[v]) { visited[v] = true; stack.push_back(v); }
        }
    }
    std::cout << "\nWeakly connected components: " << components << '\n';
    return 0;
}

Output yang Dihasilkan:

Directed edges: 4
Undirected edges (unique): 3

Daftar edge undirected hasil konversi:
  {0, 1}
  {0, 2}
  {1, 2}

Weakly connected components: 1

1. Baris if (u > v) std::swap(u, v);: normalisasi pasangan sehingga u ≤ v. Pasangan (2, 0) dan (0, 2) menjadi (0, 2) yang sama, sehingga std::set otomatis menghapus duplikat.
2. Baris undirected_set.insert({u, v});: std::set menyimpan pasangan unik. Output menunjukkan 4 directed edge terkonversi menjadi 3 undirected edge karena ada (0,2) dan (2,0) yang tergabung.
3. Baris for (const auto& [u, v] : undirected_set): structured binding C++17 — unpack std::pair menjadi dua variabel. Sangat berguna untuk iterasi container pasangan.
4. Hasil Weakly connected components: 1: setelah konversi, semua vertex saling terhubung (graph underlying bersifat connected). Directed graph asli tidak strongly connected (C tidak dapat ke B langsung), tetapi weakly connected.

Mixed Graph #

Pada beberapa masalah (mis. peta jalan dengan kombinasi jalan satu arah dan dua arah), kita memerlukan mixed graph — kombinasi directed dan undirected edge. Strategi yang umum:

1. Konversi setiap undirected edge {u, v} menjadi dua directed edge (u, v) dan (v, u).
2. Treat semua edge sebagai directed pada level algoritma.
3. Saat menghitung statistik berarah (in-degree, out-degree), ingat bahwa undirected edge menyumbang 1 ke kedua degree.

Pendekatan ini mempertahankan keseragaman algoritma — kita tidak perlu menulis dua versi BFS/DFS.

Ringkasan #

• Undirected graph: edge {u, v} = {v, u}, disimpan dua kali pada adjacency list, max edge V(V-1)/2.
• Directed graph: edge (u, v) ≠ (v, u), disimpan satu kali, max edge V(V-1).
• Pilihan jenis graph ditentukan oleh simetri hubungan: pertemanan Facebook undirected, follow Twitter directed.
• Directed graph memerlukan algoritma khusus: cycle detection tiga warna, strongly connected component, topological sort.
• Konversi directed ke undirected: normalisasi pasangan, deduplikasi dengan std::set, lalu jalankan algoritma undirected.
• Mixed graph biasa ditangani dengan konversi: undirected → dua directed edge, lalu treat semua sebagai directed.