Graafiku külgnemisloend ja maatriksesitus
Sarah Chen
⚡ Nutikas kokkuvõte
Graafi külgnevusloend ja maatriksi esitus salvestavad tippe ja servi mällu, võimaldades algoritmidel võrgustikke läbida. Külgnevusloend kasutab tipu kohta lingitud loendeid, samas kui külgnevusmaatriks kasutab ruudukujulist kahemõõtmelist ruudustikku.
Kuigi nad näevad välja erinevad, kõik graafikute tüübid saab esitada sarnasel viisil. Üldiselt on kahte tüüpi graafilist esitust:
- Külgnevusmaatriks
- Adjacency nimekiri
Adjacency nimekiri
Kõrvalasuvusloend koosneb lingitud loenditest. Iga tippu peetakse massiivi indeksiks ja iga element esindab lingitud loendit. Need lingitud loendid sisaldavad tippe, mis jagavad serva indekstipuga.
Siin on näide külgnevusloendist:
Olgu graaf V arvu tippe ja E arvu servi. Kõrvutiloendi ruumikeerukus on O(V + E), mis skaleerub pigem reaalsete servade arvuga kui iga võimaliku tippude paariga.
Halvimal juhul muutub ruumi keerukus O(V²) kui antud graaf on täielik graaf, kuna iga tipp ühendub siis iga teise tipuga.
Külgnevusmaatriks
Külgnevusmaatriks koosneb kahemõõtmelisest massiivist. V tipuga graafi korral on maatriksi suurus V × V.
Ütleme matrix[i][j] = 5See tähendab, et sõlmede i ja j vahel on serv, kus kaal on 5.
Vaatleme järgmist graafikut ja selle külgnevusmaatriksit:
Me ehitasime 2D massiiv kasutades neid samme:
Step 1) Tipul A on B-ga otse serv ja tippude kaal on 5. Seega täidetakse rea A ja veeru B lahter arvuga 5. Ülejäänud rea A lahtrid täidetakse nulliga.
Step 2) Tipul B on C-ga otsene serv ja kaal on 4. Seega täidetakse rea B ja veeru C lahter arvuga 4. Ülejäänud rea B lahtrid täidetakse nulliga, kuna tipul B ei ole ühegi teise sõlmega väljuvat serva.
Step 3) Tipul C ei ole otsesid servi ühegi teise tipuga. Seega täidetakse rida C nullidega.
Step 4) Tipul D on suunatud serv A ja C-ga.
- Rea D ja veeru A lahtri väärtus on 7. Rea D ja veeru C lahtri väärtus on 2.
- Ülejäänud rea D lahtrid täidetakse nullidega.
Step 5) Tipul E on suunatud serv tippudega B ja D. Rea E ja veeru B lahtri väärtus on 6. Rea E ja veeru D lahtri väärtus on 3. Ülejäänud rea E lahtrid täidetakse nullidega.
Siin on mõned punktid, mida tähele panna:
- Graafil ei ole isesilmuseid, kui külgnevusmaatriksi primaardiagonaal on 0.
- Graafik on suunatud graaf, kui lahtrid punktides (a, b) ja (b, a) ei oma sama väärtust. Vastasel juhul on graaf suunamata.
- Graafik on kaalutud graafik, kui mis tahes lahtri väärtus on suurem kui 1.
Kõrvusmaatriksi peamine probleem on see, et see nõuab ruutruumi. Isegi servad, mida pole olemas, eraldavad ikkagi mälus lahtreid.
Näiteks kui meil on 100 sõlmega graaf, siis on selle salvestamiseks vaja 10 000 lahtrit. RAMKuna graafikul on vähem servi, võib nii suure mälumahu eraldamine olla raiskav. Seega on külgnevusmaatriksi abil arvutatud ruumi keerukus järgmine: O(N²), kus N on graafiku sõlmede arv.
Kõrvalkohtade loend vs külgnevusmaatriks
Enne esituse valimist on kasulik võrrelda mõlemat mudelit kõrvuti operatsioonide lõikes, mis domineerivad reaalse graafi töökoormuste puhul:
| Operamine | Külgnevusmaatriks | Adjacency nimekiri |
|---|---|---|
| Ruumi keerukus | O(V²) | O(V + E) |
| Lisa tipp | O(V²) | O (1) |
| Lisa serv | O (1) | O (1) |
| Eemalda serv | O (1) | O(E) |
| Kontrolli, kas serv (i, j) eksisteerib | O (1) | O (i aste) |
| Itereeri i naabrite üle | O(V) | O (i aste) |
| Parim on | Tihedad graafikud, sagedased servapäringud | Hõredad graafid, läbimismahukad ülesanded |
Lühidalt, külgnevusmaatriks võidab konstantse ajaga servaotsingutel, samas kui külgnevusloend võidab mälu ja naabri iteratsioonil, mistõttu algoritmid nagu BFS, DFS ja Dijkstra tavaliselt paaristuvad külgnevusloenditega.
Graafi esituse eelised ja puudused
Igal esitusviisil on omad kompromissid. Mõlema mudeli tugevate ja nõrkade külgede tundmine aitab teil valida lahendatava probleemi jaoks õige.
Kõrvalmaatriksi eelised:
- Konstantse ajaga O(1) serva olemasolu päringud mis tahes tippude paari vahel.
- Fikseeritud indekseerimine muudab maatriksipõhised algoritmid, näiteks Floyd-Warshalli ja transitiivse sulgemise, rakendamise lihtsaks.
- Kaalutud servad sobivad loomulikult ühte maatriksi lahtrisse.
Kõrvalmaatriksi puudused:
- Raiskab hõreda graafi korral O(V²) mälu.
- Uue tipu lisamine nõuab kogu maatriksi suuruse muutmist.
- Ühe tipu naabrite kohal itereerimine võtab O(V) isegi siis, kui tipul on ainult mõned servad.
Kõrvalkohtade loendi eelised:
- Kasutab ainult O(V + E) mälu, mis on hõredate graafikute tegeliku servade arvu lähedal.
- Uue tipu või serva lisamine on O(1).
- Läbimisalgoritmid, näiteks BFS ja DFS, itereerivad naabreid O(kraadi) täpsusega, andes kokku O(V + E) jooksuaja.
Külgnevusloendi puudused:
- Konkreetse serva olemasolu kontrollimine võtab O(kraadi) aja O(1) asemel.
- Vahemälu lokaalsus on nõrgem, kuna lingitud loendid on mälus hajutatud.
- Kaalutud servad vajavad kaasvälja või paaride loendit, mis muudab andmestruktuuri veidi keerulisemaks.
Millal kasutada külgnevusloendit vs külgnevusmaatriksit
Esituse valik sõltub graafiku tihedusest ja kõige sagedamini tehtavatest toimingutest. Õige struktuuri valimiseks kasutage seda kiirjuhendit:
- Eelista külgnevusmaatriksit kui graaf on tihe (E on V² lähedal), kui servad harva muutuvad ja kui teie algoritm küsib mitu korda „kas i ja j vahel on serv?“.
- Eelista külgnevate kohtade nimekirja kui graaf on hõre (E on palju väiksem kui V²), kui tippude või servade hulk täitmise ajal kasvab ja kui graafi läbitakse BFS-i, DFS-i või ... abil. Dijkstra lühima tee algoritm.
- Eelista segamudelit (naaberloend pluss servade räsikomplekt), kui vajate nii kiiret naabrite iteratsiooni kui ka O(1) servapäringuid lisamälu hinnaga.
Kaasaegsed graafiteegid, näiteks NetworkX ja igraph, kasutavad vaikimisi külgnevusloendeid, kuna enamik reaalse maailma graafe – sotsiaalvõrgustikud, teekaardid, veebilehed, pakettide sõltuvused – on hõredad ja nõuavad palju läbimist.
