Representasi graf

Graf (graph) adalah kumpulan objek yang dihubungkan oleh pasangan-pasangan relasi, sehingga peta jalan, jaringan komputer, dan daftar prasyarat mata kuliah dapat dimodelkan dengannya. Topik ini menetapkan kosakata inti graf, membandingkan dua representasi standar yaitu adjacency list dan adjacency matrix, lalu membangun keduanya dari satu daftar tepi yang sama dalam Python dan Java. Perbandingan memori dan kecepatan cek tepinya menjadi pertimbangan utama ketika algoritma penelusuran diimplementasikan di atasnya.

Kosakata graf yang dipakai sepanjang modul#

Sebuah graf tersusun dari simpul (vertex) yang mewakili objek dan tepi (edge) yang menghubungkan sepasang simpul. Graf tak berarah (undirected) memperlakukan tepi sebagai hubungan dua arah, sehingga tepi 0-1 sama saja dengan tepi 1-0. Graf berarah (directed) menyimpan arah secara eksplisit, sehingga tepi u menuju v tidak otomatis berlaku sebaliknya. Adapun graf berbobot (weighted) melampirkan angka pada setiap tepi, misalnya panjang jalan atau waktu tempuh.

Graf contoh pada seluruh topik modul ini memakai enam simpul berlabel 0 sampai 5 dengan daftar tepi (0, 1), (0, 2), (1, 3), (2, 3), (3, 4), dan (4, 5). Daftar tepi (edge list) adalah bentuk paling ringkas untuk menuliskan graf, karena setiap tepi hanya ditulis sekali. Banyak masukan soal justru diberikan dalam bentuk ini, sehingga keterampilan yang dilatih di sini adalah mengubah daftar tepi menjadi struktur yang mudah ditelusuri. Dua struktur itulah adjacency list dan adjacency matrix.

Adjacency list dan adjacency matrix#

Adjacency list menyimpan graf sebagai pemetaan dari setiap simpul ke daftar tetangganya. Simpul 0 pada graf contoh bertetangga dengan 1 dan 2, sehingga entri 0 berisi [1, 2]. Total memori yang dipakai sebanding dengan $O(V + E)$, dengan $V$ menyatakan jumlah simpul dan $E$ jumlah tepi, karena yang disimpan hanya tepi yang benar-benar ada. Mengecek keberadaan satu tepi berarti menyisir daftar tetangga, yang berbiaya sebanding dengan banyaknya tetangga simpul tersebut.

Adjacency matrix memakai pendekatan yang berlawanan, yaitu matriks $V \times V$ berisi 0 dan 1 dengan sel baris u kolom v bernilai 1 bila tepi u-v ada. Seluruh $V^2$ sel dialokasikan apa pun bentuk grafnya, sehingga memorinya $O(V^2)$. Sebagai gantinya, cek tepi cukup membaca satu sel sehingga berbiaya $O(1)$. Untuk graf tak berarah, matriksnya selalu simetris terhadap diagonal utama karena setiap tepi tercatat dua kali.

Diagram berikut menampilkan graf contoh di sisi kiri dan adjacency matrix-nya di sisi kanan. Sel yang berwarna gelap menandai sel bernilai 1, dan jumlahnya tepat dua kali jumlah tepi karena simetri tadi. Kedua representasi memuat informasi yang sama, yang membedakan hanyalah bentuk aksesnya.

Membangun keduanya dari daftar tepi yang sama#

Kode berikut membangun kedua representasi dari daftar tepi yang sama tanpa library graf apa pun. Perulangan utamanya menjalankan satu pola penting, yaitu setiap tepi (u, v) ditambahkan ke arah u menuju v dan arah v menuju u karena grafnya tak berarah. Lupa arah balik adalah kesalahan yang paling sering muncul dan dibahas pada bagian akhir topik.

# Dua representasi graf tak berarah dibangun dari daftar tepi yang sama.
from collections import defaultdict

# Daftar tepi graf contoh enam simpul, label 0 sampai 5.
tepi = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5)]
n = 6

# Adjacency list: pemetaan simpul ke daftar tetangga.
tetangga = defaultdict(list)
for u, v in tepi:
    tetangga[u].append(v)  # tepi dari u menuju v
    tetangga[v].append(u)  # graf tak berarah: tambahkan juga arah baliknya

print("Adjacency list")
for simpul in sorted(tetangga):
    print(f"  {simpul}: {sorted(tetangga[simpul])}")

# Adjacency matrix: matriks n x n berisi 0 dan 1.
matriks = [[0] * n for _ in range(n)]
for u, v in tepi:
    matriks[u][v] = 1
    matriks[v][u] = 1

print("Adjacency matrix")
for baris in matriks:
    print("  ", baris)

# Pemeriksaan satu tepi pada kedua representasi.
print("Tepi 0-2 ada di matrix:", matriks[0][2] == 1)
print("Tepi 0-2 ada di list  :", 2 in tetangga[0])

Adjacency list
  0: [1, 2]
  1: [0, 3]
  2: [0, 3]
  3: [1, 2, 4]
  4: [3, 5]
  5: [4]
