Datu struktūras grafiskais attēlojums – Graphs

Apsverot konkrētu problēmu datorzinātnēs, vienmēr ir svarīgi apsvērt, kādas izpildes varētu būt nepieciešamas, lai atrisinātu jūsu problēmu. Izmantojot šo pārdomu, izvēlieties atbilstošu datu struktūru savu datu glabāšanai. Apsveriet, ka jūs varētu strādāt lielā interneta uzņēmumā, kas vēlas saglabāt atrašanās vietu un to savstarpējo savienojumu direktoriju.

Šajā ilustrācijā pilsētas ir attēlotas viena pret otru. Ievērojiet, ka nav jāreģistrē visas iespējamās detaļas. Piemēram, jūs vēlaties uzzināt, cik tālu ir Čikāga no Bostonas. To var viegli secināt no datu organizēšanas veida. To pašu pieeju var izmantot, lai modelētu interneta galamērķus, attiecības starp vārdiem vai cilvēkiem sociālajā tīklā. Šī pieeja informācijas saglabāšanai ir uz grafiku balstīta pieeja.

Šī struktūras ilustrācija ir diagramma (graph), kas sastāv no mezgliem (nodes), lai apzīmētu galamērķus un malas (edges), kas parāda, kā katrs mezgls ir saistīts ar citu. Vērtību klātbūtne starp mezgliem nozīmē, ka šis ir svērtais grafiks (weighted graph). Nav bultiņu, kas nozīmē, ka šis ir nevirzīts grafiks (undirected graph). Pretstatā virzītam grafikam un nevirzītam grafikam nav prioritātes secības (no order of precedence).

Viens veids, kā domāt par virzītiem un nevirzītiem grafikiem, ir kā divvirzienu (two way) un vienvirziena (one way) ielas. Dažreiz tas palīdz, pasūtot datus, lai izceltu kādu progresu. Citos gadījumos malas ir tikai tāpēc, lai parādītu saistību. Tad daļa ir divu vai vairāku mezglu secība, kas savienoti ar malu. Savienojums virzītā grafā tiek uzskatīts par vāji savienotu, ja mala ir tikai vienvirziena. Tomēr, ja starp diviem mezgliem ir divi savienojumi, tiek uzskatīts, ka tie ir cieši saistīti. Šajā brīdī jūs, iespējams, domājat, ka grafiks atgādina koku. Dažos veidos var teikt, ka koks ir vienkāršs grafiks. Jo īpaši kokam ir sākuma punkts, un tas veido hierarhiju ar vecākiem un bērniem. Grafiks ir daudz sarežģītāka struktūra, kurai nav ne sākuma, ne beigu. Divus mezglus, kas robežojas viens ar otru, sauc par kaimiņiem (Neighbors), un mezglus, kas ir savienoti caur kaimiņu, sauc par blakus (Adjacent).

Grafikus, piemēram, kokus, vispirms var šķērsot platumā (Breadth first) un vispirms dziļumā. Ņemiet vērā, ka vispirms meklējat platumā, apmeklējiet katru mezglu tajā pašā līmenī, pēc tam dodieties zemāk, un pirmā dziļuma meklēšana ietver katra atzara gala izurbšanu (drill), pirms pāriet uz nākamo. Pirmā pieeja ietver noteiktas sākuma vietas izvēli un atkārtošanu visos blakus esošajos mezglos. Katram kaimiņam būs savienotu mezglu savienojums, ko var pievienot citai jau minētajai datu struktūrai. Rinda (Queue), tādā veidā, jūs varat sistemātiski apmeklēt katru mezglu. Lai sasniegtu dziļu pirmo meklēšanu, varat izmantot kaudzi. Mēs saucam steku apstrādā elementus savādāk nekā rindu. Kamēr rindā prioritāte ir FIFO – pirmais ienāk, pirmais iziet (First In -First Out), kaudze koncentrējas uz pēdējo ienākošo, pēdējo ārā (Last in, Last Out). Tātad, sistemātiski novietojot visus blakus esošos mezglus kaudzē, jūs nodrošinātu pirmo dziļuma šķērsošanu. Grafiki ir daudz pētīta datu struktūra, un tie ir daudzu algoritmu pamatā, kas izstrādāti, lai noteiktu svarīgumu starp mezgliem. Neatkarīgi no mezglā glabātā elementa viens ievērojams ir īsākais ceļš. Kāds ir ātrākais veids, kā nokļūt no mezgla A uz mezglu E? Malu atsvari informēs par katra ceļa izvēles izmaksām. Šo pieeju izmanto, maršrutējot interneta pakotnes internetā vai aprēķinot braucienu pakalpojumā Google Maps.

Vēl viens izplatīts uz grafiku balstīts izaicinājums ir ceļojošs pārdevējs. Pārdevējam ir jāapmeklē daži mezgli. Kāds ir labākais maršruts, kas sasniedz visus mezglus īsākā laikā. Tas tiks izmantots pakešu maršrutēšanā, ja ir x mērķi, un y transportlīdzekļi izstrādā visefektīvāko maršrutu, lai visas pakas tiktu piegādātas ar vismazāko resursu patēriņu.

Šajā rakstā jūs uzzinājāt, kā diagrammas grafiki, jeb graphs sniedz iespēju elastīgi modelēt datus, kas atvieglo informācijas izsecināšanu par datiem pēc to glabāšanas veida. Šī daudzpusīgā pieeja tikai saglabā minimālu informāciju. Attālums no Čikāgas līdz Bostonai nekur nav glabāts, bet to var izsecināt izpētot graphs. Ir viegli uzdot dažādus jautājumus, nemainot datu struktūru. Ir bijusi vesela statistikas joma, kas veltīta informācijas secināšanai no mezglu izvietojumiem, ko var izmantot, lai izdarītu secinājumus par jebkuriem tur glabātajiem datiem.