Sissejuhatus andmestruktuuri graafikusse

Graafikud on mittelineaarsed andmestruktuurid, mis koosnevad piiratud hulga sõlmedest ja servadest. Sõlmed on elemendid ja servad on järjestatud paarisühendustena sõlmede vahel.

Pange tähele sõna mittelineaarset. Mittelineaarne andmestruktuur on selline, kus elemendid ei ole järjestatud järjestikuses järjekorras. Näiteks massiiv on lineaarne andmestruktuur, kuna elemendid on paigutatud üksteise järel. Massiivi kõik elemendid saate läbida ühe korraga. Mittelineaarsete andmestruktuuride puhul see nii pole. Mittelineaarse andmestruktuuri elemendid on paigutatud mitmel tasandil, järgides sageli hierarhilist mustrit. Graafikud on mittelineaarsed.

Järgmine sõna, millele tähelepanu tuleb pöörata, on piiratud. Me defineerime graafiku nii, et sellel oleks piiratud ja loendatav arv sõlmi. See on üsna mittemõistetav termin. Põhimõtteliselt võib graafil olla lõpmatu arv sõlmi ja see võib siiski olla piiratud. Näiteks perepuu, ulatudes Aadama ja Eevani. See on suhteliselt lõpmatu graaf, kuid on siiski loendatav ja seetõttu peetakse seda lõplikuks.

Reaalse maailma näide

Parim näide reaalainete graafikutest on Facebook. Iga inimene Facebookis on sõlm ja on ühendatud servade kaudu. A on B. sõber. B on C sõber ja nii edasi.

Terminoloogia

Siin on allpool mainitud andmestruktuuri graafiku terminid

1. Graafiku esitus: graafik on üldiselt esitatud komplektide paarina (V, E). V on tippude või sõlmede kogum. E on servade kogum. Ülaltoodud näites
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)

2. Sõlm või Vertex: graafi elemendid on ühendatud servade kaudu.

3. Servad: tee või joon graafi kahe tipu vahel.

4. Külgnevad sõlmed: kahte sõlme nimetatakse külgnevaks, kui need on ühendatud serva kaudu. Ülaltoodud näites on sõlme A külgnev sõlmedega B, C ja D, kuid mitte sõlmega E.

5. Tee: tee on servajada kahe sõlme vahel. See on sisuliselt läbisõit, mis algab ühest sõlmest ja lõpeb teisest. Ülaltoodud näites on mitu teed sõlmest A sõlme E.

Tee (A, E) = (AB, BE)
VÕI
Tee (A, E) = (AC, CD, DE)
VÕI
Tee (A, E) = (AD, DE)

6. Suunamata graaf : suunamata graaf on selline, mille servad ei määra konkreetset suunda. Servad on kahesuunalised.

Näide

Seega saab selles näites serva AC läbida nii A-st C-ni kui ka C-st A-ni. Sarnaselt kõigi servadega. Tee sõlmest B sõlme C on kas (BA, AC) või (BD, DC).

7. Suunatud graaf : Suunatud graaf on selline, kus servi saab liikuda ainult määratud suunas.

Näide

Seega on samas näites nüüd servad suunatud. Servaga saab liikuda ainult selle suunas. Praegu pole sõlmest B sõlme C ühtegi teed.

8. Kaalutud graaf : Kaalutud graaf on graaf, mille servad on seotud raskusega. Üldiselt on see serva läbimiseks kulu.

Näide

Seega on samas näites nüüd servadega seotud teatud kaal. Sõlme A ja sõlme E vahel on kaks võimalikku rada.
Tee 1 = (AB, BD, DE), kaal 1 = 3 + 2 + 5 = 10
2. rada = (AC, CD, DE), kaal 2 = 1 + 3 + 5 = 9
On selge, et eelistatakse rada 2, kui eesmärk on jõuda sõlme A sõlmest E minimaalsete kuludega.

Põhitoimingud graafikul

Siin on allpool mainitud graafiku põhitoimingud

1. Lisage / eemaldage Vertex

See on graafiku lihtsaim toiming. Lisate graafikule lihtsalt tipu. See ei pea olema serva kaudu ühendatud ühegi teise tipuga. Tippude eemaldamisel peate eemaldama kõik servad, mis pärinevad kustutatud tipust ja lõpevad sellega.

2. Lisage / eemaldage serv

See toiming lisab või eemaldab serva kahe tipu vahel. Kui kustutatakse kõik tipud, mis pärinevad tipust ja lõpevad tipuga, saab tipust eraldatud tipp.

3. Esimene laius (BFS)

See on graafikul läbitav toiming. BFS läbib graafiku horisontaalselt. See tähendab, et enne järgmisele tasemele liikumist läbib see kõik sõlmed ühel tasemel.
BFS-i algoritm algab graafiku esimese sõlme ülaosast ja läbib seejärel kõik külgnevad sõlmed. Kui kõik külgnevad sõlmed on läbitud, kordab algoritm sama protseduuri ka lapsesõlmede jaoks.

Näide

Ülaltoodud graafiku BFS-i järgi läbimisel tuleneb A -> B -> C -> D -> E -> F -> G. Algoritm algab sõlmest A ja läbib kõiki sellega külgnevaid sõlmi B, C ja D. See tähistab kõik neli sõlme külastatuna. Kui kõik A külgnevad sõlmed on läbitud, liigub algoritm punkti A esimesse külgnevasse sõlme ja kordab sama protseduuri. Sel juhul on sõlmeks B ja B-ga külgnevad sõlmed E ja F. Järgmisena läbitakse C-ga külgnevad sõlmed. Kui kõik sõlmed on külastatud, lõpeb operatsioon.

4. Esimene sügavusotsing (DFS)

Esimene sügavusotsing või DFS liigutab graafikut vertikaalselt. See algab juursõlme või graafi esimese sõlmega ja läbib kõik lapsesõlmed enne naabruses olevatesse sõlmedesse liikumist.

Näide

Ülaltoodud graafiku BFS-i järgi läbimisel tulenevad A -> B -> E -> F -> C -> G -> D. Algoritm algab sõlmest A ja läbib kõik selle alamsõlmed. Niipea kui ta kohtub B-ga, tundub, et sellel on veel lapsesõlmi. Niisiis, enne A järgmise lapsesõlme juurde minemist läbitakse B lapse lapsesõlmed.

Graafikute reaalajas rakendamine

  • Elektrienergia vooluahelate projekteerimine.
  • Ühendatud arvutite võrgu kujundamine.
  • Mis tahes aine, nt inimese DNA, molekulaarse, keemilise ja rakulise struktuuri uurimine.
  • Linnade ja linna siseste kohtade vaheliste transporditeede kujundamine.

Järeldus - graafik andmete struktuuris

Graafikud on andmestruktuurides väga kasulik mõiste. Sellel on praktilised rakendused peaaegu igas valdkonnas. On väga oluline mõista graafiteooria põhitõdesid, arendada arusaamist graafi struktuuri algoritmidest.
See artikkel oli lihtsalt sissejuhatus graafikutele. See on lihtsalt samm. Graafiteooria teema on soovitatav sügavamale sukelduda.

Soovitatavad artiklid

See on juhend andmestruktuuri graafikule. Siin käsitleme graafikute terminoloogiaid ja põhilisi toiminguid andmestruktuuris. Lisateabe saamiseks võite vaadata ka järgmist artiklit -

  1. Andmestruktuuri küsitluse küsimused
  2. Andmemudel Cassandras
  3. Mis on Data Mart?
  4. Mis on andmeteadlane?

Kategooria:

Suured andmed