Adjacency matrix
   [0, 1, 1, 0, 0, 0]
   [1, 0, 0, 1, 0, 0]
   [1, 0, 0, 1, 0, 0]
   [0, 1, 1, 0, 1, 0]
   [0, 0, 0, 1, 0, 1]
   [0, 0, 0, 0, 1, 0]
Tepi 0-2 ada di matrix: True
Tepi 0-2 ada di list  : True

Keluarannya menunjukkan adjacency list yang tiap barisnya diurutkan agar mudah dibaca. Pada matriks, jumlah angka 1 di setiap baris tepat sama dengan banyaknya tetangga simpul yang diwakili baris itu. Dua baris terakhir menegaskan perbedaan aksesnya, yaitu membaca satu sel matriks untuk cek tepi dan menyisir daftar untuk adjacency list. Pada graf sekecil ini perbedaannya tak terasa, tetapi pada graf dengan jutaan simpul selisih memori antara $O(V^2)$ dan $O(V + E)$ menentukan program dapat berjalan atau kehabisan memori.

Padanan Java#

Versi Java membangun adjacency list dengan ArrayList yang berisi ArrayList, dan daftar tepinya ditulis sebagai larik dua dimensi. Pola tambah-dua-arahnya persis sama, sehingga keluarannya identik dengan versi Python. Matriks sengaja tidak diulang di sini karena pembangunannya hanya mengganti list dengan larik.

// Adjacency list graf tak berarah enam simpul dari daftar tepi yang sama.
import java.util.ArrayList;
import java.util.List;

public class RepresentasiGraf {
    public static void main(String[] args) {
        int n = 6;
        int[][] tepi = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}};

        List<List<Integer>> tetangga = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tetangga.add(new ArrayList<>());
        }
        for (int[] e : tepi) {
            tetangga.get(e[0]).add(e[1]); // tepi dari u menuju v
            tetangga.get(e[1]).add(e[0]); // arah balik untuk graf tak berarah
        }

        System.out.println("Adjacency list");
        for (int simpul = 0; simpul < n; simpul++) {
            System.out.println("  " + simpul + ": " + tetangga.get(simpul));
        }
    }
}

Adjacency list
  0: [1, 2]
  1: [0, 3]
  2: [0, 3]
  3: [1, 2, 4]
  4: [3, 5]
  5: [4]

Keluarannya sama persis dengan enam baris adjacency list versi Python. Konsistensi ini berguna saat menguji ulang algoritma di dua bahasa, karena setiap selisih keluaran langsung menunjuk adanya bug, bukan perbedaan struktur data.

Kapan memilih yang mana#

Kedua representasi sah dipakai, dan pilihannya ditentukan oleh bentuk graf serta operasi yang dominan. Graf renggang (sparse) yang tepinya jauh lebih sedikit daripada $V^2$ membuang-buang memori bila disimpan sebagai matriks. Graf padat (dense) yang tepinya mendekati $V^2$ justru nyaman di matriks karena cek tepinya konstan. Tabel berikut merangkum perbandingannya.

Angka pada tabel juga menjelaskan mengapa algoritma penelusuran di modul ini selalu berdiri di atas adjacency list. BFS, DFS, Dijkstra, dan Kahn hanya menyusuri tetangga, sehingga iterasi yang berbiaya sebanding dengan jumlah tepi adalah bentuk optimalnya. Adapun matriks cocok ketika grafnya padat atau ketika operasi utamanya membaca pasangan simpul berulang kali.

Kesalahan umum#

Gejalanya khas, yaitu penelusuran dari satu simpul tidak menjangkau simpul yang jelas-jelas terhubung, atau jumlah tetangga antar simpul tidak seimbang. Penyebabnya hampir selalu perulangan pembangunan yang hanya menulis tetangga[u].append(v). Perbaikannya menambahkan tetangga[v].append(u) pada tempat yang sama, sehingga kedua arah terjaga dalam satu langkah.

Pemeriksaannya cepat dilakukan pada graf tak berarah, yaitu pastikan jumlah seluruh isi daftar tetangga bernilai genap dan sama dengan dua kali jumlah tepi. Pada adjacency matrix, keanehannya terlihat dari matriks yang tidak simetris. Kedua pemeriksaan ini cukup untuk menangkap kesalahan arah sebelum algoritma penelusuran dijalankan.

Ringkasan#

• Graf disimpan paling umum sebagai adjacency list berbiaya $O(V + E)$ atau adjacency matrix berbiaya $O(V^2)$, keduanya dibangun dari daftar tepi yang sama.
• Cek satu tepi berbiaya $O(1)$ pada matriks dan sebanding dengan banyaknya tetangga pada list, sedangkan iterasi tetangga paling efisien di list.
• Graf tak berarah menuntut pencatatan tepi dua arah, dan simetri matriksnya dapat dipakai sebagai pemeriksa cepat.
• Graf renggang sebaiknya memakai list, sedangkan graf padat lebih nyaman di matriks.

Referensi#

• Adjacency list — Wikipedia — Bentuk daftar ketetanggaan beserta perbandingan memori dengan matriks.
• Adjacency matrix — Wikipedia — Definisi matriks ketetanggaan dan biaya operasinya.