Hi everyone
Yn dizze notysje besleat ik de haadgegevensstruktueren te listjen dy't brûkt wurde om grafiken yn kompjûterwittenskip op te slaan, en ik sil ek prate oer in pear mear sokke struktueren dy't op ien of oare manier "kristallisearre" foar my.
Dus, litte wy begjinne. Mar net fan it begjin ôf - ik tink dat wy allegearre al witte wat in grafyk is en wat se binne (rjochte, ûnrjochte, gewicht, ûngewogen, mei of sûnder meardere rânen en loops).
Dus, litte wy gean. Hokker opsjes foar gegevensstruktueren foar "grafyk opslach" hawwe wy?
1. Matrix gegevens struktueren
1.1 Adjacency matrix. De neistlizzende matrix is in matrix wêrby't de rigel- en kolomkoppen oerienkomme mei de nûmers fan 'e hoekpunten fan' e grafyk, en de wearde fan elk fan syn eleminten a (i,j) wurdt bepaald troch de oanwêzigens of ôfwêzigens fan rânen tusken hoekpunten i en j (it is dúdlik dat foar in ûnrjochte grafyk sa'n matrix symmetrysk sil wêze, of wy kinne it iens wêze dat wy alle wearden allinich boppe de haaddiagonaal bewarje). Foar ûngewogen grafiken kin a(i,j) ynsteld wurde troch it oantal rânen fan i oant j (as der gjin soksoarte râne is, dan a(i,j)= 0), en foar gewichtige grafiken ek troch it gewicht (totaal gewicht) fan de neamde rânen.
1.2 Incidence matrix. Yn dit gefal wurdt ús grafyk ek opslein yn in tabel wêryn, as regel, de rige nûmers oerienkomme mei de nûmers fan har hoekpunten, en de kolomnûmers oerienkomme mei pre-nûmere rânen. As in hoekpunt en in râne ynfallend binne foar elkoar, dan wurdt in net-nulwearde skreaun yn 'e oerienkommende sel (foar ûnrjochte grafiken wurdt 1 skreaun as it hoekpunt en râne ynfallend binne, foar oriïntearre grafiken - "1" as de râne "útgongen" út it toppunt en "-1" as it "omfettet" deryn (it is maklik genôch om te ûnthâlden, omdat it "minus" teken ek liket te wêzen "opnaam" yn it nûmer "-1")). Foar gewichtige grafiken, wer, ynstee fan 1 en -1, kinne jo it totale gewicht fan 'e râne opjaan.
2. Opsomming gegevens struktueren
2.1 Adjacency list. No, alles liket hjir ienfâldich te wêzen. Elke hoekpunt fan 'e grafyk kin, yn' t algemien, wurde assosjeare mei elke enumeraasjestruktuer (list, vector, array, ...), dy't de nûmers fan alle hoekpunten neist de opjûne opslaan sil. Foar rjochte grafiken, wy sille tafoegje oan sa'n list allinnich dy hoekpunten dêr't der in "rjochte" râne fan in funksje vertex. Foar gewichtige grafiken sil de ymplemintaasje komplekser wêze.
2.2 List fan ribben. Hiel populêre gegevensstruktuer. De list mei rânen, sa't Captain Obviousness ús fertelt, is eins in list mei rânen fan 'e grafyk, wêrfan elk wurdt oantsjutte troch it begjinpunt, it einpunt (foar ûnrjochte grafiken is de folchoarder hjir net wichtich, hoewol foar ienwurding kinne jo brûke ferskate regels, bygelyks, spesifisearje de hoekpunten yn folchoarder tanimmend) en gewicht (allinich foar gewicht grafiken).
Jo kinne de boppesteande matrikslisten yn mear detail sjen (en mei yllustraasjes), bygelyks, .
2.3 Adjacency array. Net de meast foarkommende struktuer. Yn har kearn is it in foarm fan "ynpakke" neistlizzende listen yn ien enumeraasjestruktuer (array, vector). De earste n (neffens it oantal hoekpunten fan 'e grafyk) eleminten fan sa'n rige befetsje de startindices fan deselde rige, útgeande dêr't alle hoekpunten neist de opjûne ien wurde skreaun yn in rige.
Hjir fûn ik de meast begryplike (foar mysels) ferklearring:
3. Adjacency Vector en Associative Adjacency Array
It die bliken dat de skriuwer fan dizze rigels, net as in profesjonele programmeur, mar dy't periodyk omgie mei grafiken, meastentiids behannele mei listen fan rânen. Yndied is it handich as de grafyk meardere loops en rânen hat. En sa, yn 'e ûntwikkeling fan' e klassike listen fan rânen, stel ik foar om omtinken te jaan oan har "ûntwikkeling / tûke / wiziging / mutaasje", nammentlik: de adjacency-vektor en de assosiative adjacency-array.
3.1 Adjacency vector
Case (a1): unweighted grafyk
Wy neame in neistlizzende vector foar in net-gewogen grafyk in oardere set fan in even oantal hiele getallen (a[2i], a[2i+1],..., wêryn i is nûmere c 0), wêryn elk pear nûmers is a[2i], a[2i+1] spesifisearret in grafykrâne tusken respektivelik de hoekpunten a[2i] en a[2i+1].
Dit opnameformaat befettet gjin ynformaasje oer oft de grafyk is rjochte (beide opsjes binne mooglik). By it brûken fan it digraph-formaat wurdt de râne beskôge as rjochte fan a[2i] nei a[2i+1]. Hjir en hjirûnder: foar ûnrjochte grafiken kinne, as it nedich is, easken tapast wurde foar de folchoarder fan opnimmen fan hoekpunten (bygelyks dat it toppunt mei de legere wearde fan it dêroan tawiisde nûmer foarop komt).
Yn C ++ is it oan te rieden om in adjacency vector oan te jaan mei help fan std :: vector, fandêr de namme fan dizze gegevensstruktuer.
Case (a2): unweighted grafyk, râne gewichten binne hiel getal
Nei analogy mei gefal (a1), neame wy de neistlizzende fektor foar in gewichtige grafyk mei heule getal rânegewichten in oardere set (dynamyske array) fan nûmers (a[3i], a[3i+1], a[3i+2], ..., wêr't i nûmere is c 0), wêrby't elke "trijeling" fan nûmers a[3i], a[3i+1], a[3i+2] in râne fan 'e grafyk spesifisearret tusken hoekpunten nûmere a[3i] en respektivelik a[3i+1], en de wearde a [3i+2] is it gewicht fan dizze râne. Sa'n grafyk kin ek al of net rjochte wurde.
Case (b): unweighted grafyk, non-integer edge gewichten
Om't it ûnmooglik is om heterogene eleminten yn ien array (vektor) op te slaan, is bygelyks de folgjende ymplemintaasje mooglik. De grafyk wurdt opslein yn in pear vectoren, wêryn't de earste fektor de neistlizzende fektor fan 'e grafyk is sûnder de gewichten oan te jaan, en de twadde fektor befettet de oerienkommende gewichten (mooglike ymplemintaasje foar C++: std::pair ). Sa, foar in râne definiearre troch in pear hoekpunten ûnder yndeksen 2i, 2i + 1 fan de earste vector, it gewicht sil wêze gelyk oan it elemint ûnder yndeks i fan de twadde vector.
No, wêrom is dit nedich?
No, de skriuwer fan dizze rigels fûn it frij nuttich foar it oplossen fan in oantal problemen. No, út in formeel eachpunt sille d'r de folgjende foardielen wêze:
- De neistlizzende fektor, lykas elke oare "enumerative" struktuer, is frij kompakt, nimt minder ûnthâld op as de neistlizzende matrix (foar sparse grafiken), en is relatyf maklik te ymplementearjen.
- De hoekpunten fan 'e grafyk kinne yn prinsipe ek markearre wurde mei negative sifers. Wat as sa'n "perversion" nedich is?
- Grafiken kinne befetsje meardere rânen en meardere loops, mei ferskillende gewichten (posityf, negatyf, sels nul). D'r binne hjir gjin beheiningen.
- Jo kinne ek ferskate eigenskippen tawize oan rânen - mar foar mear oer dat, sjoch paragraaf 4.
It moat lykwols talitten wurde dat dizze "list" gjin rappe tagong ta de râne betsjuttet. En hjir komt de Associative Adjacency Array ta de rêding, dy't hjirûnder besprutsen wurdt.
3.2 Associative adjacency array
Dus, as tagong ta in spesifike râne, syn gewicht en oare eigenskippen is kritysk foar ús, en ûnthâld easken net tastean ús te brûken de adjacency matrix, dan litte wy tinke oer hoe't wy kinne feroarje de adjacency vector te lossen dit probleem. Dat, de kaai is in râne fan 'e grafyk, dy't kin wurde oantsjutte as in bestelde pear heule getallen. Hoe sjocht dit der út? Is it net in kaai yn in assosjatyf array? En, as dat sa is, wêrom implementearje wy it net? Lit ús hawwe in assosjatyf array dêr't elke kaai - in oardere pear hiele getallen - sil wurde assosjearre mei in wearde - in hiel getal of in echt getal dat spesifisearret it gewicht fan de râne. Yn C++ is it oan te rieden om dizze struktuer te ymplementearjen basearre op de std :: mapcontainer (std :: map , int> of std::map , dûbel>), of std::multimap as meardere rânen wurde ferwachte. No, wy hawwe in struktuer foar it opslaan fan grafiken dy't minder ûnthâld opnimt dan "matrix"-struktueren, grafiken kin definiearje mei meardere loops en rânen, en net iens strikte easken hat foar de net-negativiteit fan vertexnûmers (ik wit it net) wa hat dit nedich, mar dochs).
4. Gegevensstruktueren binne fol, mar der ûntbrekt wat
En it is wier: by it oplossen fan in oantal problemen, moatte wy miskien wat skaaimerken tawize oan 'e rânen fan' e grafyk en, neffens, opslaan. As it mooglik is om ûndûbelsinnich te ferminderjen dizze funksjes ta hiele getallen, dan is it mooglik om te bewarjen sokke "grafiken mei oanfoljende funksjes" mei help fan útwreide ferzjes fan de neistlizzende vector en assosjatyf adjacency array.
Dat, lit ús in unweighted grafyk hawwe, foar elke râne wêrfan it nedich is om bygelyks 2 ekstra funksjes op te slaan, spesifisearre troch heule getallen. Yn dit gefal is it mooglik om syn neistlizzende fektor te definiearjen as in oardere set net fan "pearen", mar fan "kwartetten" fan heule getallen (a[2i], a[2i+1], a[2i+2], a [2i+3]...), wêrby't a[2i+2] en a[2i+3] de skaaimerken fan 'e oerienkommende râne sille bepale. Foar in grafyk mei hiele gewichten fan rânen is de folchoarder oer it algemien ferlykber (it iennichste ferskil sil wêze dat de attributen it gewicht fan 'e râne folgje en wurde oantsjutte troch de eleminten a[2i+3] en a[2i+4] , en de râne sels wurdt oantsjutte net 4, mar 5 bestelde nûmers). En foar in grafyk mei net-geheel getal râne gewichten, de funksjes kinne wurde skreaun yn syn unweighted komponint.
By it brûken fan in assosjatyf neistlizzende array foar grafiken mei heule getal rânegewichten, is it mooglik om as wearde net in inkeld getal op te jaan, mar in array (vektor) fan nûmers dy't, neist it gewicht fan in râne, al syn oare needsaaklike spesifisearje funksjes. Tagelyk sil in oerlêst foar it gefal fan net-integer gewichten de needsaak wêze om in teken te spesifisearjen mei in driuwend puntnûmer (ja, dit is in oerlêst, mar as d'r net safolle fan sokke tekens binne, en as jo dogge 't set se net te "tricky" dûbel, dan kin it neat wêze). Dit betsjut dat yn C++ útwreide assosjative adjacency-arrays kinne wurde definieare as folget: std :: map , std::vector> of std::map , std :: vector, wêryn de earste wearde yn de "key-wearde-vector" sil wêze it gewicht fan 'e râne, en dan de numerike oantsjuttings fan syn skaaimerken lizze.
Literatuer:
Oer grafiken en algoritmen yn it algemien:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmen: konstruksje en analyze, 2e edysje: Trans. út it Ingelsk – M.: Williams Publishing House, 2011.
2. Harari Frank. Grafyske teory. M.: Mir, 1973.
It rapport fan 'e auteur oer dizze selde fektor en assosjatyf array fan adjacencies:
3. Chernoukhov S.A. Adjacency vector en assosjatyf adjacency array as manieren om te fertsjintwurdigjen en opslaan grafiken / SA Chernouhov. Adjacency vector en adjacency map as gegevensstruktueren om in grafyk te fertsjintwurdigjen // Samling fan artikels fan 'e Ynternasjonale Wittenskiplike en Praktyske Konferinsje "Problemen fan it útfieren fan de resultaten fan ynnovative ûntjouwings en manieren om se op te lossen" (Saratov, 14.09.2019 septimber 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Nuttige online boarnen oer it ûnderwerp:
4.
5.
Boarne: www.habr.com