Kumusta lahat.
Sa talang ito, nagpasya akong ilista ang mga pangunahing istruktura ng data na ginagamit upang mag-imbak ng mga graph sa agham ng computer, at magsasalita din ako tungkol sa ilang higit pang mga istruktura na kahit papaano ay "nag-crystallize" para sa akin.
Kaya, magsimula tayo. Ngunit hindi sa simula pa lang - sa palagay ko alam na nating lahat kung ano ang isang graph at kung ano ang mga ito (nakadirekta, hindi nakadirekta, may timbang, walang timbang, mayroon o walang maraming mga gilid at mga loop).
So, tara na. Anong mga opsyon para sa mga istruktura ng data para sa "imbakan ng graph" ang mayroon tayo?
1. Mga istruktura ng data ng matrix
1.1 Adjacency matrix. Ang adjacency matrix ay isang matrix kung saan ang mga heading ng row at column ay tumutugma sa mga numero ng vertices ng graph, at ang value ng bawat elemento nito a(i,j) ay tinutukoy ng presensya o kawalan ng mga gilid sa pagitan ng vertices i at j (malinaw na para sa isang hindi nakadirekta na graph, ang isang matrix ay magiging simetriko, o maaari kaming sumang-ayon na iimbak namin ang lahat ng mga halaga lamang sa itaas ng pangunahing dayagonal). Para sa mga hindi natimbang na graph, ang a(i,j) ay maaaring itakda sa pamamagitan ng bilang ng mga gilid mula i hanggang j (kung walang ganoong gilid, pagkatapos ay a(i,j)= 0), at para sa mga weighted na graph, ayon din sa timbang (kabuuang timbang) ng mga nabanggit na gilid.
1.2 Matrix ng insidente. Sa kasong ito, ang aming graph ay naka-imbak din sa isang talahanayan kung saan, bilang panuntunan, ang mga numero ng row ay tumutugma sa mga numero ng mga vertices nito, at ang mga numero ng column ay tumutugma sa mga pre-numbered na mga gilid. Kung ang isang vertex at isang gilid ay insidente sa isa't isa, pagkatapos ay isang hindi-zero na halaga ang nakasulat sa kaukulang cell (para sa mga hindi nakadirekta na mga graph, 1 ay nakasulat kung ang vertex at gilid ay insidente, para sa mga nakatuon - "1" kung ang gilid "lumabas" mula sa tuktok at "-1" kung ito ay "kasama" dito (ito ay sapat na madaling matandaan, dahil ang "minus" sign ay tila "kasama" din sa numerong "-1")). Para sa mga weighted graph, muli, sa halip na 1 at -1, maaari mong tukuyin ang kabuuang bigat ng gilid.
2. Enumeration data structures
2.1 Listahan ng katabi. Well, parang simple lang ang lahat dito. Ang bawat vertex ng graph, sa pangkalahatan, ay maaaring iugnay sa anumang enumeration structure (list, vector, array, ...), na mag-iimbak ng mga numero ng lahat ng vertices na katabi ng ibinigay na isa. Para sa mga nakadirekta na graph, idaragdag lang namin sa naturang listahan ang mga vertex kung saan mayroong "nakadirekta" na gilid mula sa isang feature vertex. Para sa mga weighted graph, magiging mas kumplikado ang pagpapatupad.
2.2 Listahan ng mga tadyang. Isang sikat na istraktura ng data. Ang listahan ng mga gilid, gaya ng sinasabi sa amin ni Captain Obviousness, ay talagang isang listahan ng mga gilid ng graph, na ang bawat isa ay tinukoy ng panimulang vertex, ang nagtatapos na vertex (para sa mga hindi nakadirekta na mga graph ang pagkakasunud-sunod ay hindi mahalaga dito, bagaman para sa pag-iisa maaari mong gumamit ng iba't ibang panuntunan, halimbawa, pagtukoy sa mga vertices sa pagtaas ng pagkakasunud-sunod) at timbang (para sa mga weighted graph lang).
Maaari mong tingnan ang mga listahan ng matrix na nakalista sa itaas nang mas detalyado (at may mga guhit), halimbawa, .
2.3 Adjacency array. Hindi ang pinakakaraniwang istraktura. Sa kaibuturan nito, ito ay isang anyo ng "pag-iimpake" ng mga listahan ng katabi sa isang enumeration structure (array, vector). Ang unang n (ayon sa bilang ng mga vertices ng graph) na mga elemento ng naturang array ay naglalaman ng mga panimulang indeks ng parehong array, simula kung saan ang lahat ng vertices na katabi ng ibinigay ay nakasulat sa isang row.
Dito ko nakita ang pinaka-maiintindihan (para sa aking sarili) na paliwanag:
3. Adjacency Vector at Associative Adjacency Array
Ito ay lumabas na ang may-akda ng mga linyang ito, na hindi isang propesyonal na programmer, ngunit na pana-panahong nakikitungo sa mga graph, kadalasang nakikitungo sa mga listahan ng mga gilid. Sa katunayan, ito ay maginhawa kung ang graph ay may maraming mga loop at mga gilid. At kaya, sa pagbuo ng mga klasikong listahan ng mga gilid, iminumungkahi kong bigyang-pansin ang kanilang "pag-unlad/sangay/pagbabago/mutation", ibig sabihin: ang adjacency vector at ang associative adjacency array.
3.1 Adjacency vector
Case (a1): walang timbang na graph
Tatawag kami ng adjacency vector para sa isang unweighted graph na isang ordered set ng even number of integers (a[2i], a[2i+1],..., kung saan ang i ay may bilang na c 0), kung saan ang bawat pares ng mga numero ay a[2i], a[2i+1 ] ay tumutukoy sa gilid ng graph sa pagitan ng mga vertices a[2i] at a[2i+1], ayon sa pagkakabanggit.
Ang format ng pag-record na ito ay hindi naglalaman ng impormasyon tungkol sa kung ang graph ay nakadirekta (parehong mga opsyon ay posible). Kapag ginagamit ang digraph na format, ang gilid ay itinuturing na nakadirekta mula sa a[2i] hanggang sa a[2i+1]. Dito at sa ibaba: para sa mga hindi nakadirekta na graph, kung kinakailangan, ang mga kinakailangan para sa pagkakasunud-sunod ng pagtatala ng mga vertice ay maaaring ilapat (halimbawa, na ang vertex na may mas mababang halaga ng numerong itinalaga dito ay mauna).
Sa C++, ipinapayong tumukoy ng adjacency vector gamit ang std::vector, kaya ang pangalan ng istruktura ng data na ito.
Case (a2): walang timbang na graph, ang mga edge weight ay integer
Sa pamamagitan ng pagkakatulad sa case (a1), tinatawag namin ang adjacency vector para sa isang weighted graph na may integer edge weights isang ordered set (dynamic array) ng mga numero (a[3i], a[3i+1], a[3i+2], ..., kung saan ang i ay may bilang na c 0), kung saan ang bawat "triplet" ng mga numerong a[3i], a[3i+1], a[3i+2] ay tumutukoy sa gilid ng graph sa pagitan ng mga vertice na may bilang na a[3i] at a[3i+1], ayon sa pagkakabanggit, at ang halagang a [3i+2] ay ang bigat ng gilid na ito. Ang ganitong graph ay maaari ding idirekta o hindi.
Case (b): unweighted graph, non-integer edge weights
Dahil imposibleng mag-imbak ng mga heterogenous na elemento sa isang array (vector), halimbawa, posible ang sumusunod na pagpapatupad. Ang graph ay naka-imbak sa isang pares ng mga vector, kung saan ang unang vector ay ang adjacency vector ng graph nang hindi tinukoy ang mga timbang, at ang pangalawang vector ay naglalaman ng kaukulang mga timbang (posibleng pagpapatupad para sa C++: std::pair ). Kaya, para sa isang gilid na tinukoy ng isang pares ng vertices sa ilalim ng mga index 2i, 2i+1 ng unang vector, ang timbang ay magiging katumbas ng elemento sa ilalim ng index i ng pangalawang vector.
Well, bakit kailangan ito?
Well, ang may-akda ng mga linyang ito ay natagpuan na ito ay lubos na kapaki-pakinabang para sa paglutas ng isang bilang ng mga problema. Kaya, mula sa isang pormal na pananaw, magkakaroon ng mga sumusunod na pakinabang:
- Ang adjacency vector, tulad ng anumang iba pang "enumerative" na istraktura, ay medyo compact, tumatagal ng mas kaunting memorya kaysa sa adjacency matrix (para sa mga kalat-kalat na graph), at medyo madaling ipatupad.
- Ang mga vertex ng graph, sa prinsipyo, ay maaari ding markahan ng mga negatibong numero. Paano kung kailangan ang ganitong “perversion”?
- Ang mga graph ay maaaring maglaman ng maraming mga gilid at maraming mga loop, na may iba't ibang mga timbang (positibo, negatibo, kahit na zero). Walang mga paghihigpit dito.
- Maaari ka ring magtalaga ng iba't ibang katangian sa mga gilid - ngunit para sa higit pa tungkol doon, tingnan ang seksyon 4.
Gayunpaman, dapat itong aminin na ang "listahan" na ito ay hindi nagpapahiwatig ng mabilis na pag-access sa gilid. At dito ang Associative Adjacency Array ay sumagip, na tinalakay sa ibaba.
3.2 Kaugnay na hanay ng katabi
Kaya, kung ang pag-access sa isang tiyak na gilid, ang timbang nito at iba pang mga katangian ay kritikal para sa amin, at ang mga kinakailangan sa memorya ay hindi nagpapahintulot sa amin na gamitin ang adjacency matrix, pagkatapos ay isipin natin kung paano natin mababago ang adjacency vector upang malutas ang problemang ito. Kaya, ang susi ay isang gilid ng graph, na maaaring tukuyin bilang isang nakaayos na pares ng mga integer. Anong itsura nito? Hindi ba ito isang susi sa isang associative array? At, kung gayon, bakit hindi natin ito ipatupad? Magkaroon tayo ng isang associative array kung saan ang bawat key - isang nakaayos na pares ng integer - ay iuugnay sa isang value - isang integer o isang tunay na numero na tumutukoy sa bigat ng gilid. Sa C++, ipinapayong ipatupad ang istrukturang ito batay sa std::map container (std::map , int> o std::map , double>), o std::multimap kung maraming mga gilid ang inaasahan. Well, mayroon kaming istraktura para sa pag-iimbak ng mga graph na kumukuha ng mas kaunting memorya kaysa sa mga istruktura ng "matrix", maaaring tukuyin ang mga graph na may maraming mga loop at gilid, at kahit na walang mahigpit na mga kinakailangan para sa hindi negatibong mga numero ng vertex (hindi ko alam sino ang nangangailangan nito, ngunit gayon pa man).
4. Puno ang mga istruktura ng data, ngunit may kulang
At totoo ito: kapag nilulutas ang ilang problema, maaaring kailanganin nating magtalaga ng ilang katangian sa mga gilid ng graph at, nang naaayon, iimbak ang mga ito. Kung posible na hindi malabo na bawasan ang mga feature na ito sa mga integer, posibleng mag-imbak ng mga naturang "graph na may mga karagdagang feature" gamit ang mga pinahabang bersyon ng adjacency vector at associative adjacency array.
Kaya, magkaroon tayo ng isang hindi natimbang na graph, para sa bawat gilid kung saan kinakailangan na mag-imbak, halimbawa, 2 karagdagang mga tampok na tinukoy ng mga integer. Sa kasong ito, posibleng tukuyin ang adjacency vector nito bilang isang ordered set hindi ng "mga pares", ngunit ng "quartets" ng mga integer (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , kung saan matutukoy ng a[2i+2] at a[2i+3] ang mga katangian ng kaukulang gilid. Para sa isang graph na may mga integer na timbang ng mga gilid, ang pagkakasunud-sunod ay karaniwang magkatulad (ang tanging pagkakaiba ay ang mga katangian ay susunod sa bigat ng gilid at tutukuyin ng mga elementong a[2i+3] at a[2i+4] , at ang gilid mismo ay tutukuyin hindi 4, ngunit 5 ordered number). At para sa isang graph na may non-integer edge weights, ang mga feature ay maaaring isulat sa hindi timbang na bahagi nito.
Kapag gumagamit ng associative adjacency array para sa mga graph na may integer edge weights, posibleng tukuyin bilang value hindi isang numero, ngunit array (vector) ng mga numero na tumutukoy, bilang karagdagan sa bigat ng isang gilid, lahat ng iba pang kinakailangan nito mga tampok. Kasabay nito, ang isang abala para sa kaso ng mga non-integer na timbang ay ang pangangailangan na tukuyin ang isang senyas na may numero ng lumulutang na punto (oo, ito ay isang abala, ngunit kung walang ganoong karaming mga palatandaan, at kung hindi mo 't itakda ang mga ito masyadong "mapanlinlang" double, pagkatapos ay maaaring ito ay wala) . Nangangahulugan ito na sa C++ extended associative adjacency arrays ay maaaring tukuyin bilang mga sumusunod: std::map , std::vector> o std::map , std::vector, kung saan ang unang value sa "key-value-vector" ay ang bigat ng gilid, at pagkatapos ay matatagpuan ang mga numerical designation ng mga katangian nito.
Panitikan:
Tungkol sa mga graph at algorithm sa pangkalahatan:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithms: construction at analysis, 2nd edition: Trans. mula sa Ingles – M.: Williams Publishing House, 2011.
2. Harari Frank. Teorya ng graph. M.: Mir, 1973.
Ang ulat ng may-akda tungkol sa parehong vector at nag-uugnay na hanay ng mga adjacencies:
3. Chernoukhov S.A. Adjacency vector at associative adjacency array bilang mga paraan upang kumatawan at mag-imbak ng mga graph / SA Chernouhov. Adjacency vector at adjacency map bilang mga istruktura ng data upang kumatawan sa isang graph // Koleksyon ng mga artikulo ng International Scientific and Practical Conference "Mga problema sa pagpapatupad ng mga resulta ng mga makabagong pag-unlad at mga paraan upang malutas ang mga ito" (Saratov, Setyembre 14.09.2019, 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Mga kapaki-pakinabang na online na mapagkukunan sa paksa:
4.
5.
Pinagmulan: www.habr.com