Graafin vierekkäisyysluettelo ja matriisiesitys
Sarah Chen
⚡ Älykäs yhteenveto
Graafin vierekkäisyyslista ja matriisiesitys tallentavat solmut ja kaaret muistiin, jolloin algoritmit voivat kulkea verkkojen läpi. Vierekkäisyyslista käyttää linkitettyjä listoja solmukohtaisesti, kun taas vierekkäisyysmatriisi käyttää neliömäistä kaksiulotteista ruudukkoa.
Vaikka ne näyttävätkin erilaisilta, kaikki kaavioiden tyypit voidaan esittää samalla tavalla. Graafiesitystyyppejä on yleensä kaksi:
- Viereisyysmatriisi
- Adjacency-luettelo
Adjacency-luettelo
Vierekkäisyyslista koostuu linkitetyistä listoista. Jokainen solmu on taulukkoindeksi, ja jokainen alkio edustaa linkitettyä listaa. Nämä linkitetyt listat sisältävät solmut, joilla on yhteinen kaari indeksin solmun kanssa.
Tässä on esimerkki vierekkäisyysluettelosta:
Olkoon graafissa V lukumäärä solmuja ja E lukumäärä kaaria. Vierekkäisyyslistan avaruusvaativuus on O(V + E), joka skaalautuu todellisten reunojen lukumäärän mukaan pikemminkin kuin kaikkien mahdollisten kärkiparien mukaan.
Pahimmassa tapauksessa avaruuskompleksisuus muuttuu O(V²) jos annettu graafi on täydellinen graafi, koska jokainen kärki yhdistyy sitten jokaiseen muuhun kärkeen.
Viereisyysmatriisi
Vierekkäisyysmatriisi koostuu 2D-taulukosta. Jos graafissa on V solmua, matriisin koko on V × V.
Sanoa matrix[i][j] = 5Se tarkoittaa, että solmujen i ja j välillä on reuna, jossa paino on 5.
Tarkastellaan seuraavaa graafia ja sen vierekkäisyysmatriisia:
Me rakensimme 2D-taulukko käyttämällä näitä vaiheita:
Vaihe 1) Pisteellä A on suora reuna pisteen B kanssa, ja paino on 5. Niinpä rivin A ja sarakkeen B solu täytetään luvulla 5. Loput rivin A solut täytetään nollalla.
Vaihe 2) Pisteellä B on suora reuna solmun C kanssa, ja paino on 4. Joten rivin B ja sarakkeen C solu täytetään luvulla 4. Rivin B loput solut täytetään nollalla, koska solmulla B ei ole lähtevää reunaa mihinkään muuhun solmuun.
Vaihe 3) Pisteellä C ei ole suoria reunoja minkään muun pisteen kanssa. Joten rivi C täytetään nollilla.
Vaihe 4) Pisteellä D on suunnattu kaari A:n ja C:n kanssa.
- Rivin D ja sarakkeen A solun arvo on 7. Rivin D ja sarakkeen C solun arvo on 2.
- Loput rivin D solut täytetään nollilla.
Vaihe 5) Pisteellä E on suunnattu kaari pisteiden B ja D kanssa. Rivin E ja sarakkeen B solun arvo on 6. Rivin E ja sarakkeen D solun arvo on 3. Loput rivin E solut täytetään nollilla.
Tässä on joitain huomioitavia kohtia:
- Graafi ei solmi itseään silmukoilla, kun vierekkäisyysmatriisin päädiagonaali on 0.
- Graafi on suunnattu graafi, jos solujen (a, b) ja (b, a) arvot eivät ole samat. Muussa tapauksessa graafi on suuntaamaton.
- Graafi on painotettu graafi, jos jonkin solun arvo on suurempi kuin 1.
Vierekkäisyysmatriisin suurin ongelma on, että se vaatii neliöityneen tilan. Jopa olemattomat kaaret varaavat silti soluja muistissa.
Esimerkiksi jos meillä on graafi, jossa on 100 solmua, niin sen tallentamiseen tarvitaan 10 000 solua. RAMKoska graafissa on vähemmän kaaria, niin suuren muistin varaaminen voi olla turhaa. Joten vierekkäisyysmatriisia käytettäessä avaruuskompleksisuus on O(N²), jossa N on solmujen lukumäärä graafissa.
Vierekkäisyysluettelo vs. vierekkäisyysmatriisi
Ennen esityksen valitsemista on hyödyllistä vertailla molempia malleja rinnakkain niiden operaatioiden välillä, jotka hallitsevat todellisia graafikuormia:
| OperaTUKSEN | Viereisyysmatriisi | Adjacency-luettelo |
|---|---|---|
| Avaruuden monimutkaisuus | O(V²) | O(V + E) |
| Lisää kärkipiste | O(V²) | O (1) |
| Lisää reuna | O (1) | O (1) |
| Poista reuna | O (1) | O(E) |
| Tarkista, onko reunaa (i, j) olemassa | O (1) | O (i:n aste) |
| Iteroi i:n naapureiden yli | O (V) | O (i:n aste) |
| Parasta | Tiheät graafit, usein esiintyvät reunakyselyt | Harvat graafit, läpikulkupainotteiset tehtävät |
Lyhyesti sanottuna vierekkäisyysmatriisi voittaa vakioaikaisissa reunahauissa, kun taas vierekkäisyyslista voittaa muistissa ja naapuriteroinnissa, minkä vuoksi algoritmit, kuten BFS, DFS ja Dijkstra, yleensä käyttävät pareja vierekkäisyyslistojen kanssa.
Graafiesityksen edut ja haitat
Jokaisella esitystavalla on omat kompromissinsa. Molempien mallien vahvuuksien ja heikkouksien tunteminen auttaa sinua valitsemaan oikean mallin ratkaisemaasi ongelmaan.
Vierekkäisyysmatriisin edut:
- Vakioaikaiset O(1) reunan olemassaolokyselyt minkä tahansa solmuparin välillä.
- Kiinteä indeksointi tekee matriisipohjaisten algoritmien, kuten Floyd-Warshallin ja transitiivisen sulkeuman, toteuttamisesta helppoa.
- Painotetut reunat sopivat luonnollisesti yhteen matriisisoluun.
Vierekkäisyysmatriisin haitat:
- Tuhlaa O(V²) muistia, kun graafi on harva.
- Uuden kärkipisteen lisääminen vaatii koko matriisin koon muuttamisen.
- Yhden solmun naapureiden yli iterointi vaatii O(V):n, vaikka solmulla olisi vain muutama kaari.
Vierekkäisyyslistan edut:
- Käyttää vain O(V + E)-muistia, joka on lähellä todellista kaarien määrää harvoissa graafeissa.
- Uuden kärkipisteen tai kaaren lisääminen on O(1).
- Läpikulkualgoritmit, kuten BFS ja DFS, iteroivat naapureita O(asteessa), jolloin kokonaissuoritusaika on O(V + E).
Vierekkäisyyslistan haitat:
- Tietyn reunan olemassaolon tarkistaminen vie O (aste) aikaa O(1) sijaan.
- Välimuistin lokaalius on heikompi, koska linkitetyt listat ovat hajallaan muistissa.
- Painotetut reunat tarvitsevat kumppanikentän tai pariluettelon, mikä hieman monimutkaistaa tietorakennetta.
Milloin käyttää vierekkäisyysluetteloa vs. vierekkäisyysmatriisia
Esitystavan valinta riippuu graafin tiheydestä ja useimmin suoritettavista operaatioista. Käytä tätä pikaopasta valitaksesi oikean rakenteen:
- Suosi vierekkäisyysmatriisia kun graafi on tiheä (E on lähellä V²:tä), kun kaaret muuttuvat harvoin ja kun algoritmisi kysyy useita kertoja "onko i:n ja j:n välillä kaaria?".
- Suosi vierekkäisyyttä kun graafi on harva (E on paljon pienempi kuin V²), kun solmu- tai kaarijoukko kasvaa suorituksen aikana ja kun graafia käydään läpi BFS:llä, DFS:llä tai Dijkstran lyhimmän polun algoritmi.
- Mieluummin sekamalli (vieruslista plus hajautusjoukko kaaria), kun tarvitset sekä nopeaa naapurikyselyä että O(1)-reunakyselyitä lisämuistin kustannuksella.
Nykyaikaiset graafikirjastot, kuten NetworkX ja igraph, käyttävät oletusarvoisesti vierekkäisyyslistoja, koska useimmat reaalimaailman graafit – sosiaaliset verkostot, tiekartat, verkkosivut ja pakettiriippuvuudet – ovat harvassa ja läpikulkupainotteisia.
