Diagrammas datu struktūra

Satura rādītājs

Grafiku terminoloģija
Grafika attēlojums
Grafika darbības

Šajā apmācībā jūs uzzināsiet, kas ir diagrammas datu struktūra. Jūs atradīsit arī diagrammas attēlojumus.

Diagrammas datu struktūra ir mezglu kopums, kuriem ir dati un kuri ir savienoti ar citiem mezgliem.

Mēģināsim to saprast, izmantojot piemēru. Facebook vietnē viss ir mezgls. Tas ietver lietotāju, fotoattēlu, albumu, notikumu, grupu, lapu, komentāru, stāstu, video, saiti, piezīmi … viss, kam ir dati, ir mezgls.

Katra attiecība ir mala no viena mezgla uz otru. Neatkarīgi no tā, vai jūs ievietojat fotoattēlu, pievienojaties grupai, piemēram, lapai utt., Šīm attiecībām tiek izveidota jauna mala.

Grafu datu struktūras piemērs

Tad viss facebook ir šo mezglu un malu kolekcija. Tas ir tāpēc, ka facebook datu glabāšanai izmanto diagrammas datu struktūru.

Precīzāk, grafiks ir datu struktūra (V, E), kas sastāv no

Virsotņu kolekcija V
Malu kolekcija E, kas attēlota kā sakārtoti virsotņu pāri (u, v)

Virsotnes un malas

Diagrammā

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

Grafiku terminoloģija

Blakusparādības : Tiek teikts, ka virsotne atrodas blakus citai virsotnei, ja tās savieno mala. 2. un 3. virsotne nav blakus, jo starp tām nav malas.
Ceļš : Malu secību, kas ļauj pāriet no A virsotnes uz B virsotni, sauc par ceļu. 0-1, 1-2 un 0-2 ir ceļi no 0 virsotnes līdz 2 virsotnei.
Virzīts grafiks : grafiks, kurā mala (u, v) nenozīmē, ka ir arī mala (v, u). Šādas diagrammas malas ir attēlotas ar bultiņām, lai parādītu malas virzienu.

Grafika attēlojums

Diagrammas parasti tiek attēlotas divos veidos:

1. Adjacency Matrix

Blakus esošā matrica ir 2 x V x V virsotņu masīvs. Katra rinda un kolonna apzīmē virsotni.

Ja jebkura elementa vērtība a(i)(j)ir 1, tas norāda, ka ir mala, kas savieno virsotni i un virsotni j.

Iepriekš izveidotā grafika blakusesības matrica ir

Grafiks blakus esošās matricas

Tā kā tas ir nenovirzīts grafiks, malai (0,2) mums jāatzīmē arī mala (2,0); padarot blakusefekta matricu simetrisku attiecībā uz diagonāli.

Malu meklēšana (pārbaudot, vai starp virsotni A un virsotni B ir mala) ir ārkārtīgi ātra blakus esošās matricas attēlojumā, taču mums ir jārezervē vieta visām iespējamām saitēm starp visām virsotnēm (V x V), tāpēc tas prasa vairāk vietas.

2. Adjacency saraksts

Blakus esošais saraksts attēlo diagrammu kā saistītu sarakstu masīvu.

Masīva indekss apzīmē virsotni, un katrs elements saistītajā sarakstā apzīmē citas virsotnes, kas veido malu ar virsotni.

Pirmajā piemērā izveidotā diagrammas blakusesošais saraksts ir šāds:

Blakusparādību saraksta attēlojums

Blakus esošais saraksts ir efektīvs uzglabāšanas ziņā, jo mums ir jāuzglabā tikai malu vērtības. Grafikam ar miljoniem virsotņu tas var nozīmēt daudz ietaupītas vietas.