Representasi Graf dalam Ilmu Komputer

Pengantar

Graf (graph) adalah struktur data yang terdiri atas himpunan simpul (vertex) dan sisi (edge) yang menghubungkan pasangan simpul. Graf banyak digunakan untuk memodelkan hubungan antarobjek, seperti jaringan jalan, jaringan sosial, rangkaian elektronik, dan lainlain. Karena graf dapat memiliki banyak bentuk (arah, berbobot, tidak berbobot, sederhana, multigraf, dll.), cara merepresentasikannya dalam memori komputer menjadi sangat penting. Representasi yang tepat memengaruhi efisiensi algoritmaalgoritma graf seperti pencarian lintasan, penentuan jarak terpendek, dan pencarian komponen terhubung.

Matriks Ketetanggaan (Adjacency Matrix)

Matriks ketetanggaan adalah sebuah matriks berukuran V V (V adalah jumlah simpul). Elemen A[i][j] bernilai 1 (atau bobot sisi) jika terdapat sisi dari simpul i ke simpul j, dan 0 bila tidak ada. Untuk graf tak berarah, matriks bersifat simetris.

Keunggulan

• Memeriksa keberadaan sisi antara dua simpul dapat dilakukan dalam O(1).
• Implementasi sederhana, cocok untuk graf yang padat (banyak sisi).
• Mudah mengubah menjadi representasi lain, misalnya menambahkan bobot.

Kelemahan

• Memakan ruang O(V), tidak efisien untuk graf jarang.
• Mengiterasi semua tetangga sebuah simpul memerlukan O(V) walaupun hanya sedikit tetangga.

            0 1 0 0            1 0 1 0            0 1 0 1            0 0 1 0        

Daftar Ketetanggaan (Adjacency List)

Daftar ketetanggaan menyimpan untuk setiap simpul sebuah daftar (biasanya linked list atau array dinamis) yang berisi semua tetangga yang terhubung dengan simpul tersebut. Representasi ini cocok untuk graf jarang, dimana E (jumlah sisi) jauh lebih kecil daripada V.

Keunggulan

• Ruang yang dibutuhkan hanya O(V + E).
• Mengiterasi tetangga suatu simpul berjalan dalam O(degree(v)), sehingga efisien untuk algoritma seperti DFS/BFS.

Kelemahan

• Memeriksa apakah sisi (u,v) ada memerlukan waktu O(degree(u)) atau pencarian linear dalam daftar.
• Implementasinya sedikit lebih kompleks dibanding matriks.

            1 : 2            2 : 1, 3            3 : 2, 4            4 : 3        

Daftar Sisi (Edge List)

Daftar sisi menyimpan setiap sisi dalam bentuk pasangan (u, v) atau tripel (u, v, w) bila berbobot. Representasi ini sangat sederhana dan berguna bila hanya diperlukan iterasi melalui semua sisi, misalnya dalam algoritma Kruskal.

Keunggulan

• Sangat mudah dibangun, hanya sekadar array dari sisi.
• Ruang O(E), paling efisien bila hanya membutuhkan daftar sisi.

Kelemahan

• Menemukan semua tetangga sebuah simpul memerlukan pencarian linier O(E).
• Operasi cek keberadaan sisi (u, v) juga O(E).

            (1,2)            (2,3)            (3,4)        

Bagaimana Memilih Representasi yang Tepat?

Tidak ada satu representasi yang selalu paling baik. Pilihan bergantung pada karakteristik graf dan jenis operasi yang paling sering dilakukan.

Contoh pilihan praktis:

• Jalur transportasi kota: biasanya graf jarang, gunakan daftar ketetanggaan.
• Jaringan sosial kecil: jika jumlah pengguna terbatas, matriks ketetanggaan mempermudah analisis hubungan langsung.
• Algoritma Minimum Spanning Tree (Kruskal): daftar sisi lebih mudah diproses setelah diurutkan.

Kesimpulan

Representasi graf merupakan fondasi bagi semua algoritma graf. Matriks ketetanggaan memberikan kecepatan akses konstan dengan biaya ruang tinggi, cocok untuk graf padat. Daftar ketetanggaan menyeimbangkan antara ruang dan waktu, ideal untuk graf jarang dan operasi traversal. Daftar sisi paling sederhana dan bermanfaat bila fokus pada pengolahan seluruh sisi. Memahami kelebihan dan keterbatasan masingmasing memungkinkan programmer memilih struktur yang optimal untuk permasalahan spesifik.