Struktur data untuk penyimpanan grafik: review dari yang sudah ada dan dua "hampir baru"

Halo semuanya.

Dalam catatan ini, saya memutuskan untuk membuat daftar struktur data utama yang digunakan untuk menyimpan grafik dalam ilmu komputer, dan juga berbicara tentang beberapa struktur lain yang entah bagaimana mengkristal oleh saya.

Jadi mari kita mulai. Tapi tidak sejak awal - saya pikir apa itu grafik dan apa mereka (berorientasi, tidak berorientasi, tertimbang, tidak berbobot, dengan banyak sisi dan loop atau tanpa mereka), kita semua sudah tahu.

Jadi ayo pergi. Apa saja opsi untuk struktur data untuk "penyimpanan grafik" yang kami miliki.

1. Struktur data matriks

1.1 matriks Adjacency. Matriks adjacency adalah matriks di mana judul baris dan kolom sesuai dengan jumlah simpul dari grafik, dan nilai setiap elemennya a (i, j) ditentukan oleh ada atau tidaknya tepi antara simpul i dan j (jelas bahwa matriks tersebut untuk grafik tidak terarah akan simetris, baik, atau Anda dapat setuju bahwa kami menyimpan semua nilai hanya di atas diagonal utama). Untuk grafik tanpa bobot, a (i, j) dapat ditentukan dengan jumlah tepi dari i ke j (jika tidak ada tepi tersebut, maka a (i, j) = 0), dan untuk yang berbobot, juga dengan berat (total berat) dari tepi yang disebutkan.

1.2 Matriks kejadian. Dalam hal ini, grafik kami juga disimpan dalam sebuah tabel, di mana, sebagai aturan, nomor baris sesuai dengan jumlah simpulnya, dan nomor kolom sesuai dengan tepi yang telah ditentukan sebelumnya. Jika titik dan tepi saling berhadapan, maka nilai bukan nol ditulis dalam sel yang sesuai (untuk grafik tidak berarah, 1 ditulis dalam kasus timbulnya titik dan tepi, untuk grafik berorientasi "1" jika tepi "meninggalkan" titik dan "-1" jika itu itu "masuk" (itu dikenang dengan mudah, karena tanda minus juga tampaknya "termasuk" dalam angka "-1")). Untuk grafik berbobot, sekali lagi, alih-alih 1 dan -1, Anda dapat menentukan berat total tepi.

2. Struktur data enumerasi

2.1 daftar kedekatan. Yah, semuanya tampak sederhana. Secara umum, setiap simpul grafik dapat dikaitkan dengan setiap struktur enumerasi (daftar, vektor, array, ...), di mana jumlah semua simpul yang berdekatan dengan ini akan disimpan. Untuk grafik berorientasi, kami hanya akan mencantumkan simpul di mana ada tepi "diarahkan" dari atribut-simpul. Untuk grafik berbobot, implementasinya akan lebih kompleks.

2.2 Daftar tulang rusuk. Struktur data yang cukup populer. Daftar tepi, seperti yang dikatakan Kapten Evidence, sebenarnya adalah daftar tepi grafik, yang masing-masing didefinisikan oleh titik awal, titik akhir (untuk grafik tidak berarah, urutannya tidak penting di sini, meskipun aturan yang berbeda dapat digunakan untuk penyatuan, misalnya, tentukan simpul dalam urutan naik) dan berat (hanya untuk grafik tertimbang).

Tentang daftar matriks yang tercantum di atas, Anda dapat melihat (misalnya, di sini ) lebih terinci.

2.3 Adjacency Array. Bukan struktur yang paling umum. Pada intinya, ini adalah bentuk daftar adjacency "pengepakan" menjadi satu struktur enumerasi (array, vektor). Elemen pertama n (berdasarkan jumlah simpul grafik) dari array tersebut berisi indeks awal dari array yang sama, mulai dari mana semua simpul yang berdekatan dengan ini dituliskan dalam satu baris.

Di sini saya menemukan penjelasan yang paling dapat dimengerti (untuk diri saya sendiri): ejuo.livejournal.com/4518.html

3. Vektor Adjacency dan Array Adjacency Asosiatif

