ProHoster > Blogs > Administrācija > Datu struktÅ«ras grafiku glabāŔanai: esoÅ”o un divu ā€œgandrÄ«z jaunuā€ apskats

Datu struktÅ«ras grafiku glabāŔanai: esoÅ”o un divu ā€œgandrÄ«z jaunuā€ apskats

Sveiki visiem

Å ajā piezÄ«mē es nolēmu uzskaitÄ«t galvenās datu struktÅ«ras, ko izmanto grafiku glabāŔanai datorzinātnēs, un es arÄ« runāŔu par vēl pāris Ŕādām struktÅ«rām, kas man kaut kā ā€œizkristalizējāsā€.

Tātad, sāksim. Bet ne jau no paÅ”a sākuma ā€“ es domāju, ka mēs visi jau zinām, kas ir grafs un kas tas ir (virzÄ«ts, nevirzÄ«ts, svērts, nesvērts, ar vai bez vairākām malām un cilpām).

Tātad, ejam. Kādas datu struktÅ«ras iespējas ā€œgrafu glabāŔanaiā€ mums ir?

1. Matricas datu struktūras

1.1 Blakus matrica. Blakus matrica ir matrica, kurā rindu un kolonnu virsraksti atbilst grafa virsotņu numuriem, un katra tās elementa vērtÄ«bu a(i,j) nosaka malu esamÄ«ba vai neesamÄ«ba starp virsotnēm. i un j (ir skaidrs, ka nevirzÄ«tam grafikam Ŕāda matrica bÅ«s simetriska, vai arÄ« varam vienoties, ka visas vērtÄ«bas glabājam tikai virs galvenās diagonāles). Nesvērtajiem grafiem a(i,j) var iestatÄ«t pēc Ŕķautņu skaita no i lÄ«dz j (ja tādas nav, tad a(i,j)= 0), bet svērtajiem grafiem arÄ« pēc svara. (kopējais svars) minēto malu.

