Hallo almal.
In hierdie nota het ek besluit om die belangrikste datastrukture te lys wat gebruik word om grafieke in rekenaarwetenskap te stoor, en ek sal ook praat oor nog 'n paar sulke strukture wat op een of ander manier vir my "gekristalliseer" het.
So, kom ons begin. Maar nie van die begin af nie - ek dink ons weet almal reeds wat 'n grafiek is en wat dit is (gerig, ongerig, geweeg, ongeweeg, met of sonder veelvuldige rande en lusse).
So, kom ons gaan. Watter opsies vir datastrukture vir "grafiekberging" het ons?
1. Matriksdatastrukture
1.1 Aangrensende matriks. Die aangrensende matriks is 'n matriks waar die ry- en kolomopskrifte ooreenstem met die nommers van die hoekpunte van die grafiek, en die waarde van elk van sy elemente a(i,j) word bepaal deur die teenwoordigheid of afwesigheid van rande tussen hoekpunte i en j (dit is duidelik dat vir 'n ongerigte grafiek so 'n matriks simmetries sal wees, of ons kan saamstem dat ons alle waardes net bokant die hoofdiagonaal stoor). Vir ongeweegde grafieke kan a(i,j) gestel word deur die aantal rande van i tot j (as daar nie so 'n rand is nie, dan is a(i,j)= 0), en vir geweegde grafieke, ook deur die gewig (totale gewig) van die genoemde rande.
1.2 Insidensie matriks. In hierdie geval word ons grafiek ook in 'n tabel gestoor waarin, as 'n reël, die rynommers ooreenstem met die nommers van sy hoekpunte, en die kolomnommers ooreenstem met vooraf genommerde rande. As 'n hoekpunt en 'n rand op mekaar inval, word 'n nie-nul waarde in die ooreenstemmende sel geskryf (vir ongerigte grafieke word 1 geskryf as die hoekpunt en rand invallend is, vir georiënteerdes - "1" as die rand "uitgang" uit die hoekpunt en "-1" as dit daarby "insluit" (dit is maklik genoeg om te onthou, want die "minus" teken blyk ook "ingesluit" te wees in die getal "-1")). Vir geweegde grafieke, weer, in plaas van 1 en -1, kan jy die totale gewig van die rand spesifiseer.
2. Opsomming datastrukture
2.1 Aangrensende lys. Wel, alles blyk eenvoudig hier te wees. Elke hoekpunt van die grafiek kan oor die algemeen geassosieer word met enige opsommingstruktuur (lys, vektor, skikking, ...), wat die nommers van alle hoekpunte langs die gegewe een sal stoor. Vir gerigte grafieke sal ons slegs daardie hoekpunte by so 'n lys voeg waarheen daar 'n "gerigte" rand vanaf 'n kenmerkhoekpunt is. Vir geweegde grafieke sal die implementering meer kompleks wees.
2.2 Lys van ribbes. Nogal 'n gewilde datastruktuur. Die lys rande, soos Captain Obviousness ons vertel, is eintlik 'n lys rande van die grafiek, wat elkeen gespesifiseer word deur die beginpunt, die eindpunt (vir ongerigte grafieke is die volgorde nie hier belangrik nie, alhoewel jy vir eenwording kan gebruik verskeie reëls, byvoorbeeld om die hoekpunte te spesifiseer in volgorde toeneem) en gewig (slegs vir geweegde grafieke).
Jy kan kyk na die matrikslyste hierbo gelys in meer besonderhede (en met illustrasies), byvoorbeeld, .
2.3 Aangrensende skikking. Nie die mees algemene struktuur nie. In sy kern is dit 'n vorm van "verpak" van aangrensende lyste in een opsommingstruktuur (skikking, vektor). Die eerste n (volgens die aantal hoekpunte van die grafiek) elemente van so 'n skikking bevat die beginindekse van dieselfde skikking, vanaf waar alle hoekpunte aangrensend aan die gegewe een in 'n ry geskryf word.
Hier het ek die mees verstaanbare (vir myself) verduideliking gevind:
3. Adjacency Vector en Assosiative Adjacency Array
Dit het geblyk dat die skrywer van hierdie reëls, nie 'n professionele programmeerder nie, maar wat periodiek met grafieke gehandel het, meestal met lyste van rande gehandel het. Dit is inderdaad gerieflik as die grafiek veelvuldige lusse en rande het. En so, in die ontwikkeling van die klassieke lyste van rande, stel ek voor om aandag te skenk aan hul "ontwikkeling/vertakking/modifikasie/mutasie", naamlik: die aangrensvektor en die assosiatiewe aangrensingsskikking.
3.1 Aangrensende vektor
Geval (a1): ongeweegde grafiek
Ons sal 'n aangrensende vektor vir 'n ongeweegde grafiek 'n geordende stel van 'n ewe aantal heelgetalle (a[2i], a[2i+1],..., waar i genommer is c 0) noem, waarin elke paar getalle is a[2i], a[2i+1 ] spesifiseer 'n grafiekrand tussen die hoekpunte a[2i] en a[2i+1], onderskeidelik.
Hierdie opnameformaat bevat nie inligting oor of die grafiek gerig is nie (albei opsies is moontlik). Wanneer die digraph-formaat gebruik word, word die rand beskou as gerig van a[2i] na a[2i+1]. Hier en onder: vir ongerigte grafieke, indien nodig, kan vereistes vir die volgorde van opneem van hoekpunte toegepas word (byvoorbeeld dat die hoekpunt met die laer waarde van die getal wat daaraan toegeken is, eerste kom).
In C++ is dit raadsaam om 'n aangrensende vektor te spesifiseer met behulp van std::vektor, vandaar die naam van hierdie datastruktuur.
Geval (a2): ongeweegde grafiek, randgewigte is heelgetal
In analogie met geval (a1), noem ons die aangrensende vektor vir 'n geweegde grafiek met heelgetal randgewigte 'n geordende stel (dinamiese skikking) van getalle (a[3i], a[3i+1], a[3i+2], ..., waar i genommer is c 0), waar elke “drieling” van getalle a[3i], a[3i+1], a[3i+2] 'n rand van die grafiek spesifiseer tussen hoekpunte genommer a[3i] en a[3i+1], onderskeidelik, en die waarde a [3i+2] is die gewig van hierdie rand. So 'n grafiek kan ook of gerig wees of nie.
Geval (b): ongeweegde grafiek, nie-heelgetal randgewigte
Aangesien dit onmoontlik is om byvoorbeeld heterogene elemente in een skikking (vektor) te stoor, is die volgende implementering moontlik. Die grafiek word in 'n paar vektore gestoor, waarin die eerste vektor die grafiek se aangrensende vektor is sonder om die gewigte te spesifiseer, en die tweede vektor bevat die ooreenstemmende gewigte (moontlike implementering vir C++: std::pair ). Dus, vir 'n rand gedefinieer deur 'n paar hoekpunte onder indekse 2i, 2i+1 van die eerste vektor, sal die gewig gelyk wees aan die element onder indeks i van die tweede vektor.
Wel, hoekom is dit nodig?
Wel, die skrywer van hierdie reëls het dit baie nuttig gevind om 'n aantal probleme op te los. Wel, vanuit 'n formele oogpunt sal daar die volgende voordele wees:
- Die aangrensvektor, soos enige ander "enumeratiewe" struktuur, is redelik kompak, neem minder geheue op as die aangrensende matriks (vir yl grafieke), en is relatief maklik om te implementeer.
- Die hoekpunte van die grafiek kan in beginsel ook met negatiewe getalle gemerk word. Wat as so 'n "perversie" nodig is?
- Grafieke kan veelvuldige rande en veelvuldige lusse bevat, met verskillende gewigte (positief, negatief, selfs nul). Hier is geen beperkings nie.
- Jy kan ook verskillende eienskappe aan rande toewys - maar vir meer daaroor, sien afdeling 4.
Daar moet egter erken word dat hierdie "lys" nie vinnige toegang tot die rand impliseer nie. En hier kom die Associative Adjacency Array tot die redding, wat hieronder bespreek word.
3.2 Assosiatiewe aangrensingsskikking
Dus, as toegang tot 'n spesifieke rand, sy gewig en ander eienskappe vir ons van kritieke belang is, en geheuevereistes laat ons nie toe om die aangrensmatriks te gebruik nie, laat ons dink hoe ons die aangrensvektor kan verander om hierdie probleem op te los. Dus, die sleutel is 'n rand van die grafiek, wat gespesifiseer kan word as 'n geordende paar heelgetalle. Hoe lyk dit? Is dit nie 'n sleutel in 'n assosiatiewe skikking nie? En, indien wel, hoekom implementeer ons dit nie? Kom ons het 'n assosiatiewe skikking waar elke sleutel - 'n geordende paar heelgetalle - geassosieer sal word met 'n waarde - 'n heelgetal of 'n reële getal wat die gewig van die rand spesifiseer. In C++ is dit raadsaam om hierdie struktuur te implementeer gebaseer op die std::kaarthouer (std::map , int> of std::map , double>), of std::multimap as veelvuldige rande verwag word. Wel, ons het 'n struktuur vir die stoor van grafieke wat minder geheue opneem as "matriks" strukture, grafieke met veelvuldige lusse en rande kan definieer, en nie eers streng vereistes het vir die nie-negativiteit van hoekpuntgetalle nie (ek weet nie wie het dit nodig, maar tog).
4. Datastrukture is vol, maar iets skort
En dit is waar: wanneer ons 'n aantal probleme oplos, moet ons dalk 'n paar eienskappe aan die rande van die grafiek toewys en dit dienooreenkomstig stoor. As dit moontlik is om hierdie kenmerke ondubbelsinnig tot heelgetalle te verminder, dan is dit moontlik om sulke "grafieke met addisionele kenmerke" te stoor deur uitgebreide weergawes van die aangrensvektor en assosiatiewe aangrensende skikking te gebruik.
Dus, laat ons 'n ongeweegde grafiek hê, vir elke rand waarvan dit nodig is om byvoorbeeld 2 bykomende kenmerke te stoor wat deur heelgetalle gespesifiseer word. In hierdie geval is dit moontlik om sy aangrensende vektor te definieer as 'n geordende stel nie van "pare" nie, maar van "kwartette" heelgetalle (a[2i], a[2i+1], a[2i+2], a [2i+3]...) , waar a[2i+2] en a[2i+3] die eienskappe van die ooreenstemmende rand sal bepaal. Vir 'n grafiek met heelgetalgewigte van rande is die volgorde oor die algemeen soortgelyk (die enigste verskil sal wees dat die eienskappe die gewig van die rand sal volg en gespesifiseer sal word deur die elemente a[2i+3] en a[2i+4] , en die rand self sal nie 4 nie, maar 5 geordende nommers gespesifiseer word). En vir 'n grafiek met nie-heelgetal randgewigte, kan die kenmerke in sy ongeweegde komponent geskryf word.
Wanneer 'n assosiatiewe aangrensende skikking vir grafieke met heelgetal randgewigte gebruik word, is dit moontlik om nie 'n enkele getal as 'n waarde te spesifiseer nie, maar 'n skikking (vektor) van getalle wat, benewens die gewig van 'n rand, al sy ander nodige kenmerke. Terselfdertyd sal 'n ongerief vir die geval van nie-heelgetalgewigte die behoefte wees om 'n teken met 'n drywende puntnommer te spesifiseer (ja, dit is 'n ongerief, maar as daar nie soveel sulke tekens is nie, en as jy nie stel hulle nie te “moeilik” dubbel nie, dan is dit dalk niks). Dit beteken dat in C++ uitgebreide assosiatiewe aangrensende skikkings soos volg gedefinieer kan word: std::map , std::vector> of std::kaart , std::vektor, waarin die eerste waarde in die "sleutel-waarde-vektor" die gewig van die rand sal wees, en dan is die numeriese benamings van sy kenmerke geleë.
Verwysings:
Oor grafieke en algoritmes in die algemeen:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmes: konstruksie en analise, 2de uitgawe: Trans. uit Engels – M.: Williams Publishing House, 2011.
2. Harari Frank. Grafiekteorie. M.: Mir, 1973.
Die skrywer se verslag oor dieselfde vektor en assosiatiewe verskeidenheid van aangrensings:
3. Chernoukhov S.A. Adjacency vektor en assosiatiewe aangrensend skikking as maniere om grafieke voor te stel en te stoor / SA Chernouhov. Aangrensvektor en aangrensingskaart as datastrukture om 'n grafiek voor te stel // Versameling van artikels van die Internasionale Wetenskaplike en Praktiese Konferensie "Probleme met die implementering van die resultate van innoverende ontwikkelings en maniere om dit op te los" (Saratov, 14.09.2019 September 2019). – Sterlitamak: AMI, 65, bl. 69-XNUMX
Nuttige aanlynbronne oor die onderwerp:
4.
5.
Bron: will.com