A szomszédsági lista és a gráf mátrixos ábrázolása

Annak ellenére, hogy másképp néznek ki, mindegyik grafikonok típusai hasonló módon ábrázolható. Általában kétféle grafikonábrázolás létezik:

1. Szomszédsági Mátrix
2. Szomszédsági lista

Szomszédsági lista

A szomszédsági lista Hivatkozott listákból áll. Minden csúcs tömbindexnek számít, és minden elem egy csatolt listát jelent. Ezek a linkelt listák azokat a csúcsokat tartalmazzák, amelyek élei az indexcsúccsal rendelkeznek.

Íme egy példa a szomszédsági listára:

Tegyük fel, hogy egy gráf V számú csúcsot és E számú élt tartalmaz.

Általában a tér összetettsége a következő lesz O(V + E).

A tér bonyolultsága a legrosszabb eset lesz O(V2) ha az adott Graph a teljes Graph

Szomszédsági Mátrix

Az Adjacency Matrix egy 2D tömbből áll. V számú csúcsú grafikonon a mátrix mérete a következő lesz VxV.

Mond, matrix[i][j] = 5. Ez azt jelenti, hogy van egy él az i és a j csomópont között, ahol a súly 5.

Nézzük a következő grafikont és annak szomszédsági mátrixát:

Mi hoztuk létre a 2D tömb a következő lépésekkel:

Step 1) Az A csúcsnak közvetlen éle van B-vel, súlya pedig 5. Tehát az A sor cellája és a B oszlop 5-tel lesz kitöltve. Az A sor többi cellája nullával lesz kitöltve.

Step 2) A B csúcsoknak közvetlen élük van C-vel, súlyuk pedig 4. Tehát a B sor cellája és a C oszlop 4-gyel lesz kitöltve. A B sor többi cellája nullával lesz kitöltve, mivel B-nek nincs kimenő éle egyikhez sem. egyéb csomópontok.

Step 3) A C csúcsoknak nincs közvetlen éle más csúcsokkal. Tehát a C sor nullákkal lesz kitöltve.

Step 4) A D csúcsnak van egy irányított éle A-val és C-vel.

• Itt a D sorban és az A oszlopban lévő cella értéke 7. A D sorban és a C oszlopban lévő cellák értéke 2.
• A D sor többi cellája nullákkal lesz kitöltve.

Step 5) Az E csúcsnak B-vel és D-vel irányított éle van. Az E sorban és a B oszlopban lévő cella értéke 6 lesz. Az E sorban és a D oszlopban lévő cellák értéke 3. A D sor többi cellája tele nullákkal.

Íme néhány észrevétel:

• A gráfnak nincs önhurkja, ha a szomszédsági mátrix elsődleges átlója 0.
• A Graph irányított gráf, ha az (a,b) és (b,a) indexek értéke nem azonos. Ellenkező esetben a Graph egy irányított gráf.
• A Graph súlyozott gráf lesz, ha a cellák értéke nagyobb, mint 1.

Van némi probléma a szomszédsági mátrixszal, mivel négyzetes szóközöket igényel. Itt tároljuk azokat az éleket, amelyek nincsenek összekötve. Ezek az élek foglalnak helyet a memóriában.

Például, ha van egy 100 csomópontos gráfunk, akkor 10 ezer cellára van szükség a tároláshoz a RAM. Ha a grafikonon kevesebb él van, akkora memória lefoglalása pazarlás lehet. Tehát az Adjacency mátrix használatával a tér összetettsége a következő lesz O(N2), ahol N a grafikon csomópontjainak számát jelenti.