Pohon melarang satu node punya dua induk — padahal jaringan nyata justru begitu: kota terhubung ke banyak kota, satu orang berteman dengan banyak orang, satu halaman web menaut ke ribuan halaman lain. Graph melonggarkan seluruh aturan hierarki: kumpulan vertex (node) dihubungkan oleh edge (sisi) dengan pola apa pun. Struktur inilah bahasa resmi untuk relasi — peta jalan, jejaring sosial, dependensi antar modul, hingga graph pengetahuan. Bab ini membangun dua representasi graph yang paling umum, adjacency list dan adjacency matrix, pada peta lima kota, lalu menjalankan penelusuran BFS yang akan dipakai berulang kali pada Bab algoritma graph.

Vertex Edge dan Arah Hubungan #

Istilah graph perlu dikenakan dengan tepat sebelum menulis kode. Vertex adalah entitas (misalnya kota); edge adalah hubungan antara dua vertex. Graph tak berarah (undirected) memakai sisi dua arah — jalur Jakarta–Bandung bisa dilalui dari dua arah. Graph berarah (directed) memakai panah — tautan web hanya berlaku satu arah. Weighted graph melampirkan angka pada tiap sisi: jarak kilometer, biaya tiket, atau kekuatan hubungan. Jumlah sisi yang menempel pada satu vertex disebut degree; pada graph berarah terbagi menjadi in-degree dan out-degree. Terakhir, sparse graph punya sedikit sisi dibanding jumlah vertex, sedangkan dense graph hampir menghubungkan semuanya dengan semuanya — perbedaan ini menentukan pilihan representasi.

Adjacency List dengan BFS #

Adjacency list menyimpan satu daftar tetangga untuk setiap vertex: Map<String, List<String>> memetakan nama kota ke kota-kota yang bersisian. Graph tak berarah menyimpan tiap sisi dua kali — sekali di daftar masing-masing ujung. Di atas representasi tersebut, BFS (Breadth-First Search) menelusuri graph berlapis: semua tetangga langsung lebih dulu, lalu tetangga dua langkah, dan seterusnya — persis perilaku queue:

java GraphKota.java 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class GraphKota {

    // Adjacency list: nama kota -> daftar kota yang bersisian.
    private final Map<String, List<String>> tetangga = new LinkedHashMap<>();

    public static void main(String[] args) {
        GraphKota graph = new GraphKota();
        graph.tambahSisi("Jakarta", "Bandung");
        graph.tambahSisi("Jakarta", "Semarang");
        graph.tambahSisi("Bandung", "Yogyakarta");
        graph.tambahSisi("Semarang", "Yogyakarta");
        graph.tambahSisi("Semarang", "Surabaya");
        graph.tambahSisi("Yogyakarta", "Surabaya");

        System.out.println("=== Adjacency list (graph tak berarah) ===");
        graph.cetakAdjacencyList();

        System.out.println();
        System.out.println("=== BFS mulai dari Jakarta ===");
        System.out.println("Urutan kunjungan: " + graph.bfs("Jakarta"));
    }

    void tambahSisi(String kotaA, String kotaB) {
        tetangga.computeIfAbsent(kotaA, k -> new ArrayList<>()).add(kotaB);
        tetangga.computeIfAbsent(kotaB, k -> new ArrayList<>()).add(kotaA);
    }

    String bfs(String mulai) {
        List<String> urutan = new ArrayList<>();
        Deque<String> antrean = new ArrayDeque<>();
        Map<String, Boolean> dikunjungi = new LinkedHashMap<>();
        for (String kota : tetangga.keySet()) {
            dikunjungi.put(kota, false);
        }

        dikunjungi.put(mulai, true);
        antrean.offer(mulai);

        while (!antrean.isEmpty()) {
            String kota = antrean.poll();          // kunjungi node terdepan
            urutan.add(kota);
            for (String tetanggaKota : tetangga.get(kota)) {
                if (!dikunjungi.get(tetanggaKota)) {
                    dikunjungi.put(tetanggaKota, true);
                    antrean.offer(tetanggaKota);   // jadwalkan tetangga baru
                }
            }
        }
        return String.join(" -> ", urutan);
    }

    void cetakAdjacencyList() {
        for (Map.Entry<String, List<String>> e : tetangga.entrySet()) {
            System.out.println("  " + e.getKey() + ": " + e.getValue());
        }
    }
}

Output yang Dihasilkan:

text 
=== Adjacency list (graph tak berarah) ===
  Jakarta: [Bandung, Semarang]
  Bandung: [Jakarta, Yogyakarta]
  Semarang: [Jakarta, Yogyakarta, Surabaya]
  Yogyakarta: [Bandung, Semarang, Surabaya]
  Surabaya: [Semarang, Yogyakarta]

