Daftar Ketetanggaan dan Representasi Matriks dari Grafik

⚡ Ringkasan Cerdas

Representasi daftar dan matriks kedekatan dari sebuah graf menyimpan simpul dan sisi dalam memori, memungkinkan algoritma untuk menelusuri jaringan. Daftar kedekatan menggunakan daftar berantai per simpul, sedangkan matriks kedekatan menggunakan kisi dua dimensi berbentuk persegi.

📐 Daftar Kedekatan: Sebuah array berisi V linked list di mana setiap list pada indeks i menyimpan setiap verteks yang berdekatan dengan verteks i, sehingga membutuhkan memori O(V + E).
🗺️ Matriks Kedekatan: Array dua dimensi AV × V di mana matriks[i][j] menyimpan bobot tepi atau 1 jika terdapat tepi antara simpul i dan simpul j.
⚡ Kecepatan Pencarian: Matriks kedekatan menjawab pertanyaan “apakah ada sisi antara i dan j?” dalam waktu O(1), sedangkan daftar kedekatan membutuhkan waktu O(derajat) untuk memindai daftar tetangga.
💾 Оперативная память: Matriks kedekatan selalu mengkonsumsi memori O(V²) bahkan untuk graf yang jarang, sedangkan daftar kedekatan skalanya bergantung pada jumlah sisi sebenarnya.
🔍 Paling cocok: Pilih matriks kedekatan untuk graf padat dengan kueri tepi yang sering dan daftar kedekatan untuk graf jarang dan beban kerja yang berat dalam penelusuran.
️ aplikasi: Kedua representasi tersebut mendukung algoritma BFS, DFS, Dijkstra, PageRank, perutean jaringan jalan, dan pipeline Graph Neural Network yang digunakan di berbagai sistem AI.

Baca Selengkapnya

Meski terlihat berbeda, semuanya jenis grafik dapat direpresentasikan dengan cara yang serupa. Secara umum terdapat dua jenis representasi graf:

Matriks Adjacency
Daftar Kedekatan

Daftar Kedekatan

Daftar kedekatan terdiri dari daftar berantai. Setiap simpul dianggap sebagai indeks larik, dan setiap elemen mewakili daftar berantai. Daftar berantai ini berisi simpul-simpul yang berbagi sisi dengan simpul indeks.

Berikut adalah contoh daftar kedekatan (adjacency list):

Misalkan sebuah graf memiliki V jumlah simpul dan E jumlah sisi. Kompleksitas ruang dari daftar ketetanggaan adalah O(V + E)yang skalanya bergantung pada jumlah sisi sebenarnya, bukan setiap pasangan simpul yang mungkin.

Kompleksitas ruang terburuk menjadi O(V²) jika graf yang diberikan adalah graf lengkap, karena setiap simpul terhubung ke setiap simpul lainnya.

Matriks Adjacency

Matriks kedekatan terdiri dari larik 2D. Untuk graf dengan V simpul, ukuran matriksnya adalah V × V.

Kami matrix[i][j] = 5Artinya, terdapat sisi antara node i dan node j yang memiliki bobot 5.

Mari kita perhatikan grafik berikut dan matriks kedekatannya:

Kami membangun Array 2D menggunakan langkah-langkah ini:

Langkah 1) Titik sudut A memiliki sisi langsung dengan B, dan bobotnya adalah 5. Jadi, sel di baris A dan kolom B akan diisi dengan 5. Sel-sel lainnya di baris A akan diisi dengan nol.

Langkah 2) Simpul B memiliki sisi langsung dengan C, dan bobotnya adalah 4. Jadi, sel di baris B dan kolom C akan diisi dengan 4. Sel-sel yang tersisa di baris B akan diisi dengan nol, karena B tidak memiliki sisi keluar ke simpul lain.

Langkah 3) Titik sudut C tidak memiliki hubungan langsung dengan titik sudut lainnya. Oleh karena itu, baris C akan diisi dengan angka nol.

Langkah 4) Titik sudut D memiliki sisi berarah dengan A dan C.

