Latihan 2
Latihan: Jaringan Sosial (Adjacency List)
Membangun graf tak berarah menggunakan representasi Adjacency List dengan memadukan Array dan Linked List untuk memodelkan jaringan pertemanan.
Menyiapkan Halaman
Butuh Bantuan Asisten?
Membangun graf tak berarah menggunakan representasi Adjacency List dengan memadukan Array dan Linked List untuk memodelkan jaringan pertemanan.
Bayangkan Anda sedang mendesain arsitektur database untuk sebuah platform media sosial baru. Anda harus menyimpan data relasi pertemanan.
Jika Anda menggunakan Adjacency Matrix, memori server Anda akan cepat habis karena Anda harus menyiapkan matriks berukuran jutaan x jutaan pengguna, padahal rata pemakai mungkin hanya memiliki 500 teman (banyak sel kosong bernilai 0).
Solusi terbaiknya adalah menggunakan Adjacency List. Dalam konsep ini, setiap simpul disimpan bersama rantai (Linked List) dari seluruh simpul yang terhubung. Jika Falih memiliki 2 teman, maka panjang Linked List milik Falih hanyalah 2. Jauh lebih hemat memori!
AddEdge: Anda sedang memodifikasi Array of Linked List. Untuk menambahkan teman baru, Anda cukup melakukan operasi InsertFirst pada indeks Array yang sesuai (indeks src dan dest). Karena sistem pertemanan ini bersifat timbal balik (Undirected), Anda harus menambahkan jalur sebanyak dua kali: satu di rantai milik src menuju dest, dan satu lagi di rantai milik dest menuju src.PrintGraph: Gunakan penelusuran Linked List yang sudah Anda kuasai. Mulailah dari kepala rantai G.firstEdge[i] dan cetak nama-nama teman yang ada di dalamnya hingga menyentuh NULL.Program akan mencetak daftar setiap pengguna diikuti dengan deretan nama pengguna lain yang terhubung (berteman) dengannya.
Karena kita menggunakan logika InsertFirst saat menyambungkan jalur, data yang terakhir kali dimasukkan akan muncul pertama kali di dalam rantai cetakan.
Output:
=== DAFTAR RELASI PERTEMANAN (ADJACENCY LIST) ===
[Falih] berteman dengan: Budi -> Andi ->
[Andi] berteman dengan: Citra -> Falih ->
[Budi] berteman dengan: Citra -> Falih ->
[Citra] berteman dengan: Budi -> Andi -> Hint: Cara Mengakses Nama
StrukturEdgeNodehanya menyimpan angka indeks saja (destVertex). Untuk mencetak namanya, gunakan indeks tersebut untuk mengintip kembali ke Array nama simpul:cout << G.vertices[temp->destVertex] << " -> ";.