Itu terjadi sehingga penulis baris ini, bukan menjadi programmer profesional, tetapi secara berkala berurusan dengan grafik, paling sering berurusan dengan daftar tepi. Memang, akan lebih mudah jika grafik memiliki banyak loop dan edge. Dan sekarang, dalam pengembangan daftar tepi klasik, saya mengusulkan untuk memperhatikan "pengembangan / percabangan / modifikasi / mutasi" mereka, yaitu: vektor adjacency dan array asosiatif dari adjacency.

3.1 Adjacency vector

Kasus (A1): Hitungan Tidak Tertimbang

Kami akan memanggil vektor adjacency untuk grafik tidak tertimbang satu set yang teratur dari bilangan bulat genap (a [2i], a [2i + 1], ..., di mana saya diberi nomor c 0), di mana setiap pasangan angka a [2i], a [2i +1] menentukan tepi grafik antara masing-masing simpul a [2i] dan [2i + 1].
Format rekaman ini tidak mengandung informasi apakah grafik berorientasi (kedua opsi dimungkinkan). Saat menggunakan format digraf, diasumsikan bahwa tepi diarahkan dari [2i] ke [2i + 1]. Selanjutnya: untuk grafik tidak berarah, jika perlu, persyaratan untuk urutan simpul perekaman dapat diterapkan (misalnya, agar simpul dengan nilai lebih rendah dari jumlah yang ditetapkan untuknya berjalan lebih dulu).

Dalam C ++, disarankan untuk menentukan vektor adjacency menggunakan std :: vector, dari mana nama struktur data ini dipilih.

Kasus (a2): grafik tidak tertimbang, bobot tepi integer

Dengan analogi dengan case (a1), kita memanggil vektor adjacency untuk grafik berbobot dengan bobot edge integer suatu himpunan yang diatur (array dinamis) angka (a [3i], a [3i + 1], [3i + 2], ..., di mana saya diberi nomor c 0), di mana setiap "triplet" dari angka a [3i], a [3i + 1], a [3i + 2] menentukan tepi grafik antara simpul di bawah angka a [3i] dan [3i +1 1], masing-masing, dan nilai [3i + 2] adalah bobot tepi ini. Grafik seperti itu juga bisa berorientasi atau tidak.

Kasing (b): grafik tidak berbobot, bobot tepi non-integer

Karena elemen heterogen tidak dapat disimpan dalam satu array (vektor), implementasi berikut dimungkinkan, misalnya. Grafik disimpan dalam sepasang vektor, di mana vektor pertama adalah vektor kedekatan dari grafik tanpa menunjukkan bobot, dan vektor kedua berisi bobot yang sesuai (kemungkinan implementasi untuk C ++ adalah: std :: pair <std :: vector, std :: vector>). Jadi, untuk tepi yang ditentukan oleh sepasang simpul di bawah indeks 2i, 2i + 1 dari vektor pertama, bobotnya akan sama dengan elemen di bawah indeks i dari vektor kedua.

Nah, mengapa ini perlu?

Nah, bagi penulis baris ini untuk memecahkan sejumlah masalah ini sepertinya cukup berguna. Nah, dari sudut pandang formal, akan ada keuntungan seperti itu:

• Vektor adjacency, seperti struktur "enumeratif" lainnya, cukup kompak, membutuhkan lebih sedikit memori daripada matriks adjacency (untuk grafik jarang), relatif mudah diimplementasikan.
• Verteks grafik, pada prinsipnya, dapat ditandai dengan angka negatif. Tiba-tiba, "penyimpangan" semacam itu juga dibutuhkan.
• Grafik dapat berisi banyak sisi dan banyak loop, dengan bobot berbeda (positif, negatif, bahkan nol). Tidak ada batasan di sini.
• Dan tulang rusuk dapat diberi properti yang berbeda - tetapi tentang ini, lihat paragraf 4.

Namun, saya harus akui, "listot" ini tidak menyiratkan akses cepat ke tulang rusuk. Dan di sini array kedekatan Asosiatif bergegas untuk membantu, tentang yang - di bawah ini.

3.2 Array kedekatan asosiatif

