Daftar Ketetanggaan dan Representasi Matriks dari Grafik
Sarah Chen
Meski terlihat berbeda, semuanya jenis grafik dapat direpresentasikan dengan cara serupa. Umumnya ada dua jenis Representasi Grafik:
- Matriks Adjacency
- Daftar Kedekatan
Daftar Kedekatan
Daftar Kedekatan terdiri dari Daftar Tertaut. Setiap simpul dianggap sebagai indeks array, dan setiap elemen mewakili daftar tertaut. Daftar tertaut ini berisi simpul-simpul yang memiliki tepian dengan simpul indeks.
Berikut ini contoh daftar kedekatan:
Katakanlah suatu graf memuat V jumlah simpul dan E jumlah sisi.
Secara umum, kompleksitas ruang akan O(V + E).
Kompleksitas ruang terburuk akan terjadi O(V2) jika Grafik yang diberikan adalah Grafik lengkap
Matriks Adjacency
Matriks Ketetanggaan terdiri dari larik 2D. Graf yang mempunyai jumlah simpul V maka ukuran matriksnya adalah VxV.
Mengatakan, matrix[i][j] = 5. Artinya ada edge antara node i dan j yang bobotnya 5.
Mari kita lihat Grafik berikut dan matriks Adjasensinya:
Kami menciptakan Array 2D menggunakan langkah-langkah ini:
Langkah 1) Simpul A bersisi lurus dengan B, dan bobotnya 5. Jadi, sel pada baris A dan kolom B akan diisi dengan 5. Sel-sel pada baris A yang tersisa akan diisi dengan nol.
Langkah 2) Simpul B mempunyai sisi lurus dengan C, dan bobotnya adalah 4. Jadi, sel pada baris B dan kolom C akan diisi dengan 4. Sel yang tersisa pada baris B akan diisi dengan nol karena B tidak memiliki tepi keluar ke mana pun. node lainnya.
Langkah 3) Simpul C tidak mempunyai sisi langsung dengan simpul lainnya. Jadi, baris C akan diisi dengan angka nol.
Langkah 4) Simpul D mempunyai sisi berarah dengan A dan C.
- Di sini, sel pada baris D dan kolom A akan bernilai 7. Sel pada baris D dan kolom C akan bernilai 2.
- Sel-sel lainnya di baris D akan diisi dengan angka nol.
Langkah 5) Simpul E mempunyai sisi berarah dengan B dan D. Sel pada baris E dan kolom B akan bernilai 6. Sel pada baris E dan kolom D akan bernilai 3. Sel-sel lainnya pada baris D akan bernilai diisi dengan angka nol.
Berikut beberapa hal yang perlu diperhatikan:
- Grafik tidak memiliki self-loop ketika diagonal utama matriks ketetanggaannya adalah 0.
- Grafik tersebut merupakan grafik berarah jika indeks (a,b) dan (b,a) tidak memiliki nilai yang sama. Jika tidak, maka Grafik tersebut merupakan grafik berarah.
- Grafik akan menjadi grafik berbobot jika nilai selnya lebih dari 1.
Ada beberapa masalah dengan matriks ketetanggaan karena memerlukan ruang kuadrat. Di sini, kami menyimpan sisi-sisi yang tidak terhubung. Tepian ini mengalokasikan ruang dalam memori.
Misalnya, jika kita memiliki grafik dengan 100 node, maka diperlukan 10 ribu sel untuk menyimpannya di RAMDengan lebih sedikit sisi pada Grafik, mengalokasikan memori yang besar bisa menjadi pemborosan. Jadi, kompleksitas ruang menggunakan matriks Ketetanggaan akan menjadi O(N2), dimana N berarti jumlah node pada Grafik.