1.2 SaslimstÄ«bas matrica. Å ajā gadÄ«jumā mÅ«su grafs tiek saglabāts arÄ« tabulā, kurā parasti rindu numuri atbilst tās virsotņu numuriem, bet kolonnu numuri atbilst iepriekÅ” numurētām malām. Ja virsotne un mala atrodas viena pret otru, tad attiecÄ«gajā Ŕūnā ieraksta vērtÄ«bu, kas nav nulle (nevirzÄ«tiem grafiem raksta 1, ja virsotne un mala ir krÄ«toÅ”as, orientētiem grafiem - ā€œ1ā€, ja mala ā€œizietā€ no virsotnes un ā€œ-1ā€, ja tas tajā ā€œietverā€ (to ir pietiekami viegli atcerēties, jo Ŕķiet, ka ā€œmÄ«nusaā€ zÄ«me ir ā€œiekļautaā€ arÄ« ciparā ā€œ-1ā€). Svērtajiem grafikiem atkal 1 un -1 vietā varat norādÄ«t malas kopējo svaru.

2. UzskaitīŔanas datu struktūras

2.1 Blakus esoÅ”o saraksts. Nu Å”eit viss Ŕķiet vienkārÅ”i. Katru grafa virsotni kopumā var saistÄ«t ar jebkuru uzskaites struktÅ«ru (saraksts, vektors, masÄ«vs, ...), kurā tiks saglabāti visu virsotņu numuri, kas atrodas blakus dotajai virsotnei. VirzÄ«tajiem grafiem mēs pievienosim Ŕādam sarakstam tikai tās virsotnes, kurām ir ā€œvirzÄ«taā€ mala no objekta virsotnes. Svērtajiem grafikiem ievieÅ”ana bÅ«s sarežģītāka.

2.2 Ribu saraksts. Diezgan populāra datu struktÅ«ra. Malu saraksts, kā mums stāsta Captain Obviousness, patiesÄ«bā ir grafa Ŕķautņu saraksts, no kurām katra ir norādÄ«ta ar sākuma virsotni, beigu virsotni (nevirzÄ«tiem grafiem secÄ«ba Å”eit nav svarÄ«ga, lai gan apvienoÅ”anai var izmantojiet dažādus noteikumus, piemēram, virsotņu norādÄ«Å”anu pieauguma secÄ«bā un svaru (tikai svērtajiem grafikiem).

JÅ«s varat apskatÄ«t iepriekÅ” minētos matricu sarakstus sÄ«kāk (un ar ilustrācijām), piemēram, Å”eit.

2.3 Blakus masÄ«vs. Nav visizplatÄ«tākā struktÅ«ra. Savā bÅ«tÄ«bā tas ir veids, kā ā€œiesaiņotā€ blakus sarakstus vienā uzskaites struktÅ«rā (masÄ«vā, vektorā). Šāda masÄ«va pirmie n (pēc grafa virsotņu skaita) elementi satur viena un tā paÅ”a masÄ«va sākuma indeksus, no kuriem pēc kārtas tiek ierakstÄ«tas visas dotajam blakus esoŔās virsotnes.

Šeit es atradu sev saprotamāko skaidrojumu: ejuo.livejournal.com/4518.html

3. Blakusuma vektors un asociatīvais blakus masīvs

IzrādÄ«jās, ka Å”o rindu autors, nebÅ«dams profesionāls programmētājs, bet periodiski nodarbojies ar grafiem, visbiežāk nodarbojies ar Ŕķautņu sarakstiem. PatieŔām, tas ir ērti, ja grafikā ir vairākas cilpas un malas. Un tāpēc, izstrādājot klasiskos Ŕķautņu sarakstus, es ierosinu pievērst uzmanÄ«bu to ā€œattÄ«stÄ«bai/atzarojumam/modifikācijai/mutācijaiā€, proti: blakus vektoram un asociatÄ«vajam blakus masÄ«vam.

3.1. Blakus vektors

Gadījums (a1): nesvērts grafiks

Par blakus vektoru nesvērtam grafam sauksim sakārtotu pāra veselu skaitļu kopu (a[2i], a[2i+1],..., kur i ir numurēts c 0), kurā katrs skaitļu pāris ir a[2i], a[2i+1 ] norāda grafa malu attiecīgi starp virsotnēm a[2i] un a[2i+1].
Å is ieraksta formāts nesatur informāciju par to, vai grafiks ir vērsts (iespējamas abas iespējas). Lietojot divkārÅ”u formātu, tiek uzskatÄ«ts, ka mala ir vērsta no a[2i] uz a[2i+1]. Å eit un tālāk: nevirzÄ«tiem grafiem, ja nepiecieÅ”ams, var piemērot prasÄ«bas virsotņu ierakstÄ«Å”anas secÄ«bai (piemēram, virsotne ar zemāku tai pieŔķirtā skaitļa vērtÄ«bu).

Programmā C++ ir ieteicams norādīt blakus vektoru, izmantojot std::vector, līdz ar to arī Ŕīs datu struktūras nosaukumu.

Gadījums (a2): nesvērts grafiks, malu svari ir veseli skaitļi

Pēc analoÄ£ijas ar gadÄ«jumu (a1) mēs saucam blakus vektoru svērtam grafikam ar veselu skaitļu malu svaru par sakārtotu skaitļu kopu (dinamisko masÄ«vu) (a[3i], a[3i+1], a[3i+2], ..., kur i ir numurēts c 0), kur katrs skaitļu a[3i], a[3i+1], a[3i+2] ā€œtripletsā€ norāda grafa malu starp virsotnēm, kas numurētas a[3i] un a[3i+1], un vērtÄ«ba a [3i+2] ir Ŕīs malas svars. Šāds grafiks var bÅ«t arÄ« virzÄ«ts vai nē.

Gadījums (b): nesvērts grafiks, malu svari, kas nav veseli skaitļi

Tā kā, piemēram, vienā masÄ«vā (vektorā) nav iespējams uzglabāt neviendabÄ«gus elementus, ir iespējama Ŕāda realizācija. Grafs tiek saglabāts vektoru pārÄ«, kurā pirmais vektors ir grafika blakus vektors, nenorādot svarus, bet otrais vektors satur atbilstoÅ”os svarus (iespējama C++ ievieÅ”ana: std::pair ). Tādējādi malai, ko nosaka virsotņu pāris zem pirmā vektora indeksiem 2i, 2i+1, svars bÅ«s vienāds ar elementu zem otrā vektora indeksa i.

Nu, kāpēc tas ir vajadzīgs?

Å o rindu autoram tas Ŕķita diezgan noderÄ«gs vairāku problēmu risināŔanai. No formālā viedokļa bÅ«s Ŕādas priekÅ”rocÄ«bas:

  • Blakus vektors, tāpat kā jebkura cita ā€œuzskaitāmāā€ struktÅ«ra, ir diezgan kompakts, aizņem mazāk atmiņas nekā blakusesÄ«bas matrica (retiem grafikiem) un ir salÄ«dzinoÅ”i viegli Ä«stenojams.
  • Grafa virsotnes principā var atzÄ«mēt arÄ« ar negatÄ«viem skaitļiem. Ko darÄ«t, ja Ŕāda "izvirtÄ«ba" ir vajadzÄ«ga?
  • Grafikos var bÅ«t vairākas malas un vairākas cilpas ar atŔķirÄ«gu svaru (pozitÄ«vs, negatÄ«vs, pat nulle). Å eit nav nekādu ierobežojumu.
  • Varat arÄ« pieŔķirt malām dažādus rekvizÄ«tus, bet par to vairāk skatiet 4. sadaļā.

Tomēr jāatzÄ«st, ka Å”is ā€œsarakstsā€ nenozÄ«mē ātru piekļuvi malai. Un Å”eit palÄ«gā nāk Associative Adjacency Array, kas tiek apspriests tālāk.

3.2. Asociatīvais blakus masīvs

Tātad, ja piekļuve konkrētai malai, tās svaram un citām Ä«paŔībām mums ir kritiska, un atmiņas prasÄ«bas neļauj izmantot blakusesÄ«bas matricu, tad padomāsim, kā mēs varam mainÄ«t blakusesÄ«bas vektoru, lai atrisinātu Å”o problēmu. Tātad atslēga ir grafika mala, kuru var norādÄ«t kā sakārtotu veselu skaitļu pāri. Kā tas izskatās? Vai tā nav atslēga asociatÄ«vajā masÄ«vā? Un, ja tā, kāpēc mēs to neieviesām? Ä»aujiet mums izveidot asociatÄ«vu masÄ«vu, kurā katra atslēga - sakārtots veselu skaitļu pāris - tiks saistÄ«ts ar vērtÄ«bu - veselu skaitli vai reālu skaitli, kas norāda malas svaru. C++ valodā Å”o struktÅ«ru ieteicams ieviest, pamatojoties uz std::map konteineru (std::map , int> vai std::map , double>) vai std::multimap, ja ir paredzētas vairākas malas. Mums ir struktÅ«ra grafu glabāŔanai, kas aizņem mazāk atmiņas nekā ā€œmatricasā€ struktÅ«ras, var definēt grafikus ar vairākām cilpām un malām, un tai pat nav stingru prasÄ«bu virsotņu skaitļu nenegatÄ«vÄ«bai (es nezinu kam tas vajadzÄ«gs, bet tomēr).

4. Datu struktūras ir pilnas, bet kaut kā pietrūkst

Un tā ir taisnÄ«ba: risinot vairākas problēmas, mums, iespējams, bÅ«s jāpieŔķir daži raksturlielumi grafika malām un attiecÄ«gi jāsaglabā. Ja ir iespējams viennozÄ«mÄ«gi Ŕīs pazÄ«mes reducēt lÄ«dz veseliem skaitļiem, tad Ŕādus ā€œgrafikus ar papildu pazÄ«mēmā€ iespējams uzglabāt, izmantojot blakus vektora un asociatÄ«vā blakus masÄ«va paplaÅ”inātās versijas.

Tātad, pieņemsim neizsvērtu grafiku, kura katrai malai ir nepiecieÅ”ams saglabāt, piemēram, 2 papildu pazÄ«mes, kas norādÄ«tas ar veseliem skaitļiem. Å ajā gadÄ«jumā ir iespējams definēt tā blakus vektoru kā sakārtotu kopu, kas nav ā€œpāruā€, bet gan veselu skaitļu ā€œkvartetuā€ (a[2i], a[2i+1], a[2i+2], a [2i+3]ā€¦) , kur a[2i+2] un a[2i+3] noteiks atbilstoŔās malas raksturlielumus. Grafikam ar malu veseliem skaitļiem secÄ«ba parasti ir lÄ«dzÄ«ga (vienÄ«gā atŔķirÄ«ba bÅ«s tāda, ka atribÅ«ti sekos malas svaram un tiks norādÄ«ti ar elementiem a[2i+3] un a[2i+4] , un pati mala tiks norādÄ«ta nevis 4, bet 5 sakārtoti cipari). Un grafikam ar malu svariem, kas nav veseli skaitļi, pazÄ«mes var ierakstÄ«t tā nesvērtajā komponentā.

Izmantojot asociatÄ«vo blakusesÄ«bu masÄ«vu grafiem ar veselu malu svaru, kā vērtÄ«bu var norādÄ«t nevis vienu skaitli, bet skaitļu masÄ«vu (vektoru), kas papildus malas svaram norāda arÄ« visu pārējo nepiecieÅ”amo. Iespējas. Tajā paŔā laikā neērtÄ«bas attiecÄ«bā uz svaru, kas nav veseli skaitļi, radÄ«s nepiecieÅ”amÄ«ba norādÄ«t zÄ«mi ar peldoŔā komata skaitli (jā, tas ir neērtÄ«bas, bet, ja Ŕādu zÄ«mju nav tik daudz un Neuzstādiet tos pārāk ā€œgrÅ«tiā€ dubultā, tad tas var bÅ«t nekas) . Tas nozÄ«mē, ka C++ paplaÅ”inātos asociatÄ«vos blakus masÄ«vus var definēt Ŕādi: std::map , std::vector> vai std::map , std::vector, kurā pirmā vērtÄ«ba ā€œatslēgas vērtÄ«bas vektorāā€ bÅ«s malas svars, un pēc tam atrodas tās raksturlielumu skaitliskie apzÄ«mējumi.

Literatūra:

Par grafikiem un algoritmiem kopumā:

1. Kormens, Tomass H., Leizersons, Čārlzs I., Rivests, Ronalds L., Steins, Klifords. Algoritmi: konstrukcija un analÄ«ze, 2. izdevums: Trans. no angļu valodas ā€“ M.: Williams Publishing House, 2011.
2. Harari Frenks. Grafu teorija. M.: Mir, 1973.
Autora ziņojums par Å”o paÅ”u vektoru un blakus esoÅ”o asociatÄ«vo masÄ«vu:
3. Chernoukhov S.A. Blakus vektors un asociatÄ«vais blakusesÄ«bu masÄ«vs kā grafiku attēloÅ”anas un uzglabāŔanas veidi / SA Černouhovs. Blakusvektors un blakuskarte kā datu struktÅ«ras, lai attēlotu grafiku // Starptautiskās zinātniski praktiskās konferences ā€œInovatÄ«vu izstrādņu rezultātu ievieÅ”anas problēmas un to risināŔanas veidiā€ rakstu krājums (Saratova, 14.09.2019. gada 2019. septembris). ā€“ Sterlitamak: AMI, 65, lpp. 69-XNUMX
NoderÄ«gi tieÅ”saistes avoti par Å”o tēmu:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

Avots: www.habr.com

Pievieno komentāru