Jadi, jika bagi kita akses ke tepi tertentu, bobotnya dan properti lainnya sangat penting, dan persyaratan memori tidak memungkinkan penggunaan matriks adjacency, maka mari kita pikirkan tentang bagaimana Anda dapat mengubah vektor adjacency untuk menyelesaikan masalah ini. Jadi, kuncinya adalah tepi grafik, yang dapat didefinisikan sebagai pasangan bilangan bulat yang dipesan. Seperti apa bentuknya? Mungkinkah itu menjadi kunci dalam array asosiatif? Dan jika demikian, mengapa kita tidak menerapkannya? Mari kita memiliki array asosiatif, di mana setiap kunci - sepasang bilangan bulat yang dipesan - akan dikaitkan dengan nilai - bilangan bulat atau bilangan real yang menentukan bobot tepi. Dalam C ++, disarankan untuk mengimplementasikan struktur ini berdasarkan std :: map container (std :: map <std :: pair <int, int>, int> atau std :: map <std :: pair <int, int>, double>) , atau std :: multimap jika diasumsikan banyak sisi. Nah, dan di sini kita memiliki struktur untuk menyimpan grafik, yang membutuhkan lebih sedikit memori daripada struktur "matriks", dapat menentukan grafik dengan banyak loop dan tepi dan bahkan tanpa persyaratan ketat untuk non-negatif dari nomor vertex (saya tidak tahu siapa yang membutuhkannya, tapi tetap saja).

4. Struktur data setidaknya "banjir", tetapi ada sesuatu yang hilang

Dan kebenarannya adalah: ketika memecahkan sejumlah masalah, kita mungkin perlu menetapkan beberapa atribut ke tepi grafik dan, karenanya, untuk menyimpannya. Jika dimungkinkan untuk mereduksi fitur-fitur ini menjadi bilangan bulat, maka mungkin untuk menyimpan "grafik dengan fitur tambahan" menggunakan versi lanjutan dari vektor adjacency dan array adjacency asosiatif.

Jadi, mari kita memiliki grafik tanpa bobot, untuk setiap sisi yang perlu untuk menyimpan, misalnya, 2 tanda tambahan yang ditentukan oleh bilangan bulat. Dalam kasus ini, dimungkinkan untuk menentukan vektor kedekatannya sebagai sekumpulan urutan bukan "pasangan", tetapi "kuartet" bilangan bulat (a [2i], a [2i + 1], [2i + 2], [2i + 3] .. .), di mana [2i + 2] dan [2i + 3] akan menentukan fitur tepi yang sesuai. Untuk grafik dengan bobot tepi integer, urutan umumnya sama (satu-satunya perbedaan adalah bahwa tanda-tanda mengikuti berat tepi dan diberikan oleh elemen a [2i + 3] dan [2i + 4], dan tepi itu sendiri akan ditentukan bukan 4, tetapi 5 nomor yang dipesan). Dan untuk grafik dengan bobot tepi non-integer, atribut dapat ditulis ke komponen yang tidak berbobot.

Saat menggunakan array kedekatan asosiatif untuk grafik dengan bobot tepi integer, dimungkinkan untuk menentukan bukan angka individual, tetapi array (vektor) angka yang menentukan, selain bobot tepi, semua atribut lainnya yang diperlukan. Pada saat yang sama, ketidaknyamanan untuk kasus bobot non-integer akan menjadi kebutuhan untuk menentukan karakter dengan angka floating point (ya, ini adalah ketidaknyamanan, tetapi jika tidak ada begitu banyak tanda-tanda seperti itu, dan jika Anda tidak mengaturnya terlalu "rumit" ganda, maka itu mungkin bukan apa-apa) . Jadi, di C ++, array adjacency asosiatif yang diperluas dapat didefinisikan sebagai berikut: std :: map <std :: pair <int, int>, std :: vector> atau std :: map <std :: pair <int, int>, std :: vector, dengan nilai pertama dalam "vector-value-by-key" adalah bobot edge, dan kemudian penunjukan numerik fitur-fiturnya terletak.

Referensi:

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: Per. dari bahasa inggris - M .: Williams Publishing House, 2011.
2. Harari Frank. Teori grafik. M .: Mir, 1973.
Laporan penulis tentang vektor yang sama dan susunan asosiatif yang sama ini:
3. Chernoukhov S.A. Adjacency vector dan array adjacency asosiatif sebagai cara untuk mewakili dan menyimpan grafik / SA Chernouhov. Adjacency vector and adjacency map sebagai struktur data untuk merepresentasikan grafik // Kumpulan artikel dari konferensi ilmiah dan praktis internasional "Masalah penerapan hasil pengembangan inovatif dan cara untuk menyelesaikannya" (Saratov, 14 September 2019). - Sterlitamak: AMI, 2019, p. 65-69
Sumber-sumber Internet yang berguna tentang topik:
4.prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html