Hei kaikki
Tässä muistiinpanossa päätin listata tärkeimmät tietorakenteet, joita käytetään tietojenkäsittelytieteen graafien tallentamiseen, ja puhun myös parista muusta sellaisesta rakenteesta, jotka jotenkin "kiteytyivät" minulle.
Joten aloitetaan. Mutta ei aivan alusta lähtien - luulen, että me kaikki tiedämme jo mikä graafi on ja mitä ne ovat (suunnattu, suuntaamaton, painotettu, painottamaton, useilla reunoilla ja silmukoilla tai ilman).
Mennään siis. Mitä vaihtoehtoja tietorakenteille "kaavion tallennusta" varten meillä on?
1. Matriisitietorakenteet
1.1 Vierekkäisyysmatriisi. Vierekkäisyysmatriisi on matriisi, jossa rivi- ja sarakeotsikot vastaavat graafin kärkien lukuja ja sen kunkin elementin a(i,j) arvon määrää kärkien välisten reunojen olemassaolo tai puuttuminen. i ja j (on selvää, että suuntaamattomalle graafille tällainen matriisi on symmetrinen, tai voimme sopia, että tallennamme kaikki arvot vain päädiagonaalin yläpuolelle). Painottamattomille graafille a(i,j) voidaan asettaa reunojen lukumäärällä i:stä j:ään (jos sellaista ei ole, niin a(i,j)= 0) ja painotetuissa graafisissa myös painolla. (kokonaispaino) mainittujen reunojen.
1.2 Ilmaantuvuusmatriisi. Tässä tapauksessa myös graafimme on tallennettu taulukkoon, jossa pääsääntöisesti rivinumerot vastaavat sen kärkien numeroita ja sarakkeiden numerot vastaavat esinumeroituja reunoja. Jos kärki ja reuna kohtaavat toisiaan, niin vastaavaan soluun kirjoitetaan nollasta poikkeava arvo (suuntaamattomien graafien kohdalla kirjoitetaan 1, jos kärki ja reuna ovat sattuvia, suuntautuneille graafiille - "1", jos reuna "poistuu" kärjestä ja "-1", jos se "sisältyy" siihen (se on tarpeeksi helppo muistaa, koska "miinus"-merkki näyttää myös olevan "sisältyy" numeroon "-1"). Painotetuille kaavioille voit jälleen määrittää reunan kokonaispainon 1:n ja -1:n sijaan.
2. Luettelotietorakenteet
2.1 Lähialueluettelo. No, kaikki näyttää olevan yksinkertaista täällä. Kukin graafin kärkipiste voidaan yleensä liittää mihin tahansa laskentarakenteeseen (lista, vektori, taulukko, ...), joka tallentaa kaikkien annetun pisteen vieressä olevien pisteiden numerot. Suunnattujen graafien kohdalla lisäämme tällaiseen luetteloon vain ne kärjet, joihin on "suunnattu" reuna piirrepisteestä. Painotettujen kaavioiden toteutus on monimutkaisempaa.
2.2 Luettelo kylkiluista. Melko suosittu tietorakenne. Reunojen luettelo, kuten Captain Obviousness kertoo, on itse asiassa luettelo graafin reunoista, joista jokainen määritellään aloituspisteellä, loppupisteellä (ohjaamattomien graafien kohdalla järjestyksellä ei ole merkitystä, vaikka yhdistämisessä voit Käytä erilaisia sääntöjä, esimerkiksi määrittämällä kärjet kasvavassa järjestyksessä) ja painoa (vain painotetuille kaavioille).
Voit tarkastella yllä lueteltuja matriisiluetteloita tarkemmin (ja kuvituksella), esim. .
2.3 Vierekkäisyysryhmä. Ei yleisin rakenne. Pohjimmiltaan se on eräänlainen vierekkäisyysluetteloiden "pakkaaminen" yhdeksi luettelorakenteeksi (taulukko, vektori). Tällaisen taulukon ensimmäiset n (graafin kärkien lukumäärän mukaan) elementtiä sisältävät saman taulukon aloitusindeksit, joista alkaen kaikki annetun pisteen vieressä olevat pisteet kirjoitetaan riviin.
Täältä löysin (itselleni) ymmärrettävimmän selityksen:
3. Vierekkäisyysvektori ja assosiatiivinen vierekkäisyystaulukko
Kävi ilmi, että näiden rivien kirjoittaja, joka ei ollut ammattiohjelmoija, mutta joka ajoittain käsitteli graafia, käsitteli useimmiten reunaluetteloita. Itse asiassa on kätevää, jos graafissa on useita silmukoita ja reunoja. Ja niinpä klassisia reunuslistoja kehitettäessä ehdotan, että kiinnitetään huomiota niiden "kehitykseen/haaraan/muokkaukseen/mutaatioon", nimittäin: viereisyysvektoriin ja assosiatiiviseen viereisyystaulukkoon.
3.1 Vierekkäisyysvektori
Tapaus (a1): painottamaton kaavio
Kutsumme painottamattoman graafin vierekkäisyysvektoriksi parillisen määrän kokonaislukuja (a[2i], a[2i+1],..., jossa i on numeroitu c 0), jossa jokainen lukupari on a[2i], a[2i+1 ] määrittää graafin reunan pisteiden a[2i] ja a[2i+1] välillä, vastaavasti.
Tämä tallennusmuoto ei sisällä tietoja siitä, onko kuvaaja suunnattu (molemmat vaihtoehdot ovat mahdollisia). Digrafimuotoa käytettäessä reunan katsotaan olevan suunnattu kohdasta a[2i] kohtaan a[2i+1]. Tässä ja alla: suuntaamattomiin graafisiin voidaan tarvittaessa soveltaa vaatimuksia tallennuksen pisteiden järjestyksestä (esimerkiksi, että kärki, jolla on pienempi arvo sille osoitetusta numerosta, tulee ensin).
C++:ssa on suositeltavaa määrittää viereisyysvektori käyttämällä std::vectoria, josta tämän tietorakenteen nimi.
Tapaus (a2): painottamaton graafi, reunapainot ovat kokonaislukuja
Analogisesti tapauksen (a1) kanssa kutsumme kokonaislukureunapainotteisen painotetun graafin viereisyysvektoria järjestetyksi numerojoukoksi (dynaaminen matriisi) (a[3i], a[3i+1], a[3i+2], ..., jossa i on numeroitu c 0), jossa jokainen lukujen a[3i], a[3i+1], a[3i+2] "tripletti" määrittelee graafin reunan numeroiden a[3i] kärkien välillä. ja a[3i+1], vastaavasti, ja arvo a [3i+2] on tämän reunan paino. Tällainen graafi voi myös olla joko suunnattu tai ei.
Tapaus (b): painottamaton graafi, ei-kokonaislukujen reunapainotukset
Koska heterogeenisia elementtejä on mahdotonta tallentaa esimerkiksi yhteen taulukkoon (vektoriin), seuraava toteutus on mahdollinen. Graafi on tallennettu vektoripariin, jossa ensimmäinen vektori on graafin viereisyysvektori ilman painoja ja toinen vektori sisältää vastaavat painot (mahdollinen toteutus C++:lle: std::pair ). Siten ensimmäisen vektorin indeksien 2i, 2i+1 alaisen kärkiparin määrittelemän reunan paino on yhtä suuri kuin toisen vektorin indeksin i alla oleva elementti.
No miksi tämä on tarpeellista?
No, näiden rivien kirjoittaja piti sitä varsin hyödyllisenä useiden ongelmien ratkaisemisessa. No, muodollisesta näkökulmasta katsottuna, sillä on seuraavat edut:
- Viereisyysvektori, kuten mikä tahansa muukin "enumeratiivinen" rakenne, on melko kompakti, vie vähemmän muistia kuin vierekkäisyysmatriisi (harvoille kaavioille) ja se on suhteellisen helppo toteuttaa.
- Graafin kärjet voidaan periaatteessa merkitä myös negatiivisilla luvuilla. Entä jos tällaista "perversiota" tarvitaan?
- Kaaviot voivat sisältää useita reunoja ja useita silmukoita eri painoilla (positiivinen, negatiivinen, jopa nolla). Täällä ei ole rajoituksia.
- Voit myös määrittää reunoille erilaisia ominaisuuksia - mutta lisää siitä kohdasta 4.
On kuitenkin myönnettävä, että tämä "luettelo" ei tarkoita nopeaa pääsyä reunaan. Ja tässä Associative Adjacency Array tulee apuun, jota käsitellään alla.
3.2 Assosiatiivinen viereisyystaulukko
Joten jos pääsy tiettyyn reunaan, sen painoon ja muihin ominaisuuksiin on meille kriittistä ja muistivaatimukset eivät salli viereisyysmatriisin käyttöä, niin mietitään kuinka voimme muuttaa viereisyysvektoria tämän ongelman ratkaisemiseksi. Avain on siis graafin reuna, joka voidaan määritellä järjestetyksi kokonaislukupariksi. Miltä tämä näyttää? Eikö se ole avain assosiatiivisessa taulukossa? Ja jos on, miksi emme pane sitä täytäntöön? Otetaan assosiatiivinen matriisi, jossa jokainen avain - järjestetyssä kokonaislukuparissa - liitetään arvoon - kokonaisluku tai reaaliluku, joka määrittää reunan painon. C++:ssa on suositeltavaa toteuttaa tämä rakenne perustuen std::map-säilöön (std::map , int> tai std::map , double>), tai std::multimap, jos useita reunoja odotetaan. No, meillä on graafien tallennusrakenne, joka vie vähemmän muistia kuin "matriisi"-rakenteet, pystyy määrittelemään graafit, joissa on useita silmukoita ja reunoja, eikä sillä ole edes tiukkoja vaatimuksia kärkilukujen ei-negatiivisuudelle (en tiedä kuka tätä tarvitsee, mutta silti).
4. Tietorakenteet ovat täynnä, mutta jotain puuttuu
Ja se on totta: kun ratkaisemme useita tehtäviä, meidän on ehkä osoitettava joitain ominaisuuksia graafin reunoihin ja vastaavasti tallennettava ne. Jos on mahdollista pelkistää nämä piirteet yksiselitteisesti kokonaisluvuiksi, on mahdollista tallentaa tällaisia "lisäominaisuuksilla varustettuja kaavioita" käyttämällä viereisyysvektorin ja assosiatiivisen viereisyystaulukon laajennettuja versioita.
Otetaan siis painottamaton graafi, jonka jokaiselle reunalle on tarpeen tallentaa esim. 2 kokonaisluvuilla määriteltyä lisäominaisuutta. Tässä tapauksessa on mahdollista määritellä sen viereisyysvektori järjestetyksi joukoksi, joka ei ole "pareja", vaan kokonaislukujen "kvartettia" (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , jossa a[2i+2] ja a[2i+3] määrittävät vastaavan reunan ominaisuudet. Graafissa, jossa on reunojen kokonaislukupainot, järjestys on yleensä samanlainen (ainoa ero on, että attribuutit seuraavat reunan painoa ja määritetään elementeillä a[2i+3] ja a[2i+4] , ja itse reuna ei määritetä 4, vaan 5 järjestettyä numeroa). Ja graafin, jossa on ei-kokonaislukujen reunapainot, piirteet voidaan kirjoittaa sen painottamattomaan komponenttiin.
Käytettäessä assosiatiivista vierekkäisyystaulukkoa graafille, jossa on kokonaislukujen reunapainot, on mahdollista määrittää arvoksi ei yksittäinen luku, vaan numerotaulukko (vektori), joka määrittää reunan painon lisäksi sen kaikki muut tarpeelliset ominaisuudet. Samaan aikaan haittana ei-kokonaislukupainojen tapauksessa on tarve määrittää merkki liukulukulla (kyllä, tämä on haitta, mutta jos tällaisia merkkejä ei ole niin paljon ja jos et Älä aseta niitä liian "hankaliksi" kaksinkertaisiksi, niin se voi olla mitään) . Tämä tarkoittaa, että C++:ssa laajennetut assosiatiiviset viereisyystaulukot voidaan määritellä seuraavasti: std::map , std::vektori> tai std::kartta , std::vector, jossa "avainarvo-vektorin" ensimmäinen arvo on reunan paino, ja sitten sijaitsevat sen ominaisuuksien numeeriset nimet.
Viitteet:
Tietoja kaavioista ja algoritmeista yleensä:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmit: rakentaminen ja analyysi, 2. painos: Trans. englannista – M.: Williams Publishing House, 2011.
2. Harari Frank. Graafiteoria. M.: Mir, 1973.
Tekijän raportti näistä samasta vektorista ja assosiatiivisesta vierekkäisyydestä:
3. Chernoukhov S.A. Vierekkäisyysvektori ja assosiatiivinen viereisyystaulukko tapoina esittää ja tallentaa kaavioita / SA Chernouhov. Vierekkäisyysvektori ja viereisyyskartta datarakenteina kuvaamaan kuvaajaa // Kansainvälisen tieteellisen ja käytännön konferenssin artikkelikokoelma "Innovatiivisten kehitysten tulosten toteuttamisen ongelmat ja niiden ratkaisutavat" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, s. 65-69
Hyödyllisiä verkkolähteitä aiheesta:
4.
5.
Lähde: will.com