=== BFS mulai dari Jakarta ===
Urutan kunjungan: Jakarta -> Bandung -> Semarang -> Yogyakarta -> Surabaya

Urutan BFS dari Jakarta adalah Jakarta -> Bandung -> Semarang -> Yogyakarta -> Surabaya. Mari kita bedah mengapa urutannya seperti itu:

  1. Baris 20-27 (tambahSisi): computeIfAbsent membuat daftar tetangga saat kota pertama kali muncul, lalu add menambalkan ujung satunya. Karena LinkedHashMap dipakai, urutan sisipan terjaga — urutan daftar tetangga ditentukan urutan pemanggilan tambahSisi, dan itulah yang membuat output program deterministik.
  2. Baris 37-40 (tanda kunjungan): array dikunjungi diinisialisasi untuk semua kota sebelum penelusuran dimulai. BFS menandai vertex saat masuk antrean, bukan saat keluar — tanpa tanda ini, kota dengan dua tetangga sama akan masuk antrean dua kali.
  3. Baris 42-54 (loop utama BFS): setiap iterasi mengeluarkan satu kota dari depan antrean, mencatatnya ke urutan, lalu mengantrekan seluruh tetangga yang belum ditandai. Queue FIFO-lah yang memaksa semua kota jarak satu (Bandung, Semarang) keluar lebih dulu sebelum kota jarak dua (Yogyakarta, Surabaya).

Kompleksitas BFS adalah O(V + E): setiap vertex masuk antrean tepat satu kali, dan setiap sisi diperiksa paling dua kali. Penelusuran ini adalah fondasi pencarian jalur terpendek pada graph tak berbobot yang akan kita bangun di Bab Algoritma Graph.

Adjacency Matrix #

Representasi kedua menyimpan matriks V×V: sel di baris i kolom j bernilai 1 (atau bobot) bila ada sisi dari vertex i ke vertex j. Program berikut memakai graph tak berarah yang sama persis, lalu menambahkan graph berarah berbobot untuk menunjukkan variasinya:

java GraphMatriks.java 
public class GraphMatriks {

    public static void main(String[] args) {
        String[] kota = {"Jakarta", "Bandung", "Semarang", "Yogyakarta", "Surabaya"};

        // ===== Graph tak berarah: adjacency matrix =====
        int[][] matriks = new int[kota.length][kota.length];
        tambahSisi(matriks, kota, "Jakarta", "Bandung");
        tambahSisi(matriks, kota, "Jakarta", "Semarang");
        tambahSisi(matriks, kota, "Bandung", "Yogyakarta");
        tambahSisi(matriks, kota, "Semarang", "Yogyakarta");
        tambahSisi(matriks, kota, "Semarang", "Surabaya");
        tambahSisi(matriks, kota, "Yogyakarta", "Surabaya");

        System.out.println("=== Adjacency matrix (graph tak berarah) ===");
        cetakMatriks(kota, matriks);

        int jumlahSisi = 0;
        for (int i = 0; i < kota.length; i++) {
            for (int j = i + 1; j < kota.length; j++) {
                if (matriks[i][j] == 1) {
                    jumlahSisi++;
                }
            }
        }
        System.out.println("Jumlah sisi terhitung dari matriks: " + jumlahSisi);
        System.out.println("Ruang simpan: " + (kota.length * kota.length) + " sel");

        System.out.println();
        System.out.println("=== Matrix berarah berbobot (jarak dalam km) ===");
        int[][] berat = new int[kota.length][kota.length];
        tambahSisiBerat(berat, kota, "Jakarta", "Bandung", 150);
        tambahSisiBerat(berat, kota, "Jakarta", "Semarang", 450);
        tambahSisiBerat(berat, kota, "Bandung", "Yogyakarta", 400);
        tambahSisiBerat(berat, kota, "Semarang", "Yogyakarta", 130);
        tambahSisiBerat(berat, kota, "Semarang", "Surabaya", 350);
        tambahSisiBerat(berat, kota, "Yogyakarta", "Surabaya", 320);
        tambahSisiBerat(berat, kota, "Surabaya", "Jakarta", 780);
        cetakMatriks(kota, berat);
    }

    static int indeks(String[] kota, String nama) {
        for (int i = 0; i < kota.length; i++) {
            if (kota[i].equals(nama)) {
                return i;
            }
        }
        throw new IllegalArgumentException("Kota tidak dikenal: " + nama);
    }

