Razlika med drevesom in grafom
Vsebina
Drevo in graf spadata v kategorijo nelinearne podatkovne strukture, kjer drevo ponuja zelo uporaben način predstavljanja razmerja med vozlišči v hierarhični strukturi, graf pa sledi mrežnemu modelu. Drevo in graf razlikujeta po tem, da mora biti drevesna struktura povezana in nikoli ne sme imeti zank, medtem ko v grafu ni takšnih omejitev.
Nelinearna struktura podatkov je sestavljena iz zbirke elementov, ki so razporejeni na ravnini, kar pomeni, da med elementi ni takšnega zaporedja, kot je v linearni strukturi podatkov.
-
- Primerjalna tabela
- Opredelitev
- Ključne razlike
- Zaključek
Primerjalna tabela
| Osnove za primerjavo | Drevo | Graf |
|---|---|---|
| Pot | Samo ena med dvema vozliščima. | Dovoljena je več kot ena pot. |
| Koreninsko vozlišče | Ima točno eno koreninsko vozlišče. | Graf nima korenskega vozlišča. |
| Zanke | Nobene zanke niso dovoljene. | Graf ima lahko zanke. |
| Kompleksnost | Manj zapletena | Kompleksneje zapleteno |
| Prehodne tehnike | Prednaročilo, po naročilu in naročilo. | Iskanje po širini in prvo globino. |
| Število robov | n-1 (kjer je n število vozlišč) | Ni določeno |
| Vrsta modela | Hierarhična | Omrežje |
Opredelitev drevesa
A drevo je končna zbirka podatkovnih elementov, ki jih običajno imenujemo vozlišča. Kot je že omenjeno, je drevo nelinearna podatkovna struktura, ki ureja podatkovne predmete v razvrščenem vrstnem redu. Uporablja se za prikaz hierarhične strukture med različnimi podatkovnimi elementi in podatke organizira v veje, ki podatke povezujejo. Dodajanje novega roba v drevesu povzroči nastanek zanke ali vezja.
Obstaja več vrst dreves, kot so binarno drevo, binarno drevo za iskanje, drevo AVL, binarno drevo z navojem, B drevo itd. Stiskanje podatkov, shranjevanje datotek, manipulacija aritmetičnega izraza in drevesa igre so nekatere od aplikacij drevesa struktura podatkov.
Lastnosti drevesa:
- Na vrhu drevesa je označeno vozlišče, imenovano koren drevesa.
- Preostale podatkovne postavke so razdeljene na ločene podskupine, ki se nanašajo na poddrevo.
- Drevo se razširi v višino proti dnu.
- Drevo mora biti povezano, kar pomeni, da mora biti pot od enega korena do vseh drugih vozlišč.
- Ne vsebuje zank.
- Drevo ima robove n-1.
Obstajajo različni izrazi, povezani z drevesi, kot so terminalno vozlišče, rob, raven, stopnja, globina, gozd itd. Med temi izrazi so nekateri spodaj opisani.
- Roba - Vrstica, ki povezuje dve vozlišči.
- Raven - Drevo je razdeljeno na ravni tako, da je koreninsko vozlišče na ravni 0. Potem so njegovi neposredni otroci na ravni 1, njegovi neposredni otroci pa na ravni 2 in tako naprej do terminala ali listnega vozlišča.
- Stopnja - To je število podrezij vozlišča v danem drevesu.
- Globina - To je najvišja raven katerega koli vozlišča na določenem drevesu in znana tudi kot višina.
- Terminalno vozlišče - vozlišče najvišje stopnje je terminalno vozlišče, medtem ko so druga vozlišča razen terminalnega in korenskega vozlišča znana kot ne-terminalna vozlišča.
Opredelitev grafa
A graf je tudi matematična nelinearna struktura podatkov, ki lahko predstavlja različne vrste fizične strukture. Sestavljen je iz skupine tock (ali vozlišč) in niza robov, ki povezujejo obe točki. Vrhovi na grafu so predstavljeni kot točka ali krogi, robovi pa so prikazani kot loki ali odseki črt. Rob je predstavljen z E (v, w), kjer sta v in w pari tock. Če odstranite rob iz vezja ali povezanega grafa, ustvarite podstavek, ki je drevo.
Grafi so razvrščeni v različne kategorije, kot so usmerjeni, ne usmerjeni, povezani, nepovezani, preprosti in več-graf. Računalniško omrežje, prometni sistem, graf družbenih omrežij, električni tokokrogi in načrtovanje projektov so nekatere od aplikacij strukture podatkov grafov. Zaposlen je tudi v tehniki upravljanja z imenom as PERT (tehnika ocenjevanja in pregleda programa) in CPM (metoda kritične poti), v kateri se analizira struktura grafa.
Lastnosti grafa:
- Točka v grafu se lahko z robovi poveže s poljubnim številom drugih tock.
- Roba je lahko dvosmerna ali usmerjena.
- Rob je lahko obtežen.
V grafu uporabljamo tudi različne izraze, kot so sosednja točki, pot, cikel, stopnja, povezan graf, celoten graf, tehtan graf itd. Razumejmo nekatere od teh izrazov.
- Sosednja točka - Vrh a je poleg vrha b, če je rob (a, b) ali (b, a).
- Pot - Pot iz naključnega vrha w je sosednje zaporedje tock.
- Cikel - To je pot, kjer sta prva in zadnja točka enaka.
- Stopnja - Gre za številne robove, ki se pojavljajo na točki.
- Povezani graf - Če obstaja pot od naključnega toka do katerega koli drugega toka, potem je ta graf znan kot povezan graf.
- V drevesu obstaja samo ena pot med dvema vozliščema, medtem ko ima graf lahko enosmerne in dvosmerne poti med vozlišči.
- V drevesu je točno eno koreninsko vozlišče in vsak otrok ima lahko le enega starša. Nasprotno pa v grafu ni koncepta korenskega vozlišča.
- Drevo ne more imeti zank in samodejnih zank, medtem ko ima lahko graf zanke in samodejne zanke.
- Grafi so bolj zapleteni, saj lahko imajo zanke in samodejne zanke. V nasprotju s tem so drevesa v primerjavi z grafom preprosta.
- Drevo se premika po tehnikah prednaročila, po naročilu in po naročilu. Po drugi strani pa za prečkanje grafov uporabljamo BFS (prvo iskanje širine) in DFS (globinsko prvo iskanje).
- Drevo ima lahko robove n-1. Nasprotno, v grafu ni vnaprej določeno število robov in je odvisno od grafa.
- Drevo ima hierarhično strukturo, medtem ko ima graf mrežni model.
Zaključek
Graf in drevo sta nelinearna struktura podatkov, ki se uporablja za reševanje različnih zapletenih problemov. Graf je skupina tock in robov, kjer rob povezuje par tock, medtem ko drevo velja za minimalno povezan graf, ki mora biti povezan in brez zank.
