Uvod v graf v strukturi podatkov
Grafi so nelinearne podatkovne strukture, ki vsebujejo končni nabor vozlišč in robov. Vozlišča so elementi in robovi so urejeni pari povezav med vozlišči.
Opazite besedo nelinearno. Nelinearna struktura podatkov je tista, pri kateri elementi niso razporejeni v zaporednem zaporedju. Na primer, matrika je linearna podatkovna struktura, ker so elementi razporejeni drug za drugim. V enem samem teku lahko prečkate vse elemente matrike. Tako pri nelinearnih strukturah podatkov ne gre. Elementi nelinearne podatkovne strukture so razporejeni v več ravneh, pogosto po hierarhičnem vzorcu. Grafi so nelinearni.
Naslednja beseda, na katero bodite pozorni, je končna. Graf definiramo tako, da ima končno in števno število vozlišč. To je precej neskladen izraz. Graf ima v bistvu neskončno število vozlišč in je še vedno končen. Na primer, družinsko drevo, ki sega vse do Adama in Eve. To je razmeroma neskončen graf, vendar je še vedno štet in se zato šteje za končno.
Primer iz resničnega sveta
Najboljši primer grafov v resničnem svetu je Facebook. Vsaka oseba na Facebooku je vozlišče in je povezana preko robov. A je prijatelj B. B je prijatelj C in tako naprej.
Terminologije
Spodaj so omenjene terminologije grafov v strukturi podatkov
1. Prikaz grafike: Graf je ponavadi predstavljen kot par nizov (V, E). V je niz tock ali vozlišč. E je niz Robov. V zgornjem primeru je dr.
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Vozlišče ali Vertex: Elementi grafa so povezani skozi robove.
3. Robovi: pot ali črta med dvema točkama v grafu.
4. Sosednja vozlišča: Če se povezujeta skozi rob, se dve vozlišči imenujeta sosednji. V zgornjem primeru vozlišče A meji na vozlišča B, C in D, ne pa na vozlišče E.
5. Pot: Pot je zaporedje robov med dvema vozliščema. Gre v bistvu za prečkanje, ki se začne pri enem vozlišču in konča pri drugem. V zgornjem primeru je več poti od vozlišča A do vozlišča E.
Pot (A, E) = (AB, BE)
ALI
Pot (A, E) = (AC, CD, DE)
ALI
Pot (A, E) = (AD, DE)
6. Neizmerni graf: Neusmerjen graf je tisti, kjer robovi ne določajo določene smeri. Robovi so dvosmerni.
Primer
Tako je v tem primeru mogoče premikati rob AC od A do C in C do A. Podobno kot vsi robovi. Pot od vozlišča B do vozlišča C bi bila (BA, AC) ali (BD, DC).
7. Usmerjeni graf: usmerjeni graf je tisti, kjer se robovi lahko premikajo samo v določeni smeri.
Primer
Tako so v istem primeru zdaj robovi usmerjeni. Robo lahko prečkate le vzdolž njegove smeri. Zdaj ni poti od vozlišča B do vozlišča C.
8. Uteženi grafikon: tehtan graf je tisti, kjer so robovi povezani z utežjo. To so na splošno stroški prečka roba.
Primer
Tako imajo v istem primeru z robovi določeno težo, povezano z njimi. Med vozliščem A do vozlišča E. sta možni dve poti.
Pot1 = (AB, BD, DE), teža1 = 3 + 2 + 5 = 10
Pot2 = (AC, CD, DE), teža2 = 1 + 3 + 5 = 9
Jasno bi bilo, da bi raje Path2, če je cilj doseči vozlišče E iz vozlišča A z minimalnimi stroški.
Osnovne operacije na grafu
Spodaj so navedene osnovne operacije grafa
1. Dodaj / odstrani vertex
To je najpreprostejša operacija v grafu. V graf preprosto dodate točko. Ni treba, da se prek roba poveže z drugimi vrhovi. Ko odstranite točko, morate odstraniti vse robove, ki izvirajo in se končajo na izbrisani točki.
2. Dodaj / odstrani rob
Ta operacija doda ali odstrani rob med dvema vozliščema. Ko se vsi robovi, ki izvirajo iz in se končajo na točki, izbrišejo, postane točko izolirano točko.
3. Prva širina iskanja (BFS)
To je prečna operacija v grafu. BFS vodoravno prečka graf. To pomeni, da prečka vsa vozlišča na isti ravni, preden nadaljuje na naslednjo raven.
Algoritem BFS se začne na vrhu prvega vozlišča v grafu in nato prečka vsa sosednja vozlišča do njega. Ko se prečkajo vsa sosednja vozlišča, algoritem ponovi enak postopek za nadrejena vozlišča.
Primer
Prehod zgornjega grafa na način BFS bi bil posledica A -> B -> C -> D -> E -> F -> G. Algoritem se začne od vozlišča A in prečka vsa njegova sosednja vozlišča B, C in D. vsa štiri obiskana vozlišča. Ko se prečkajo vsa sosednja vozlišča A, se algoritem premakne na prvo sosednje vozlišče A in ponovi isti postopek. V tem primeru je vozlišče B, sosednja vozlišča na B pa E in F. Nato se sosednja vozlišča na C prečkajo. Ko so vsa vozlišča obiskana, se operacija konča.
4. Globinsko prvo iskanje (DFS)
Globina Prvo iskanje ali DFS prečka graf navpično. Začne se s korenskim vozliščem ali prvim vozliščem grafa in prečka vsa podrejena vozlišča, preden se premakne na sosednja vozlišča.
Primer
Prehod zgornjega grafa na način BFS bi bil posledica A -> B -> E -> F -> C -> G -> D. Algoritem se začne od vozlišča A in prečka vsa njegova podrejena vozlišča. Takoj, ko naleti na B, se zdi, da ima nadaljnja otroška vozlišča. Otroška vozlišča B se torej premikajo, preden nadaljujejo do naslednjega otroškega vozlišča A.
Izvedbe grafov v resničnem svetu
- Zasnova električnih vezij za prenos energije.
- Oblikovanje omrežja medsebojno povezanih računalnikov.
- Preučevanje molekularne, kemične in celične strukture katere koli snovi, na primer človeške DNK.
- Oblikovanje prometnih poti med mesti in kraji znotraj mesta.
Zaključek - Graf v podatkovni strukturi
Grafi so zelo uporaben koncept v strukturah podatkov. Ima praktične izvedbe na skoraj vseh področjih. Zelo pomembno je razumeti osnove teorije grafov, razviti razumevanje algoritmov graf strukture.
Ta članek je bil zgolj uvod v grafe. Je le odskočna deska. Priporočljivo je, da se še dodatno potopite v temo teorije grafov.
Priporočeni članki
To je vodnik po grafu v strukturi podatkov. Tukaj razpravljamo o terminologijah in osnovnih operacijah grafa v podatkovni strukturi. Če želite izvedeti več, si oglejte tudi naslednji članek -
- Vprašanja o intervjuju s strukturo podatkov
- Podatkovni model v Cassandri
- Kaj je Data Mart?
- Kaj je podatkovni znanstvenik?