Helo semua.
Dalam nota ini, saya memutuskan untuk menyenaraikan struktur data utama yang digunakan untuk menyimpan graf dalam sains komputer, dan saya juga akan bercakap tentang beberapa lagi struktur sedemikian yang entah bagaimana "menghablur" untuk saya.
Jadi, mari kita mulakan. Tetapi bukan dari awal lagi - Saya rasa kita semua sudah tahu apa itu graf dan apakah graf itu (diarahkan, tidak terarah, berwajaran, tidak berwajaran, dengan atau tanpa berbilang tepi dan gelung).
Jadi, mari kita pergi. Apakah pilihan untuk struktur data untuk "storan graf" yang kita ada?
1. Struktur data matriks
1.1 Matriks bersebelahan. Matriks bersebelahan ialah matriks di mana tajuk baris dan lajur sepadan dengan nombor bucu graf, dan nilai setiap unsurnya a(i,j) ditentukan oleh kehadiran atau ketiadaan tepi antara bucu i dan j (jelas bahawa untuk graf tidak terarah, matriks sedemikian akan simetri, atau kita boleh bersetuju bahawa kita menyimpan semua nilai hanya di atas pepenjuru utama). Untuk graf tidak berwajaran, a(i,j) boleh ditetapkan dengan bilangan tepi dari i hingga j (jika tiada tepi sedemikian, maka a(i,j)= 0), dan untuk graf berwajaran, juga mengikut berat (jumlah berat) tepi yang disebutkan.
1.2 Matriks kejadian. Dalam kes ini, graf kami juga disimpan dalam jadual di mana, sebagai peraturan, nombor baris sepadan dengan nombor bucunya, dan nombor lajur sepadan dengan tepi pranombor. Jika bucu dan tepi bersinggungan antara satu sama lain, maka nilai bukan sifar ditulis dalam sel yang sepadan (untuk graf tidak berarah, 1 ditulis jika bucu dan tepi bersinggungan, untuk graf berorientasikan - "1" jika tepi "keluar" dari puncak dan "-1" jika ia "termasuk" di dalamnya (ia cukup mudah untuk diingati, kerana tanda "tolak" juga nampaknya "disertakan" dalam nombor "-1")). Untuk graf berwajaran, sekali lagi, bukannya 1 dan -1, anda boleh menentukan jumlah berat tepi.
2. Struktur data pengiraan
2.1 Senarai bersebelahan. Nah, semuanya nampak mudah di sini. Setiap bucu graf, secara umum, boleh dikaitkan dengan mana-mana struktur penghitungan (senarai, vektor, tatasusunan, ...), yang akan menyimpan nombor semua bucu bersebelahan dengan yang diberikan. Untuk graf terarah, kami akan menambah pada senarai sedemikian hanya bucu yang terdapat tepi "diarahkan" daripada bucu ciri. Untuk graf berwajaran pelaksanaannya akan menjadi lebih kompleks.
2.2 Senarai tulang rusuk. Struktur data yang cukup popular. Senarai tepi, seperti yang Kapten Obviousness memberitahu kami, sebenarnya adalah senarai tepi graf, setiap satunya ditentukan oleh bucu permulaan, bucu penghujung (untuk graf tidak terarah susunannya tidak penting di sini, walaupun untuk penyatuan anda boleh gunakan pelbagai peraturan, contohnya, menentukan bucu dalam susunan meningkat) dan berat (untuk graf berwajaran sahaja).
Anda boleh melihat senarai matriks yang disenaraikan di atas dengan lebih terperinci (dan dengan ilustrasi), contohnya, .
2.3 Tatasusunan bersebelahan. Bukan struktur yang paling biasa. Pada terasnya, ia adalah satu bentuk "membungkus" senarai bersebelahan ke dalam satu struktur penghitungan (tatasusunan, vektor). Unsur n pertama (mengikut bilangan bucu graf) tatasusunan sedemikian mengandungi indeks permulaan tatasusunan yang sama, bermula dari mana semua bucu yang bersebelahan dengan yang diberikan ditulis dalam satu baris.
Di sini saya dapati penjelasan yang paling mudah difahami (untuk diri saya sendiri):
3. Vektor Bersebelahan dan Tatasusunan Bersebelahan
Ternyata pengarang baris ini, bukan pengaturcara profesional, tetapi yang secara berkala berurusan dengan graf, paling kerap berurusan dengan senarai tepi. Sesungguhnya, adalah mudah jika graf mempunyai berbilang gelung dan tepi. Oleh itu, dalam pembangunan senarai klasik tepi, saya mencadangkan untuk memberi perhatian kepada "pembangunan/cawangan/pengubahsuaian/mutasi" mereka, iaitu: vektor bersebelahan dan tatasusunan bersebelahan bersekutu.
3.1 Vektor bersebelahan
Kes (a1): graf tidak berwajaran
Kami akan memanggil vektor bersebelahan untuk graf tidak berwajaran sebagai set tertib bilangan integer genap (a[2i], a[2i+1],..., dengan i bernombor c 0), di mana setiap pasangan nombor ialah a[2i], a[2i+1 ] masing-masing menentukan tepi graf antara bucu a[2i] dan a[2i+1].
Format rakaman ini tidak mengandungi maklumat tentang sama ada graf diarahkan (kedua-dua pilihan adalah mungkin). Apabila menggunakan format digraf, tepi dianggap diarahkan dari a[2i] ke a[2i+1]. Di sini dan di bawah: untuk graf tidak terarah, jika perlu, keperluan untuk susunan bucu merekod boleh digunakan (contohnya, bucu dengan nilai yang lebih rendah daripada nombor yang diberikan kepadanya didahulukan).
Dalam C++, adalah dinasihatkan untuk menentukan vektor bersebelahan menggunakan std::vector, maka nama struktur data ini.
Kes (a2): graf tidak berwajaran, berat tepi ialah integer
Dengan analogi dengan kes (a1), kami memanggil vektor bersebelahan untuk graf berwajaran dengan pemberat tepi integer sebagai set tertib (tatasusunan dinamik) nombor (a[3i], a[3i+1], a[3i+2], ..., dengan i bernombor c 0), di mana setiap "triplet" nombor a[3i], a[3i+1], a[3i+2] menentukan tepi graf antara bucu bernombor a[3i] dan a[3i+1], masing-masing, dan nilai a [3i+2] ialah berat tepi ini. Graf sedemikian juga boleh sama ada diarahkan atau tidak.
Kes (b): graf tidak berwajaran, pemberat tepi bukan integer
Memandangkan adalah mustahil untuk menyimpan elemen heterogen dalam satu tatasusunan (vektor), sebagai contoh, pelaksanaan berikut adalah mungkin. Graf disimpan dalam sepasang vektor, di mana vektor pertama ialah vektor bersebelahan graf tanpa menyatakan pemberat, dan vektor kedua mengandungi pemberat yang sepadan (kemungkinan pelaksanaan untuk C++: std::pair ). Oleh itu, untuk tepi yang ditakrifkan oleh sepasang bucu di bawah indeks 2i, 2i+1 vektor pertama, beratnya akan sama dengan elemen di bawah indeks i vektor kedua.
Nah, mengapa ini perlu?
Nah, pengarang baris ini mendapati ia agak berguna untuk menyelesaikan beberapa masalah. Nah, dari sudut pandangan formal, akan ada kelebihan berikut:
- Vektor bersebelahan, seperti mana-mana struktur "penghitungan" yang lain, agak padat, mengambil kurang memori daripada matriks bersebelahan (untuk graf jarang), dan agak mudah untuk dilaksanakan.
- Bucu graf, pada dasarnya, juga boleh ditandakan dengan nombor negatif. Bagaimana jika "penyelewengan" sedemikian diperlukan?
- Graf boleh mengandungi berbilang tepi dan berbilang gelung, dengan pemberat yang berbeza (positif, negatif, malah sifar). Tiada sekatan di sini.
- Anda juga boleh menetapkan sifat yang berbeza pada tepi - tetapi untuk lebih lanjut tentang itu, lihat bahagian 4.
Walau bagaimanapun, mesti diakui bahawa "senarai" ini tidak membayangkan akses cepat ke tepi. Dan di sini Array Adjacency Bersekutu datang untuk menyelamatkan, yang dibincangkan di bawah.
3.2 Tatasusunan bersebelahan bersekutu
Jadi, jika akses kepada kelebihan tertentu, beratnya dan sifat-sifat lain adalah kritikal bagi kita, dan keperluan ingatan tidak membenarkan kita menggunakan matriks bersebelahan, maka mari kita fikirkan bagaimana kita boleh menukar vektor bersebelahan untuk menyelesaikan masalah ini. Jadi, kuncinya ialah pinggir graf, yang boleh ditentukan sebagai pasangan integer tertib. Apakah rupa ini? Bukankah ia kunci dalam tatasusunan bersekutu? Dan, jika ya, mengapa kita tidak melaksanakannya? Marilah kita mempunyai tatasusunan bersekutu di mana setiap kunci - pasangan integer tertib - akan dikaitkan dengan nilai - integer atau nombor nyata yang menentukan berat tepi. Dalam C++, adalah dinasihatkan untuk melaksanakan struktur ini berdasarkan bekas std::map (std::map , int> atau std::map , double>), atau std::multimap jika berbilang tepi dijangka. Nah, kami mempunyai struktur untuk menyimpan graf yang menggunakan kurang memori daripada struktur "matriks", boleh mentakrifkan graf dengan berbilang gelung dan tepi, malah tidak mempunyai keperluan yang ketat untuk bukan negatif nombor bucu (saya tidak tahu yang memerlukan ini, tetapi masih).
4. Struktur data penuh, tetapi ada yang hilang
Dan memang benar: apabila menyelesaikan beberapa masalah, kita mungkin perlu menetapkan beberapa ciri pada tepi graf dan, dengan itu, menyimpannya. Jika adalah mungkin untuk mengurangkan ciri ini dengan jelas kepada integer, maka adalah mungkin untuk menyimpan "graf dengan ciri tambahan" sedemikian menggunakan versi lanjutan vektor bersebelahan dan tatasusunan bersebelahan bersekutu.
Jadi, marilah kita mempunyai graf tidak berwajaran, untuk setiap tepi yang perlu disimpan, sebagai contoh, 2 ciri tambahan yang ditentukan oleh integer. Dalam kes ini, adalah mungkin untuk mentakrifkan vektor bersebelahannya sebagai set tertib bukan "pasangan", tetapi "kuartet" integer (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , di mana a[2i+2] dan a[2i+3] akan menentukan ciri-ciri tepi sepadan. Untuk graf dengan berat integer tepi, susunannya secara amnya serupa (satu-satunya perbezaan adalah hakikat bahawa atribut akan mengikut berat tepi dan akan ditentukan oleh unsur a[2i+3] dan a[2i+ 4], dan tepi itu sendiri akan ditentukan bukan 4, tetapi 5 nombor tertib). Dan untuk graf dengan pemberat tepi bukan integer, ciri boleh ditulis ke dalam komponen tidak berwajarannya.
Apabila menggunakan tatasusunan bersebelahan bersekutu untuk graf dengan pemberat tepi integer, adalah mungkin untuk menentukan sebagai nilai bukan nombor tunggal, tetapi tatasusunan (vektor) nombor yang menentukan, sebagai tambahan kepada berat tepi, semua nilai lain yang diperlukan ciri-ciri. Pada masa yang sama, kesulitan untuk kes pemberat bukan integer adalah keperluan untuk menentukan tanda dengan nombor titik terapung (ya, ini adalah kesulitan, tetapi jika tidak terdapat begitu banyak tanda sedemikian, dan jika anda tidak 't set mereka terlalu “tricky” double, maka ia mungkin tiada apa-apa) . Ini bermakna bahawa dalam C++ tatasusunan bersebelahan bersekutu lanjutan boleh ditakrifkan seperti berikut: std::map , std::vector> atau std::map , std::vector, di mana nilai pertama dalam "key-value-vector" akan menjadi berat tepi, dan kemudian penetapan berangka ciri-cirinya terletak.
kesusasteraan:
Mengenai graf dan algoritma secara umum:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritma: pembinaan dan analisis, edisi ke-2: Trans. dari bahasa Inggeris – M.: Rumah Penerbitan Williams, 2011.
2. Harari Frank. Teori graf. M.: Mir, 1973.
Laporan pengarang tentang vektor yang sama dan tatasusunan bersekutu ini:
3. Chernoukhov S.A. Vektor bersebelahan dan tatasusunan bersebelahan bersekutu sebagai cara untuk mewakili dan menyimpan graf / SA Chernouhov. Vektor bersebelahan dan peta bersebelahan sebagai struktur data untuk mewakili graf // Koleksi artikel Persidangan Saintifik dan Praktikal Antarabangsa "Masalah melaksanakan hasil pembangunan inovatif dan cara untuk menyelesaikannya" (Saratov, 14.09.2019 September 2019). – Sterlitamak: AMI, 65, hlm. 69-XNUMX
Sumber dalam talian yang berguna mengenai topik:
4.
5.
Sumber: www.habr.com