Štruktúra dát grafu

Obsah

Terminológia grafov
Grafové znázornenie
Grafické operácie

V tomto návode sa dozviete, čo je to grafová dátová štruktúra. Nájdete tiež znázornenie grafu.

Grafová dátová štruktúra je súbor uzlov, ktoré majú údaje a sú spojené s inými uzlami.

Pokúsme sa to pochopiť na príklade. Na facebooku je všetko uzol. To zahŕňa používateľa, fotografiu, album, udalosť, skupinu, stránku, komentár, príbeh, video, odkaz, poznámku … všetko, čo má údaje, je uzol.

Každý vzťah je výhodou z jedného uzla do druhého. Či už zverejníte fotografiu, pripojíte sa k skupine, napríklad na stránku atď., Pre tento vzťah sa vytvorí nový okraj.

Ukážka dátovej štruktúry grafu

Celý facebook je potom súborom týchto uzlov a hrán. Je to tak preto, lebo facebook používa na ukladanie svojich údajov dátovú štruktúru grafu.

Presnejšie povedané, graf je dátová štruktúra (V, E), ktorá sa skladá z

Zbierka vrcholov V
Súbor hrán E, predstavovaných ako usporiadané páry vrcholov (u, v)

Vrcholy a hrany

V grafe

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Terminológia grafov

Susedstvo : O vrchole sa hovorí, že susedí s iným vrcholom, ak ich spája hrana. Vrcholy 2 a 3 nesusedia, pretože medzi nimi nie je hrana.
Cesta : Postupnosť hrán, ktorá vám umožňuje prechádzať z vrcholu A na vrchol B, sa nazýva cesta. 0-1, 1-2 a 0-2 sú cesty od vrcholu 0 k vrcholu 2.
Smerovaný graf : Graf, v ktorom hrana (u, v) nemusí nutne znamenať, že existuje aj hrana (v, u). Okraje v takom grafe sú znázornené šípkami, ktoré ukazujú smer okraja.

Grafové znázornenie

Grafy sú bežne znázornené dvoma spôsobmi:

1. Matica susedstva

Matica susednosti je 2D pole V x V vrcholov. Každý riadok a stĺpec predstavuje vrchol.

Ak je hodnota ľubovoľného prvku a(i)(j)1, znamená to, že existuje hrana spájajúca vrchol i a vrchol j.

Matica susednosti pre graf, ktorý sme vytvorili vyššie, je

Matica susednosti grafu

Pretože ide o neorientovaný graf, pre hranu (0,2) musíme tiež označiť hranu (2,0); čím je matica susedstva symetrická okolo uhlopriečky.

Vyhľadanie okraja (kontrola, či existuje hrana medzi vrcholom A a vrcholom B) je v zobrazovaní susednej matice extrémne rýchla, ale musíme si vyhradiť priestor pre každé možné spojenie medzi všetkými vrcholmi (V x V), takže si vyžaduje viac priestoru.

2. Zoznam susedov

Zoznam susedstiev predstavuje graf ako pole prepojených zoznamov.

Index poľa predstavuje vrchol a každý prvok v jeho prepojenom zozname predstavuje ďalšie vrcholy, ktoré tvoria hranu s vrcholom.

Zoznam susedstiev pre graf, ktorý sme vytvorili v prvom príklade, je nasledovný:

Reprezentácia zoznamu susedov

Zoznam susedstiev je efektívny z hľadiska ukladania, pretože musíme ukladať iba hodnoty pre okraje. Pre graf s miliónmi vrcholov to môže znamenať veľa ušetreného miesta.