    static void tambahSisi(int[][] m, String[] kota, String a, String b) {
        m[indeks(kota, a)][indeks(kota, b)] = 1;
        m[indeks(kota, b)][indeks(kota, a)] = 1;   // tak berarah: simetris
    }

    static void tambahSisiBerat(int[][] m, String[] kota, String dari, String ke, int jarak) {
        m[indeks(kota, dari)][indeks(kota, ke)] = jarak;   // berarah: satu sel saja
    }

    static void cetakMatriks(String[] kota, int[][] m) {
        System.out.printf("%-12s", "");
        for (String nama : kota) {
            System.out.printf("%-11s", nama);
        }
        System.out.println();
        for (int i = 0; i < kota.length; i++) {
            System.out.printf("%-12s", kota[i]);
            for (int j = 0; j < kota.length; j++) {
                String sel = (m[i][j] == 0) ? "-" : String.valueOf(m[i][j]);
                System.out.printf("%-11s", sel);
            }
            System.out.println();
        }
    }
}

Output yang Dihasilkan:

text 
=== Adjacency matrix (graph tak berarah) ===
            Jakarta    Bandung    Semarang   Yogyakarta Surabaya   
Jakarta     -          1          1          -          -          
Bandung     1          -          -          1          -          
Semarang    1          -          -          1          1          
Yogyakarta  -          1          1          -          1          
Surabaya    -          -          1          1          -          
Jumlah sisi terhitung dari matriks: 6
Ruang simpan: 25 sel

=== Matrix berarah berbobot (jarak dalam km) ===
            Jakarta    Bandung    Semarang   Yogyakarta Surabaya   
Jakarta     -          150        450        -          -          
Bandung     -          -          -          400        -          
Semarang    -          -          -          130        350        
Yogyakarta  -          -          -          -          320        
Surabaya    780        -          -          -          -

Dua sifat matriks terbaca langsung dari output. Matrix tak berarah simetris terhadap diagonal — baris Jakarta kolom Bandung dan baris Bandung kolom Jakarta sama-sama bernilai 1, sehingga cukup menghitung separuh atas untuk mendapatkan 6 sisi. Matrix berarah berbobot justru asimetris: Jakarta -> Bandung bernilai 150 sedangkan arah baliknya kosong, dan hanya Surabaya -> Jakarta yang bernilai 780 — arah perjalanan satu arah tampak dari sel yang tidak berpasangan.

Memilih Representasi #

Kedua representasi menghasilkan graph yang sama, tetapi biaya operasinya berbeda arah:

AspekAdjacency listAdjacency matrix
Ruang simpanO(V + E)O(V²)
Cek sisi (u, v)O(degree u)O(1)
Menelusur tetangga satu vertexO(degree u)O(V)
Cocok untukgraph jarang (sparse)graph padat (dense) atau ukuran kecil

Peta lima kota menyita 25 sel matriks untuk 6 sisi — mubazir tetapi tak terasa. Graph satu juta halaman web dengan rata-rata 20 tautan per halaman akan menyita 10¹² sel matriks, mustahil, sementara adjacency list hanya menyimpan sekitar 20 juta referensi. Sebaliknya, algoritma yang terus-menerus bertanya “apakah u terhubung ke v?” menikmati jawaban O(1) dari matriks. Kebanyakan graph dunia nyata jarang (sparse), dan pustaka algoritma umumnya memilih adjacency list sebagai default.

Representasi graph kini tersedia; yang belum adalah cara berjalan di atasnya secara cerdas. Tiga bab teknik algoritma di depan — searching, sorting, recursion — akan melengkapi perangkat kita sebelum kembali ke BFS berteman DFS dan Dijkstra pada Bab Algoritma Graph.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

GraphKota.java

