Hammaga salom.
Ushbu eslatmada men kompyuter fanida grafiklarni saqlash uchun ishlatiladigan asosiy ma'lumotlar tuzilmalarini sanab o'tishga qaror qildim va men uchun qandaydir tarzda "kristallangan" yana bir nechta tuzilmalar haqida gapirib beraman.
Shunday ekan, boshlaylik. Lekin boshidanoq emas - o'ylaymanki, biz hammamiz allaqachon grafik nima ekanligini va ular nima ekanligini bilamiz (yo'naltirilgan, yo'naltirilmagan, vaznli, vaznsiz, bir nechta qirralar va halqalar bilan yoki ularsiz).
Xo'sh, ketaylik. Bizda "grafik saqlash" uchun ma'lumotlar tuzilmalari uchun qanday imkoniyatlar mavjud?
1. Matritsali ma’lumotlar tuzilmalari
1.1 Qo'shnilik matritsasi. Qo'shni matritsa - bu matritsa bo'lib, unda satr va ustun sarlavhalari grafikning uchlari soniga to'g'ri keladi va uning har bir elementining qiymati a(i,j) cho'qqilar orasidagi qirralarning mavjudligi yoki yo'qligi bilan belgilanadi. i va j (yo'naltirilmagan grafik uchun bunday matritsa nosimmetrik bo'lishi aniq yoki biz barcha qiymatlarni faqat asosiy diagonaldan yuqorida saqlashimizga rozi bo'lishimiz mumkin). Og'irlanmagan grafiklar uchun a(i,j) ni i dan j gacha bo'lgan qirralarning soni bo'yicha (agar bunday chekka bo'lmasa, a(i,j)= 0), vaznli grafiklar uchun esa og'irlik bo'yicha ham o'rnatilishi mumkin. ko'rsatilgan qirralarning (umumiy og'irligi).
1.2 Insidans matritsasi. Bunday holda, bizning grafikimiz, qoida tariqasida, satr raqamlari uning uchlari raqamlariga, ustun raqamlari esa oldindan raqamlangan qirralarga mos keladigan jadvalda saqlanadi. Agar cho'qqi va chekka bir-biriga to'g'ri keladigan bo'lsa, unda mos keladigan katakchaga nolga teng bo'lmagan qiymat yoziladi (yo'naltirilmagan grafiklar uchun, agar cho'qqi va chekka tushsa, 1 yoziladi, yo'naltirilganlar uchun - agar chekka bo'lsa - "1" Cho'qqidan "chiqish" va agar u "o'z ichiga olgan" bo'lsa, "-1" (eslab qolish juda oson, chunki "minus" belgisi ham "-1" raqamiga "qo'shilgan" ko'rinadi)). Og'irlangan grafiklar uchun yana 1 va -1 o'rniga siz chekkaning umumiy og'irligini belgilashingiz mumkin.
2. Hisoblash ma'lumotlari tuzilmalari
2.1 Qo'shnilar ro'yxati. Xo'sh, bu erda hamma narsa oddiy ko'rinadi. Grafikning har bir cho'qqisi, umuman olganda, har qanday sanab tuzilmasi (ro'yxat, vektor, massiv, ...) bilan bog'lanishi mumkin, bu esa berilganiga ulashgan barcha cho'qqilarning raqamlarini saqlaydi. Yo'naltirilgan grafiklar uchun biz bunday ro'yxatga faqat xususiyat cho'qqisidan "yo'naltirilgan" qirrasi bo'lgan cho'qqilarni qo'shamiz. Og'irlangan grafiklar uchun amalga oshirish yanada murakkab bo'ladi.
2.2 Qovurg'alar ro'yxati. Juda mashhur ma'lumotlar tuzilmasi. Kapitan Obviousness bizga aytganidek, qirralarning ro'yxati aslida grafik qirralarining ro'yxati bo'lib, ularning har biri boshlang'ich cho'qqi, yakuniy cho'qqi bilan belgilanadi (yo'naltirilmagan grafiklar uchun bu erda tartib muhim emas, lekin birlashtirish uchun siz turli qoidalardan foydalaning, masalan, cho'qqilarni oshirish tartibida belgilash) va og'irlik (faqat vaznli grafiklar uchun).
Yuqorida sanab o'tilgan matritsalar ro'yxatini batafsilroq ko'rishingiz mumkin (va rasmlar bilan), masalan, .
2.3 Qo'shnilik massivi. Eng keng tarqalgan tuzilma emas. Asosan, bu qo'shni ro'yxatlarni bitta ro'yxat tuzilmasi (massiv, vektor)ga "qadoqlash" shaklidir. Bunday massivning birinchi n (grafik uchlari soniga ko'ra) elementlari bir xil massivning boshlang'ich indekslarini o'z ichiga oladi, undan boshlab berilganiga qo'shni barcha uchlari qatorga yoziladi.
Bu erda men eng tushunarli (o'zim uchun) tushuntirishni topdim:
3. Qo‘shnilik vektori va assotsiativ qo‘shnilik massivi
Ma'lum bo'lishicha, ushbu satrlarning muallifi professional dasturchi bo'lmagan, lekin vaqti-vaqti bilan grafikalar bilan shug'ullangan, ko'pincha qirralarning ro'yxati bilan shug'ullangan. Haqiqatan ham, agar grafikda bir nechta halqa va qirralar bo'lsa, bu qulay. Shunday qilib, qirralarning klassik ro'yxatini ishlab chiqishda men ularning "rivojlanish/tarmoq/modifikatsiya/mutatsiya", ya'ni qo'shnilik vektori va assotsiativ qo'shnilik massiviga e'tibor berishni taklif qilaman.
3.1 Qo'shnilik vektori
Holat (a1): tortilmagan grafik
Tartibga solinmagan butun sonli (a[2i], a[2i+1],..., bu yerda i c 0 bilan raqamlangan), har bir juft sondan iborat tartiblangan to‘plamni tortilmagan grafik uchun qo‘shnilik vektori deb ataymiz. a[2i], a[2i+1 ] mos ravishda a[2i] va a[2i+1] uchlari orasidagi grafik chetini belgilaydi.
Ushbu yozib olish formati grafik yo'naltirilganligi haqida ma'lumotni o'z ichiga olmaydi (har ikkala variant ham mumkin). Digraf formatidan foydalanilganda chekka a[2i] dan a[2i+1] gacha yo'naltirilgan deb hisoblanadi. Bu erda va quyida: yo'naltirilmagan grafiklar uchun, agar kerak bo'lsa, cho'qqilarni yozish tartibiga qo'yiladigan talablar qo'llanilishi mumkin (masalan, unga tayinlangan raqamning pastki qiymatiga ega cho'qqi birinchi o'rinda turadi).
C++ da qo'shnilik vektorini std::vector yordamida ko'rsatish maqsadga muvofiq, shuning uchun bu ma'lumotlar strukturasi nomi.
Holat (a2): tortilmagan grafik, chekka og'irliklari butun son
(a1) holiga o'xshatib, chekka og'irliklari butun sonli vaznli grafik uchun qo'shnilik vektorini raqamlarning tartiblangan to'plami (dinamik massiv) deb ataymiz (a[3i], a[3i+1], a[3i+2], ..., bu yerda i raqamlangan c 0), bu erda a[3i], a[3i+1], a[3i+2] raqamlarining har bir “uchligi” a[3i] sonli uchlari orasidagi grafikning chetini belgilaydi. va mos ravishda a[3i+1] va a [3i+2] qiymati bu chekkaning og'irligidir. Bunday grafik ham yo'naltirilishi mumkin yoki yo'q.
Hol (b): tortilmagan grafik, butun son bo'lmagan chekka og'irliklari
Heterojen elementlarni bitta massivda (vektorda) saqlash mumkin emasligi sababli, masalan, quyidagi amalga oshirish mumkin. Grafik vektorlar juftligida saqlanadi, unda birinchi vektor og'irliklarni ko'rsatmasdan grafikning qo'shnilik vektori, ikkinchi vektor esa mos keladigan og'irliklarni o'z ichiga oladi (C++: std::pair uchun amalga oshirilishi mumkin). ). Shunday qilib, birinchi vektorning 2i, 2i+1 indekslari ostidagi juft cho'qqilar bilan aniqlangan chekka uchun og'irlik ikkinchi vektorning i indeksi ostidagi elementga teng bo'ladi.
Xo'sh, bu nima uchun kerak?
Xo'sh, ushbu satrlar muallifi uni bir qator muammolarni hal qilish uchun juda foydali deb topdi. Xo'sh, rasmiy nuqtai nazardan, quyidagi afzalliklar bo'ladi:
- Qo'shnilik vektori, boshqa har qanday "hisoblash" tuzilmasi kabi, juda ixcham, qo'shnilik matritsasiga qaraganda kamroq xotirani egallaydi (siyrak grafiklar uchun) va amalga oshirish nisbatan oson.
- Grafikning uchlari, qoida tariqasida, manfiy raqamlar bilan ham belgilanishi mumkin. Agar bunday "buzilish" kerak bo'lsa-chi?
- Grafiklar turli og'irliklarga ega (musbat, salbiy, hatto nol) bir nechta qirralar va bir nechta halqalarni o'z ichiga olishi mumkin. Bu erda hech qanday cheklovlar yo'q.
- Bundan tashqari, qirralarga turli xususiyatlarni belgilashingiz mumkin - ammo bu haqda ko'proq ma'lumot olish uchun 4-bo'limga qarang.
Biroq, tan olish kerakki, ushbu "ro'yxat" chekkaga tezkor kirishni anglatmaydi. Va bu erda Associative Adjacency Array yordamga keladi, bu quyida muhokama qilinadi.
3.2 Assotsiativ qo'shnilik massivi
Shunday qilib, agar ma'lum bir chekkaga kirish, uning og'irligi va boshqa xususiyatlari biz uchun juda muhim bo'lsa va xotira talablari qo'shnilik matritsasidan foydalanishga imkon bermasa, unda bu muammoni hal qilish uchun qo'shnilik vektorini qanday o'zgartirishimiz haqida o'ylab ko'raylik. Demak, kalit tartiblangan butun sonlar juftligi sifatida belgilanishi mumkin bo'lgan grafikning chetidir. Bu nimaga o'xshaydi? Bu assotsiativ massivdagi kalit emasmi? Va agar shunday bo'lsa, nega biz buni amalga oshirmaymiz? Keling, assotsiativ massivga ega bo'lsin, unda har bir kalit - tartiblangan butun sonlar juftligi - qiymat - butun son yoki chekka og'irligini belgilaydigan haqiqiy son bilan bog'lanadi. C++ tilida ushbu tuzilmani std::map konteyneri (std::map) asosida amalga oshirish maqsadga muvofiqdir. , int> yoki std::map , double>), yoki std::multimap, agar bir nechta qirralar kutilsa. Xo'sh, bizda "matritsa" tuzilmalariga qaraganda kamroq xotirani egallaydigan grafiklarni saqlash uchun tuzilma mavjud, grafiklarni bir nechta halqa va qirralar bilan aniqlay oladi va hatto tepalik raqamlarining manfiy bo'lmasligi uchun qat'iy talablarga ega emas (bilmayman). Bu kimga kerak, lekin baribir).
4. Ma'lumotlar tuzilmalari to'la, lekin nimadir etishmayapti
Va bu haqiqat: bir qator muammolarni hal qilishda biz grafikning chetlariga ba'zi xususiyatlarni belgilashimiz va shunga mos ravishda ularni saqlashimiz kerak bo'lishi mumkin. Agar bu xususiyatlarni butun sonlarga aniq qisqartirish mumkin bo'lsa, u holda qo'shnilik vektori va assotsiativ qo'shnilik massivining kengaytirilgan versiyalari yordamida bunday "qo'shimcha funktsiyalarga ega grafiklarni" saqlash mumkin.
Shunday qilib, har bir chekka uchun, masalan, butun sonlar bilan belgilangan 2 ta qo'shimcha xususiyatni saqlash kerak bo'lgan tortilmagan grafikga ega bo'lamiz. Bunday holda, uning qo'shnilik vektorini "juftlar" emas, balki butun sonlarning "kvartetlari" (a[2i], a[2i+1], a[2i+2], a) tartiblangan to'plami sifatida aniqlash mumkin. [2i+3]…) , bu erda a[2i+2] va a[2i+3] mos keladigan chekka xarakteristikalarini aniqlaydi. Qirralarning butun ogʻirliklari boʻlgan grafik uchun tartib odatda oʻxshashdir (farq shundaki, atributlar chekka ogʻirligiga mos keladi va a[2i+3] va a[2i+4] elementlari bilan belgilanadi. , va chekkaning o'zi 4 emas, balki 5 tartibli raqam ko'rsatiladi). Butun son bo'lmagan chekka og'irliklari bo'lgan grafik uchun xususiyatlar uning tortilmagan komponentiga yozilishi mumkin.
Butun sonli chekka og'irliklari bo'lgan grafiklar uchun assotsiativ qo'shnilik massividan foydalanganda, qiymat sifatida bitta raqamni emas, balki chekka og'irligiga qo'shimcha ravishda uning boshqa barcha zarurligini ko'rsatadigan raqamlar qatorini (vektorini) ko'rsatish mumkin. Xususiyatlari. Shu bilan birga, butun son bo'lmagan og'irliklar holati uchun noqulaylik suzuvchi nuqta raqami bilan belgini ko'rsatish zarurati bo'ladi (ha, bu noqulaylik, lekin agar bunday belgilar unchalik ko'p bo'lmasa va agar siz 'Ularni juda "hiyla" ikki barobarga o'rnatmang, keyin hech narsa bo'lmasligi mumkin). Bu shuni anglatadiki, C++ da kengaytirilgan assotsiativ qo'shni massivlarni quyidagicha aniqlash mumkin: std::map , std::vector> yoki std::map , std::vektor, unda "kalit-qiymat-vektor" dagi birinchi qiymat chekka og'irligi bo'ladi, so'ngra uning xarakteristikasining raqamli belgilari joylashgan.
Adabiyot:
Grafiklar va umuman algoritmlar haqida:
1. Kormen, Tomas X., Leiserson, Charlz I., Rivest, Ronald L., Stein, Klifford. Algoritmlar: qurish va tahlil qilish, 2-nashr: Trans. ingliz tilidan - M.: Uilyams nashriyoti, 2011 yil.
2. Harari Frank. Grafik nazariyasi. M.: Mir, 1973 yil.
Xuddi shu vektor va qo'shnilarning assotsiativ massivi haqida muallifning hisoboti:
3. Chernuxov S.A. Grafiklarni ko'rsatish va saqlash usullari sifatida qo'shnilik vektori va assotsiativ qo'shnilik massivi / SA Chernouhov. Qo'shnilik vektori va qo'shnilik xaritasi grafikni ifodalash uchun ma'lumotlar tuzilmalari sifatida // "Innovatsion ishlanmalar natijalarini joriy etish muammolari va ularni hal qilish yo'llari" Xalqaro ilmiy-amaliy konferentsiya maqolalari to'plami (Saratov, 14.09.2019 yil 2019 sentyabr). – Sterlitamak: AMI, 65, p. 69-XNUMX
Mavzu bo'yicha foydali onlayn manbalar:
4.
5.
Manba: www.habr.com