A szomszédsági lista és a gráf mátrixos ábrázolása
Szerkesztőség
⚡ Okos összefoglaló
A gráfok szomszédsági listája és mátrixreprezentációja a csúcsokat és éleket a memóriában tárolja, lehetővé téve az algoritmusok számára a hálózatok bejárását. A szomszédsági lista csúcsonként láncolt listákat használ, míg a szomszédsági mátrix egy négyzetes kétdimenziós rácsot használ.
Annak ellenére, hogy másképp néznek ki, mindegyik grafikonok típusai hasonló módon ábrázolható. Általában kétféle gráfreprezentáció létezik:
- Szomszédsági Mátrix
- Szomszédsági lista
Szomszédsági lista
Egy szomszédsági lista láncolt listákból áll. Minden csúcs egy tömbindexnek tekinthető, és minden elem egy láncolt listát jelöl. Ezek a láncolt listák azokat a csúcsokat tartalmazzák, amelyek élükön az indexcsúccsal osztoznak.
Íme egy példa a szomszédsági listára:
Legyen egy gráf V számú csúcsot és E számú élt tartalmaz. A szomszédsági lista térbonyolultsága: O(V + E), amely a valódi élek számával skálázódik, nem pedig minden lehetséges csúcspárral.
A legrosszabb esetben a térbeli komplexitás a következővé válik: O(V²) ha az adott gráf teljes gráf, mivel minden csúcs ezután minden más csúccsal kapcsolódik.
Szomszédsági Mátrix
Egy szomszédsági mátrix egy 2D tömbből áll. Egy V csúcsú gráf esetén a mátrix mérete a következő lesz: V × V.
Mondjuk matrix[i][j] = 5Ez azt jelenti, hogy az i és a j csomópont között van egy él, ahol a súly 5.
Nézzük meg a következő gráfot és annak szomszédsági mátrixát:
Építettük a 2D tömb a következő lépésekkel:
Step 1) Az A csúcsnak közvetlen éle van a B csúcstal, és a súlya 5. Tehát az A sorban és a B oszlopban lévő cellát 5 tölti ki. Az A sor többi celláját nulla tölti ki.
Step 2) A B csúcsnak közvetlen éle van C-vel, és a súlya 4. Tehát a B sorban és a C oszlopban lévő cellát 4 tölti ki. A B sorban lévő többi cellát nulla tölti ki, mivel a B csúcsnak nincs kimenő éle egyetlen más csomóponthoz sem.
Step 3) A C csúcsnak nincsenek közvetlen élei más csúccsal. Tehát a C sor nullákkal lesz kitöltve.
Step 4) A D csúcsnak irányított éle van A-val és C-vel.
- A D sorban és az A oszlopban lévő cella értéke 7 lesz. A D sorban és a C oszlopban lévő cella értéke 2 lesz.
- A D sor többi cellája nullákkal lesz kitöltve.
Step 5) Az E csúcsnak irányított éle van a B és D csúcsokkal. Az E sorban és a B oszlopban lévő cella értéke 6 lesz. Az E sorban és a D oszlopban lévő cella értéke 3 lesz. Az E sor többi cellája nullákkal lesz kitöltve.
Íme néhány észrevétel:
- A gráfnak nincsenek önhurkai, ha a szomszédsági mátrix elsődleges átlója 0.
- Egy gráf irányított gráf, ha az (a, b) és (b, a) cellák nem ugyanazt az értéket tartják. Ellenkező esetben a gráf irányítatlan.
- A grafikon súlyozott grafikon, ha bármelyik cella értéke nagyobb, mint 1.
A szomszédsági mátrix fő problémája, hogy négyzetes helyet igényel. Még a nem létező élek is lefoglalják a cellákat a memóriában.
Például, ha van egy 100 csomópontból álló gráfunk, akkor 10 000 cellára van szükség a tárolásához. RAMKevesebb éllel a gráfban ilyen nagy memória lefoglalása pazarló lehet. Tehát a szomszédsági mátrix használatával a térkomplexitás: O(N²), ahol N a gráfban lévő csomópontok száma.
Szomszédsági lista vs. szomszédsági mátrix
Mielőtt reprezentációt választanánk, érdemes összehasonlítani a két modellt egymás mellett azokon a műveleteken, amelyek a valós gráfterheléseket dominálják:
| OperaCIÓ | Szomszédsági Mátrix | Szomszédsági lista |
|---|---|---|
| A tér összetettsége | O(V²) | O(V + E) |
| Csúcspont hozzáadása | O(V²) | O (1) |
| Él hozzáadása | O (1) | O (1) |
| Él eltávolítása | O (1) | O(E) |
| Ellenőrizd, hogy létezik-e az (i, j) él | O (1) | O (i foka) |
| Iteráció az i szomszédain | O(V) | O (i foka) |
| A legjobb | Sűrű gráfok, gyakori éllekérdezések | Ritka gráfok, bejárás-nehéz feladatok |
Röviden, a szomszédsági mátrix az állandó idejű élkereséseknél nyer, míg a szomszédsági lista a memória- és szomszéditerációnál, ezért az olyan algoritmusok, mint a BFS, a DFS és a Dijkstra, általában szomszédsági listákkal párosulnak.
A gráfreprezentáció előnyei és hátrányai
Minden reprezentációnak megvannak a maga kompromisszumai. Mindkét modell erősségeinek és gyengeségeinek ismerete segít kiválasztani a megfelelőt a megoldandó problémához.
A szomszédsági mátrix előnyei:
- Konstans idejű O(1) él-létezési lekérdezések tetszőleges csúcspár között.
- A fix indexelés megkönnyíti a mátrixalapú algoritmusok, például a Floyd-Warshall és a tranzitív lezárás megvalósítását.
- A súlyozott élek természetesen illeszkednek egyetlen mátrixcellába.
A szomszédsági mátrix hátrányai:
- O(V²) memóriát pazarol, ha a gráf ritka.
- Egy új csúcspont hozzáadása a teljes mátrix átméretezését igényli.
- Egyetlen csúcs szomszédain végigiterálva O(V)-t veszünk fel, még akkor is, ha a csúcsnak csak néhány éle van.
A szomszédsági lista előnyei:
- Csak O(V + E) memóriát használ, ami közel van a ritka gráfok valódi élszámához.
- Egy új csúcs vagy él hozzáadása O(1).
- Az olyan bejárási algoritmusok, mint a BFS és a DFS, O(fokban) iterálják a szomszédokat, így összességében O(V + E) futási időt kapnak.
A szomszédsági lista hátrányai:
- Egy adott él létezésének ellenőrzése O(fok) időt vesz igénybe O(1) helyett.
- A gyorsítótár lokalitása gyengébb, mivel a láncolt listák szétszórva vannak a memóriában.
- A súlyozott élekhez szükség van egy társmezőre vagy párok listájára, ami kissé bonyolítja az adatszerkezetet.
Mikor használjunk szomszédsági listát vs. szomszédsági mátrixot
A reprezentáció megválasztása a gráf sűrűségétől és a leggyakrabban futtatott műveletektől függ. Használja ezt a gyors útmutatót a megfelelő struktúra kiválasztásához:
- A szomszédsági mátrix előnyben részesítése amikor a gráf sűrű (E közel van V²-hez), amikor az élek ritkán változnak, és amikor az algoritmusod sokszor kérdezi meg, hogy „van-e él i és j között?”.
- A szomszédsági listát részesítem előnyben amikor a gráf ritka (E sokkal kisebb, mint V²), amikor a csúcs- vagy élhalmaz növekszik a végrehajtás során, és amikor a gráfot BFS, DFS vagy Dijkstra legrövidebb út algoritmusa.
- Vegyes modellt részesít előnyben (szomszédsági lista plusz élek hash halmaza), amikor gyors szomszédos iterációra és O(1) éllekérdezésekre is szükség van, extra memória rovására.
A modern gráfkönyvtárak, mint például a NetworkX és az igraph, alapértelmezés szerint szomszédsági listákat használnak, mivel a legtöbb valós gráf – közösségi hálózatok, útitervek, weboldalak, csomagfüggőségek – ritkák és bejárás-nehézek.