Unduh berkas
java 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class GraphKota {

    // Adjacency list: nama kota -> daftar kota yang bersisian.
    private final Map<String, List<String>> tetangga = new LinkedHashMap<>();

    public static void main(String[] args) {
        GraphKota graph = new GraphKota();
        graph.tambahSisi("Jakarta", "Bandung");
        graph.tambahSisi("Jakarta", "Semarang");
        graph.tambahSisi("Bandung", "Yogyakarta");
        graph.tambahSisi("Semarang", "Yogyakarta");
        graph.tambahSisi("Semarang", "Surabaya");
        graph.tambahSisi("Yogyakarta", "Surabaya");

        System.out.println("=== Adjacency list (graph tak berarah) ===");
        graph.cetakAdjacencyList();

        System.out.println();
        System.out.println("=== BFS mulai dari Jakarta ===");
        System.out.println("Urutan kunjungan: " + graph.bfs("Jakarta"));
    }

    void tambahSisi(String kotaA, String kotaB) {
        tetangga.computeIfAbsent(kotaA, k -> new ArrayList<>()).add(kotaB);
        tetangga.computeIfAbsent(kotaB, k -> new ArrayList<>()).add(kotaA);
    }

    String bfs(String mulai) {
        List<String> urutan = new ArrayList<>();
        Deque<String> antrean = new ArrayDeque<>();
        Map<String, Boolean> dikunjungi = new LinkedHashMap<>();
        for (String kota : tetangga.keySet()) {
            dikunjungi.put(kota, false);
        }

        dikunjungi.put(mulai, true);
        antrean.offer(mulai);

        while (!antrean.isEmpty()) {
            String kota = antrean.poll();          // kunjungi node terdepan
            urutan.add(kota);
            for (String tetanggaKota : tetangga.get(kota)) {
                if (!dikunjungi.get(tetanggaKota)) {
                    dikunjungi.put(tetanggaKota, true);
                    antrean.offer(tetanggaKota);   // jadwalkan tetangga baru
                }
            }
        }
        return String.join(" -> ", urutan);
    }

    void cetakAdjacencyList() {
        for (Map.Entry<String, List<String>> e : tetangga.entrySet()) {
            System.out.println("  " + e.getKey() + ": " + e.getValue());
        }
    }
}

GraphMatriks.java

Unduh berkas
java 
public class GraphMatriks {

    public static void main(String[] args) {
        String[] kota = {"Jakarta", "Bandung", "Semarang", "Yogyakarta", "Surabaya"};

        // ===== Graph tak berarah: adjacency matrix =====
        int[][] matriks = new int[kota.length][kota.length];
        tambahSisi(matriks, kota, "Jakarta", "Bandung");
        tambahSisi(matriks, kota, "Jakarta", "Semarang");
        tambahSisi(matriks, kota, "Bandung", "Yogyakarta");
        tambahSisi(matriks, kota, "Semarang", "Yogyakarta");
        tambahSisi(matriks, kota, "Semarang", "Surabaya");
        tambahSisi(matriks, kota, "Yogyakarta", "Surabaya");

        System.out.println("=== Adjacency matrix (graph tak berarah) ===");
        cetakMatriks(kota, matriks);

        int jumlahSisi = 0;
        for (int i = 0; i < kota.length; i++) {
            for (int j = i + 1; j < kota.length; j++) {
                if (matriks[i][j] == 1) {
                    jumlahSisi++;
                }
            }
        }
        System.out.println("Jumlah sisi terhitung dari matriks: " + jumlahSisi);
        System.out.println("Ruang simpan: " + (kota.length * kota.length) + " sel");

        System.out.println();
        System.out.println("=== Matrix berarah berbobot (jarak dalam km) ===");
        int[][] berat = new int[kota.length][kota.length];
        tambahSisiBerat(berat, kota, "Jakarta", "Bandung", 150);
        tambahSisiBerat(berat, kota, "Jakarta", "Semarang", 450);
        tambahSisiBerat(berat, kota, "Bandung", "Yogyakarta", 400);
        tambahSisiBerat(berat, kota, "Semarang", "Yogyakarta", 130);
        tambahSisiBerat(berat, kota, "Semarang", "Surabaya", 350);
        tambahSisiBerat(berat, kota, "Yogyakarta", "Surabaya", 320);
        tambahSisiBerat(berat, kota, "Surabaya", "Jakarta", 780);
        cetakMatriks(kota, berat);
    }

    static int indeks(String[] kota, String nama) {
        for (int i = 0; i < kota.length; i++) {
            if (kota[i].equals(nama)) {
                return i;
            }
        }
        throw new IllegalArgumentException("Kota tidak dikenal: " + nama);
    }

    static void tambahSisi(int[][] m, String[] kota, String a, String b) {
        m[indeks(kota, a)][indeks(kota, b)] = 1;
        m[indeks(kota, b)][indeks(kota, a)] = 1;   // tak berarah: simetris
    }

    static void tambahSisiBerat(int[][] m, String[] kota, String dari, String ke, int jarak) {
        m[indeks(kota, dari)][indeks(kota, ke)] = jarak;   // berarah: satu sel saja
    }

    static void cetakMatriks(String[] kota, int[][] m) {
        System.out.printf("%-12s", "");
        for (String nama : kota) {
            System.out.printf("%-11s", nama);
        }
        System.out.println();
        for (int i = 0; i < kota.length; i++) {
            System.out.printf("%-12s", kota[i]);
            for (int j = 0; j < kota.length; j++) {
                String sel = (m[i][j] == 0) ? "-" : String.valueOf(m[i][j]);
                System.out.printf("%-11s", sel);
            }
            System.out.println();
        }
    }
}