Sel pada baris D dan kolom A akan memiliki nilai 7. Sel pada baris D dan kolom C akan memiliki nilai 2.
Sel-sel lainnya di baris D akan diisi dengan angka nol.

Langkah 5) Titik sudut E memiliki sisi berarah dengan B dan D. Sel pada baris E dan kolom B akan memiliki nilai 6. Sel pada baris E dan kolom D akan memiliki nilai 3. Sel-sel lainnya pada baris E akan diisi dengan angka nol.

Berikut beberapa hal yang perlu diperhatikan:

Graf tersebut tidak memiliki loop diri ketika diagonal utama matriks kedekatan bernilai 0.
Graf tersebut merupakan graf berarah jika sel-sel di (a, b) dan (b, a) tidak memiliki nilai yang sama. Jika tidak, graf tersebut adalah graf tak berarah.
Grafik tersebut merupakan grafik berbobot jika nilai dari sel mana pun lebih besar dari 1.

Masalah utama dengan matriks kedekatan adalah bahwa ia membutuhkan ruang yang besar. Bahkan sisi yang tidak ada pun tetap mengalokasikan sel dalam memori.

Sebagai contoh, jika kita memiliki grafik dengan 100 simpul, maka dibutuhkan 10,000 sel untuk menyimpannya. RAMDengan jumlah sisi yang lebih sedikit dalam graf, mengalokasikan memori sebesar itu dapat menjadi boros. Jadi kompleksitas ruang menggunakan matriks kedekatan adalah O(N²), di mana N adalah jumlah node dalam graf.

Daftar Kedekatan vs Matriks Kedekatan

Sebelum memilih representasi, ada baiknya membandingkan kedua model secara berdampingan di seluruh operasi yang mendominasi beban kerja grafik nyata:

Operaproduksi	Matriks Adjacency	Daftar Kedekatan
Kompleksitas ruang	O(V²)	O(V + E)
Tambahkan titik sudut	O(V²)	O (1)
Tambahkan tepi	O (1)	O (1)
Hilangkan tepinya	O (1)	HAI(E)
Periksa apakah sisi (i, j) ada	O (1)	O(derajat i)
Lakukan iterasi pada tetangga i.	O (V)	O(derajat i)
Terbaik untuk	Grafik padat, kueri tepi yang sering	Graf jarang, tugas yang membutuhkan banyak penelusuran

Singkatnya, matriks kedekatan unggul dalam pencarian tepi dengan waktu konstan, sedangkan daftar kedekatan unggul dalam hal memori dan iterasi tetangga, itulah sebabnya algoritma seperti BFS, DFS, dan Dijkstra biasanya dipasangkan dengan daftar kedekatan.

Keuntungan dan Kerugian Representasi Graf

Setiap representasi memiliki kelebihan dan kekurangannya masing-masing. Mengetahui kekuatan dan kelemahan kedua model tersebut akan membantu Anda memilih model yang tepat untuk masalah yang sedang Anda selesaikan.

Keunggulan Matriks Kedekatan:

Kueri eksistensi tepi O(1) waktu konstan antara pasangan simpul mana pun.
Pengindeksan tetap membuat algoritma berbasis matriks seperti Floyd-Warshall dan penutupan transitif mudah diimplementasikan.
Tepi berbobot cocok secara alami dalam satu sel matriks.

Kelemahan Matriks Kedekatan:

Memboroskan memori O(V²) ketika grafnya jarang.
Menambahkan titik sudut baru memerlukan perubahan ukuran seluruh matriks.
Mengiterasi tetangga dari satu simpul membutuhkan waktu O(V) bahkan ketika simpul tersebut hanya memiliki sedikit sisi.

Keunggulan Daftar Berdekatan:

Hanya menggunakan memori O(V + E), yang mendekati jumlah sisi sebenarnya pada graf jarang.
Menambahkan simpul atau sisi baru adalah O(1).
Algoritma penelusuran seperti BFS dan DFS mengulangi tetangga dalam O(derajat), memberikan waktu eksekusi keseluruhan O(V + E).

Kelemahan Daftar Berdekatan:

Memeriksa apakah suatu sisi tertentu ada atau tidak membutuhkan waktu O(derajat) dan bukan O(1).
Lokalitas cache lebih lemah karena linked list tersebar di seluruh memori.
Edge berbobot memerlukan field pendamping atau daftar pasangan, yang sedikit memperumit struktur data.

Kapan Menggunakan Adjacency List vs Adjacency Matrix?

Pemilihan representasi bergantung pada kepadatan graf dan operasi yang paling sering Anda jalankan. Gunakan panduan singkat ini untuk memilih struktur yang tepat:

Lebih suka matriks kedekatan. ketika grafnya padat (E mendekati V²), ketika sisi-sisinya jarang berubah, dan ketika algoritma Anda menanyakan "apakah ada sisi antara i dan j?" berkali-kali.
Lebih suka daftar yang berdekatan ketika graf jarang (E jauh lebih kecil daripada V²), ketika himpunan simpul atau sisi bertambah selama eksekusi, dan ketika Anda menelusuri graf dengan BFS, DFS, atau Algoritma jalur terpendek Dijkstra.
Lebih menyukai model campuran. (daftar kedekatan ditambah himpunan hash dari tepi) ketika Anda membutuhkan iterasi tetangga yang cepat dan kueri tepi O(1), dengan biaya memori tambahan.

Pustaka grafik modern seperti NetworkX dan igraph secara default menggunakan daftar kedekatan karena sebagian besar grafik di dunia nyata — jaringan sosial, peta jalan, halaman web, dependensi paket — bersifat jarang dan membutuhkan banyak penelusuran.

Pertanyaan Umum Demo Slot

Daftar kedekatan (adjacency list) adalah array dari V daftar berantai (linked list) di mana setiap daftar pada indeks i menyimpan setiap simpul yang berdekatan dengan simpul i. Penggunaan memori adalah O(V + E), yang cocok untuk graf jarang (sparse graph) dan algoritma penelusuran seperti BFS dan DFS.

Matriks kedekatan adalah larik dua dimensi V × V di mana matriks[i][j] menyimpan bobot sisi atau 1 jika ada sisi antara simpul i dan simpul j. Pencarian sisi adalah O(1) tetapi memori selalu O(V²).

Matriks kedekatan menjawab kueri keberadaan tepi dalam O(1). Daftar kedekatan mengulangi tetangga dalam O(derajat), yang lebih cepat untuk algoritma penelusuran seperti BFS, DFS, dan Dijkstra. Pilihan terbaik bergantung pada operasi yang mendominasi beban kerja Anda.

Gunakan daftar kedekatan (adjacency list) ketika graf jarang (sparse), ketika simpul dan sisi berubah selama eksekusi, dan ketika algoritma sering menelusuri tetangga. Jaringan sosial, peta jalan, dan graf halaman web semuanya sesuai dengan profil ini.

Gunakan matriks kedekatan ketika graf padat, ketika himpunan simpul tetap, dan ketika algoritma menanyakan sisi yang sama berulang kali. Floyd-Warshall dan penutupan transitif keduanya bekerja secara alami pada matriks kedekatan.

Ya. Untuk graf berarah, matriksnya tidak simetris dan daftar hanya menyimpan tetangga yang keluar. Untuk graf berbobot, sel matriks menyimpan bobot sedangkan daftar menyimpan pasangan tetangga dan bobot.

Jaringan Neural Graf memasukkan matriks kedekatan atau tensor tepi jarang ke dalam lapisan pembelajaran mesin untuk deteksi penipuan, prediksi sifat molekul, dan sistem rekomendasi. Graf pengetahuan juga bergantung pada pengkodean daftar kedekatan untuk AI yang ditingkatkan dengan pengambilan informasi.

Ya. GitHub Copilot dan ChatGPT menghasilkan templat daftar dan matriks kedekatan untuk Python, C++, dan JavaPengembang masih perlu memverifikasi kasus-kasus khusus seperti tepi duplikat, loop diri, dan penanganan yang benar terhadap grafik berarah atau berbobot.