Halo.
Dalam catatan ini, saya memutuskan untuk membuat daftar struktur data utama yang digunakan untuk menyimpan grafik dalam ilmu komputer, dan saya juga akan berbicara tentang beberapa struktur lagi yang entah bagaimana “mengkristal” untuk saya.
Jadi, mari kita mulai. Namun tidak sejak awal - saya rasa kita semua sudah mengetahui apa itu grafik dan apa itu grafik (berarah, tidak berarah, berbobot, tidak berbobot, dengan atau tanpa banyak sisi dan loop).
Jadi ayo pergi. Opsi struktur data apa untuk “penyimpanan grafik” yang kita miliki?
1. Struktur data matriks
1.1 Matriks ketetanggaan. Matriks ketetanggaan adalah matriks yang judul baris dan kolomnya sesuai dengan banyaknya simpul pada graf tersebut, dan nilai setiap elemennya a(i,j) ditentukan oleh ada tidaknya sisi antar simpul. i dan j (jelas bahwa untuk graf tidak berarah matriks seperti itu akan simetris, atau kita setuju bahwa kita menyimpan semua nilai hanya di atas diagonal utama). Untuk graf tak berbobot, a(i,j) dapat ditentukan dengan jumlah sisi dari i hingga j (jika tidak ada sisi seperti itu, maka a(i,j)= 0), dan untuk graf berbobot, juga dengan bobotnya (berat total) dari tepi yang disebutkan.
1.2 Matriks insiden. Dalam hal ini, grafik kita juga disimpan dalam tabel yang, biasanya, nomor baris sesuai dengan jumlah simpulnya, dan nomor kolom sesuai dengan sisi yang telah diberi nomor sebelumnya. Jika sebuah titik dan sisi saling bersinggungan, maka nilai bukan nol dituliskan pada sel yang bersesuaian (untuk graf tak berarah, 1 ditulis jika simpul dan sisinya bersisian, untuk graf berorientasi - “1” jika sisinya “keluar” dari titik puncak dan “-1” jika “termasuk” di dalamnya (cukup mudah diingat, karena tanda “minus” juga seolah-olah “termasuk” pada angka “-1”)). Untuk grafik berbobot, sekali lagi, alih-alih 1 dan -1, Anda dapat menentukan bobot total tepinya.
2. Struktur data enumerasi
2.1 Daftar kedekatan. Ya, semuanya tampak sederhana di sini. Setiap simpul pada suatu graf, secara umum, dapat diasosiasikan dengan struktur enumerasi apa pun (daftar, vektor, larik, ...), yang akan menyimpan jumlah semua simpul yang berdekatan dengan simpul tertentu. Untuk graf berarah, ke dalam daftar tersebut kita hanya akan menambahkan simpul-simpul yang memiliki sisi “terarah” dari simpul fitur. Untuk grafik berbobot penerapannya akan lebih kompleks.
2.2 Daftar tulang rusuk. Struktur data yang cukup populer. Daftar tepi, seperti yang dikatakan Captain Obviousness kepada kita, sebenarnya adalah daftar tepi suatu graf, yang masing-masing ditentukan oleh simpul awal, simpul akhir (untuk graf tak berarah, urutannya tidak penting di sini, meskipun untuk penyatuan Anda bisa menggunakan berbagai aturan, misalnya menentukan simpul secara berurutan) dan bobot (hanya untuk graf berbobot).
Anda dapat melihat daftar matriks yang tercantum di atas secara lebih rinci (dan disertai ilustrasi), misalnya, .
2.3 Array kedekatan. Bukan struktur yang paling umum. Intinya, ini adalah bentuk “pengemasan” daftar kedekatan ke dalam satu struktur enumerasi (array, vektor). Elemen n pertama (sesuai dengan jumlah simpul pada grafik) dari larik tersebut berisi indeks awal dari larik yang sama, mulai dari mana semua simpul yang berdekatan dengan simpul tertentu ditulis dalam satu baris.
Di sini saya menemukan penjelasan yang paling bisa dimengerti (untuk saya sendiri):
3. Vektor Kedekatan dan Array Kedekatan Asosiatif
Ternyata penulis baris-baris ini, bukan seorang programmer profesional, tetapi yang secara berkala berurusan dengan grafik, paling sering berurusan dengan daftar tepian. Memang, akan lebih mudah jika grafik memiliki banyak loop dan sisi. Jadi, dalam pengembangan daftar tepi klasik, saya mengusulkan untuk memperhatikan “pengembangan/cabang/modifikasi/mutasinya”, yaitu: vektor ketetanggaan dan larik ketetanggaan asosiatif.
3.1 Vektor kedekatan
Kasus (a1): grafik tidak berbobot
Kita akan menyebut vektor ketetanggaan untuk graf tak berbobot sebagai himpunan terurut dari bilangan bulat genap (a[2i], a[2i+1],..., di mana i diberi nomor c 0), di mana setiap pasangan bilangan adalah a[2i], a[2i+1 ] menentukan tepi grafik antara simpul a[2i] dan a[2i+1], masing-masing.
Format rekaman ini tidak berisi informasi apakah grafiknya berarah (kedua opsi dimungkinkan). Bila menggunakan format digraf, sisi dianggap berarah dari a[2i] ke a[2i+1]. Di sini dan di bawah: untuk graf tak berarah, jika perlu, persyaratan urutan pencatatan simpul dapat diterapkan (misalnya, simpul dengan nilai lebih rendah dari bilangan yang ditetapkan didahulukan).
Dalam C++, disarankan untuk menentukan vektor kedekatan menggunakan std::vector, karena itulah nama struktur data ini.
Kasus (a2): graf tak berbobot, bobot sisi adalah bilangan bulat
Dengan analogi dengan kasus (a1), kita menyebut vektor ketetanggaan untuk graf berbobot dengan bobot tepi bilangan bulat sebagai himpunan bilangan terurut (array dinamis) (a[3i], a[3i+1], a[3i+2], ..., dimana i diberi nomor c 0), dimana setiap “triplet” dari bilangan a[3i], a[3i+1], a[3i+2] menentukan sisi dari graf antara simpul-simpul bernomor a[3i] dan a[3i+1], masing-masing, dan nilai a [3i+2] adalah bobot sisi ini. Grafik seperti itu juga bisa berarah atau tidak.
Kasus (b): graf tak berbobot, bobot sisi bukan bilangan bulat
Karena tidak mungkin menyimpan elemen heterogen dalam satu larik (vektor), misalnya, implementasi berikut dapat dilakukan. Grafik disimpan dalam sepasang vektor, di mana vektor pertama adalah vektor ketetanggaan grafik tanpa menentukan bobot, dan vektor kedua berisi bobot yang sesuai (kemungkinan implementasi untuk C++: std::pair ). Jadi, untuk suatu sisi yang didefinisikan oleh sepasang simpul dengan indeks 2i, 2i+1 dari vektor pertama, bobotnya akan sama dengan elemen di bawah indeks i dari vektor kedua.
Nah, mengapa hal ini perlu?
Nah, penulis baris-baris ini menganggapnya cukup berguna untuk memecahkan sejumlah masalah. Nah, dari segi formal, keuntungannya adalah sebagai berikut:
- Vektor ketetanggaan, seperti struktur “enumeratif” lainnya, cukup kompak, menggunakan lebih sedikit memori dibandingkan matriks ketetanggaan (untuk grafik renggang), dan relatif mudah diimplementasikan.
- Titik-titik pada suatu graf pada prinsipnya juga dapat ditandai dengan angka negatif. Bagaimana jika “penyimpangan” seperti itu diperlukan?
- Grafik dapat berisi banyak sisi dan banyak loop, dengan bobot berbeda (positif, negatif, bahkan nol). Tidak ada batasan di sini.
- Anda juga dapat menetapkan properti yang berbeda ke tepi - namun untuk informasi lebih lanjut, lihat bagian 4.
Namun, harus diakui bahwa “daftar” ini tidak berarti akses cepat ke edge. Dan di sinilah Associative Adjacency Array datang untuk menyelamatkan, yang dibahas di bawah.
3.2 Array kedekatan asosiatif
Jadi, jika akses ke edge tertentu, bobotnya, dan properti lainnya sangat penting bagi kita, dan kebutuhan memori tidak memungkinkan kita menggunakan matriks ketetanggaan, maka mari kita pikirkan bagaimana kita dapat mengubah vektor ketetanggaan untuk menyelesaikan masalah ini. Jadi, kuncinya adalah sisi grafik, yang dapat ditentukan sebagai pasangan bilangan bulat terurut. Ini kelihatannya seperti apa? Bukankah ini kunci dalam array asosiatif? Dan jika demikian, mengapa kita tidak menerapkannya? Mari kita memiliki array asosiatif di mana setiap kunci - pasangan bilangan bulat terurut - akan dikaitkan dengan nilai - bilangan bulat atau bilangan real yang menentukan bobot tepi. Dalam C++, disarankan untuk mengimplementasikan struktur ini berdasarkan wadah std::map (std::map , int> atau std::peta , double>), atau std::multimap jika diharapkan ada banyak sisi. Ya, kami memiliki struktur untuk menyimpan grafik yang memakan lebih sedikit memori daripada struktur "matriks", dapat mendefinisikan grafik dengan banyak loop dan tepi, dan bahkan tidak memiliki persyaratan ketat untuk bilangan simpul non-negatif (saya tidak tahu siapa yang membutuhkan ini, tapi tetap saja).
4. Struktur data sudah penuh, tetapi ada yang kurang
Dan memang benar: saat memecahkan sejumlah masalah, kita mungkin perlu menetapkan beberapa karakteristik pada tepi grafik dan, karenanya, menyimpannya. Jika memungkinkan untuk mereduksi fitur-fitur ini menjadi bilangan bulat, maka dimungkinkan untuk menyimpan "grafik dengan fitur tambahan" tersebut menggunakan versi yang diperluas dari vektor ketetanggaan dan larik ketetanggaan asosiatif.
Jadi, mari kita memiliki graf tak berbobot, yang untuk setiap sisinya perlu disimpan, misalnya, 2 fitur tambahan yang ditentukan oleh bilangan bulat. Dalam hal ini, vektor ketetanggaannya dapat didefinisikan sebagai himpunan terurut bukan dari “pasangan”, melainkan “kuartet” bilangan bulat (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , di mana a[2i+2] dan a[2i+3] akan menentukan karakteristik sisi yang bersesuaian. Untuk graf dengan bobot sisi bilangan bulat, urutannya secara umum sama (perbedaannya hanya pada atribut yang mengikuti bobot sisi dan ditentukan oleh elemen a[2i+3] dan a[2i+4] , dan tepinya sendiri akan ditentukan bukan 4, tetapi 5 nomor terurut). Dan untuk graf yang bobot sisinya bukan bilangan bulat, fitur-fiturnya dapat dituliskan ke dalam komponen tak berbobotnya.
Saat menggunakan larik ketetanggaan asosiatif untuk graf dengan bobot tepi bilangan bulat, dimungkinkan untuk menetapkan nilai bukan hanya satu angka, tetapi larik (vektor) angka yang menentukan, selain bobot suatu tepi, semua hal lain yang diperlukan. fitur. Pada saat yang sama, ketidaknyamanan untuk kasus bobot non-integer adalah kebutuhan untuk menentukan tanda dengan bilangan floating point (ya, ini adalah ketidaknyamanan, tetapi jika tanda seperti itu tidak banyak, dan jika Anda tidak 'jangan atur terlalu "rumit" ganda, maka itu mungkin bukan apa-apa) . Ini berarti bahwa dalam C++ array kedekatan asosiatif yang diperluas dapat didefinisikan sebagai berikut: std::map , std::vector> atau std::map , std::vector, di mana nilai pertama dalam "vektor nilai kunci" akan menjadi bobot tepi, dan kemudian penandaan numerik dari karakteristiknya ditempatkan.
Literatur:
Tentang grafik dan algoritma secara umum:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritma: konstruksi dan analisis, edisi ke-2: Trans. dari bahasa Inggris – M.: Rumah Penerbitan Williams, 2011.
2. Harari Frank. Teori grafik. M.: Mir, 1973.
Laporan penulis tentang vektor yang sama dan susunan kedekatan asosiatif:
3. Chernoukhov S.A. Vektor ketetanggaan dan larik ketetanggaan asosiatif sebagai cara untuk merepresentasikan dan menyimpan grafik / SA Chernouhov. Vektor ketetanggaan dan peta ketetanggaan sebagai struktur data untuk merepresentasikan grafik // Kumpulan artikel Konferensi Ilmiah dan Praktis Internasional “Masalah implementasi hasil pengembangan inovatif dan cara penyelesaiannya” (Saratov, 14.09.2019 September 2019). – Sterlitamak: AMI, 65, hal. 69-XNUMX
Sumber online yang berguna tentang topik ini:
4.
5.
Sumber: www.habr.com