Ebben az oktatóanyagban megtudhatja, mi a Graph Data Structure. Megtalálja a grafikon ábrázolását is.
A grafikon adatstruktúrája olyan csomópontok gyűjteménye, amelyek rendelkeznek adatokkal és kapcsolódnak más csomópontokhoz.
Próbáljuk megérteni ezt egy példán keresztül. A facebookon minden egy csomópont. Ebbe beletartozik a Felhasználó, Fotó, Album, Esemény, Csoport, Oldal, Megjegyzés, Történet, Videó, Link, Megjegyzés … bármi, aminek vannak adatai, az egy csomópont.
Minden kapcsolat él egy csomópontból a másikba. Akár fotót posztol, akár csatlakozik egy csoporthoz, például oldalhoz, stb., A kapcsolat új éllelést hoz létre.
Példa a grafikon adatszerkezetére
Az egész facebook ezeknek a csomópontoknak és éleknek a gyűjteménye. A facebook ugyanis grafikon adatszerkezetet használ az adatok tárolásához.
Pontosabban, a grafikon egy adatszerkezet (V, E), amely abból áll
- V csúcsok gyűjteménye
- Az E élek gyűjteménye, rendezett csúcspárokként ábrázolva (u, v)
Csúcsok és élek
A grafikonon
V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)
Grafikon terminológia
- Adjacency : Azt mondják, hogy egy csúcs szomszédos egy másik csúccsal, ha van egy él, amely összeköti őket. A 2. és 3. csúcs nem szomszédos, mert nincs él közöttük.
- Útvonal : Az élek sorozatát, amely lehetővé teszi az A csúcsból a B csúcsba való továbbjutást, ún. A 0-1, 1-2 és 0-2 a 0 csúcs és a 2 csúcs közötti útvonal.
- Irányított gráf : Olyan gráf, amelyben egy él (u, v) nem feltétlenül jelenti azt, hogy van egy él (v, u) is. Az ilyen grafikon éleit nyilakkal ábrázolják, hogy megmutassák az él irányát.
Grafikon ábrázolása
A grafikonokat általában kétféleképpen ábrázolják:
1. Adjacencia mátrix
A szomszédsági mátrix a V x V csúcsok 2D-s tömbje. Minden sor és oszlop egy csúcsot képvisel.
Ha bármely elem a(i)(j)értéke 1, akkor ez azt jelenti, hogy van egy él, amely összeköti az i és a j csúcsot.
A fenti grafikon szomszédsági mátrixa az
Grafikon szomszédsági mátrix
Mivel irányítatlan gráfról van szó, a (0,2) élhez szintén meg kell jelölnünk az élt (2,0); szimmetrissé téve a szomszédsági mátrixot az átlóra.
Az élkeresés (annak ellenőrzése, hogy van-e él az A és B csúcs között) rendkívül gyors a szomszédsági mátrix ábrázolásában, de helyet kell fenntartanunk az összes csúcs közötti minden lehetséges kapcsolatra (V x V), így több helyet igényel.
2. Adjacency List
A szomszédsági lista a grafikont összekapcsolt listák tömbjeként ábrázolja.
A tömb indexe egy csúcsot képvisel, és az összekapcsolt listában szereplő minden elem a többi csúcsot jelöli, amelyek élt alkotnak a csúccsal.
Az első példában készített grafikon szomszédsági listája a következő:
Adjacency lista ábrázolása
A szomszédsági lista tárolás szempontjából hatékony, mert csak az élek értékeit kell tárolnunk. Több millió csúcsot tartalmazó grafikon számára ez sok megtakarított helyet jelenthet.
Grafikonműveletek
A leggyakoribb grafikonműveletek a következők:
- Ellenőrizze, hogy az elem szerepel-e a grafikonon
- Grafikon bejárása
- Adjon elemeket (csúcs, élek) a grafikonhoz
- Az egyik csúcsból a másikba vezető út megtalálása
