Struktura podataka grafikona

Sadržaj

Grafička terminologija
Prikaz grafikona
Grafičke operacije

U ovom uputstvu naučit ćete što je struktura podataka grafikona. Također ćete naći prikaze grafa.

Graf podataka struktura je skup čvorova koji imaju podatke i povezani su s drugim čvorovima.

Pokušajmo to razumjeti na primjeru. Na facebooku je sve čvor. To uključuje korisnika, fotografiju, album, događaj, grupu, stranicu, komentar, priču, video, vezu, bilješku … sve što ima podatke je čvor.

Svaka veza je rub od jednog čvora do drugog. Bez obzira objavite li fotografiju, pridružite li se grupi, poput stranice itd., Za tu vezu stvara se novi rub.

Primjer strukture podataka grafa

Čitav facebook je tada zbirka tih čvorova i rubova. To je zato što facebook za pohranu podataka koristi strukturu podataka grafikona.

Točnije, graf je struktura podataka (V, E) koja se sastoji od

Zbirka vrhova V
Zbirka bridova E, predstavljena kao uređeni parovi vrhova (u, v)

Vrhovi i rubovi

Na grafikonu,

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

Grafička terminologija

Susjednost : Za vrh se kaže da je u susjedstvu s drugim vrhom ako postoji rub koji ih povezuje. Vrhovi 2 i 3 nisu susjedni jer između njih nema ruba.
Put : Slijed bridova koji vam omogućuje da prijeđete iz vrha A u vrh B naziva se put. 0-1, 1-2 i 0-2 putovi su od vrha 0 do vrha 2.
Usmjereni graf : Grafikon u kojem rub (u, v) ne mora nužno značiti da postoji i rub (v, u). Rubovi su u takvom grafikonu strelicama prikazani u smjeru ruba.

Prikaz grafikona

Grafovi su obično predstavljeni na dva načina:

1. Matrica susjedstva

Matrica susjedstva je 2D niz V x V vrhova. Svaki redak i stupac predstavljaju vrh.

Ako je vrijednost bilo kojeg elementa a(i)(j)1, to znači da postoji rub koji povezuje vrh i i vrh j.

Matrica susjednosti za grafikon koji smo gore stvorili je

Matrica susjedstva grafa

Budući da se radi o neusmjerenom grafu, za rub (0,2) također moramo označiti rub (2,0); čineći matricu susjedstva simetričnom oko dijagonale.

Traženje ruba (provjera postoji li rub između vrha A i vrha B) izuzetno je brzo u predstavljanju matrice susjedstva, ali moramo rezervirati prostor za svaku moguću vezu između svih vrhova (V x V), pa zahtijeva više prostora.

2. Popis susjedstva

Popis susjedstva predstavlja graf kao niz povezanih popisa.

Indeks niza predstavlja vrh, a svaki element na povezanom popisu predstavlja ostale vrhove koji tvore rub s vrhom.

Popis susjednosti za graf koji smo napravili u prvom primjeru je sljedeći:

Zastupljenost popisa susjedstva

Popis susjednosti učinkovit je u smislu pohrane, jer trebamo pohraniti samo vrijednosti za rubove. Za graf s milijunima vrhova to može značiti puno spremljenog prostora.