Sisu

• Võrdlusdiagramm
• Puu määratlus
• Puu omadused:
• Graafiku määratlus
• Graafiku omadused:
• Järeldus

Puu ja graaf kuuluvad mittelineaarse andmestruktuuri kategooriasse, kus puu pakub väga kasulikku viisi sõlmede vahelise suhte esindamiseks hierarhilises struktuuris ja graaf järgib võrgumudelit. Puu ja graafi eristab asjaolu, et puu struktuur peab olema ühendatud ja sellel ei tohi kunagi olla silmuseid, samas kui graafikul sellised piirangud puuduvad.

Mittelineaarne andmestruktuur koosneb tasapinnaliselt levivate elementide kogumist, mis tähendab, et elementide vahel pole sellist järjestust, nagu lineaarses andmestruktuuris eksisteerib.

1. 1. Võrdlusdiagramm
   2. Definitsioon
   3. Peamised erinevused
   4. Järeldus

Võrdlusdiagramm

Võrdluse alus	Puu	Graafik
Tee	Ainult üks kahe tipu vahel.	Lubatud on rohkem kui üks tee.
Juursõlm	Sellel on täpselt üks juursõlm.	Graafikul pole juursõlme.
Silmused	Silmused pole lubatud.	Graafikul võib olla silmuseid.
Keerukus	Vähem keeruline	Võrdlemisi keerulisem
Läbilõikamise tehnikad	Ettetellimisel, tellimisel ja järeltellimisel.	Laiuse esimene otsing ja sügavuse esimene otsing.
Servade arv	n-1 (kus n on sõlmede arv)	Ei ole defineeritud
Mudeli tüüp	Hierarhiline	Võrgustik

Puu määratlus

A puu on andmekogude piiratud kogum, mida tavaliselt nimetatakse sõlmedeks. Nagu eespool mainitud, on puu mittelineaarne andmestruktuur, mis korraldab andmeühikud järjestatud järjekorras. Seda kasutatakse hierarhilise struktuuri kuvamiseks erinevate andmeelementide vahel ja andmete järjestamiseks hargnemiseks. Uue serva lisamisega puusse tekib silmus või vooluring.

Puid on mitut tüüpi, näiteks binaarne puu, binaarne otsingupuu, AVL-puu, keermestatud binaarne puu, B-puu jne. Puu rakenduste hulka kuuluvad andmete pakkimine, failide salvestamine, aritmeetilise avaldisega manipuleerimine ja mängupuud. andmestruktuur.

Puu omadused:

• Puu ülaosas on määratud sõlme, mida tuntakse puu juurena.
• Ülejäänud andmeüksused jagunevad eraldatud alamkomplektideks, mida nimetatakse alampuudeks.
• Puu on laiuse poole laiendatud.
• Puu peab olema ühendatud, mis tähendab, et ühest juurest kõigi teiste sõlmedeni peab olema tee.
• See ei sisalda ühtegi silmust.
• Puul on n-1 serva.

Puudega on seotud mitmesuguseid termineid, näiteks lõppsõlm, serv, tase, aste, sügavus, mets jne. Nende mõistete hulgas on mõned neist allpool kirjeldatud.

• Serv - kahte sõlme ühendav joon.
• Tase - Puu jaotatakse tasanditeks nii, et juursõlm on tasemel 0. Siis on tema vahetud lapsed tasemel 1 ja tema otsesed lapsed tasemel 2 ja nii edasi kuni terminali- või lehesõlme.
• Kraad - see on sõlme alamtrasside arv antud puus.
• Sügavus - see on antud puu mis tahes sõlme maksimaalne tase ja seda nimetatakse ka kõrgus.
• Terminalisõlm - Kõrgeima taseme sõlm on terminalisõlm, teised sõlmed, välja arvatud terminali- ja juursõlm, on tuntud kui mitte-terminaalsõlmed.

Graafiku määratlus

A graafik on ka matemaatiline mittelineaarne andmestruktuur, mis võib tähistada mitmesuguseid füüsikalisi struktuure. See koosneb tippudest (või sõlmedest) ja servadest, mis ühendavad kahte tippu. Graafiku tipud on näidatud punkti või ringidena ja servad on esitatud kaarate või sirgsegmentidena. Serva tähistab E (v, w), kus v ja w on tippude paarid. Serva eemaldamine vooluringilt või ühendatud graafikult loob alamgraafi, mis on puu.

Graafikud liigitatakse erinevatesse kategooriatesse nagu suunatud, suunamata, ühendatud, ühendamata, lihtsad ja mitmegraafilised. Graafi andmestruktuuri mõned rakendused on arvutivõrk, transpordisüsteem, sotsiaalvõrgustiku graafik, elektriskeemid ja projekti kavandamine. Seda kasutatakse ka juhtimistehnikas, mida nimetatakse PERT (programmi hindamise ja ülevaatuse tehnika) ja CPM (kriitilise tee meetod), milles analüüsitakse graafi struktuuri.

Graafiku omadused:

• Graafiku tipu saab servade abil ühendada suvalise arvu teiste tippudega.
• Serva saab suunata või suunata.
• Serva saab kaaluda.

Samuti kasutame graafikul mitmesuguseid termineid nagu külgnevad tipud, tee, tsükkel, aste, ühendatud graaf, täielik graaf, kaalutud graaf jne. Mõistagem mõnda neist mõistetest.

• Külgnevad tipud - Tipp a külgneb tipuga b, kui on serv (a, b) või (b, a).
• Tee - Tee juhuslikust tipust w on külgnev tippude jada.
• Tsükkel - See on tee, kus esimene ja viimane tipp on samad.
• Kraad - see on arv tippe langevaid servi.
• Ühendatud graafik - Kui eksisteerib tee juhuslikust tipust teise tippu, siis nimetatakse seda graafi ühendatud graafiks.

1. Puus eksisteerib kahe tipu vahel ainult üks tee, graafikul aga võivad olla ühesuunalised ja kahesuunalised teed sõlmede vahel.
2. Puus on täpselt üks juursõlm ja igal lapsel võib olla ainult üks vanem. Vastupidi, graafikul puudub juursõlme kontseptsioon.
3. Puul ei saa olla silmuseid ega autosilmuseid, samas kui graafil võivad olla silmuseid ja autosilmuseid.
4. Graafikud on keerukamad, kuna sellel võib olla silmuseid ja autosilmuseid. Seevastu puud on graafikuga võrreldes lihtsad.
5. Puust juhitakse ettetellimisel, tellimisel ja järeltellimisel. Teisest küljest kasutame graafiku läbimiseks BFS-i (esimese laiuse otsing) ja DFS-i (esimese sügavuse otsing).
6. Puul võib olla n-1 serva. Vastupidi, graafikul pole etteantud servade arvu ja see sõltub graafikust.
7. Puul on hierarhiline struktuur, graafil aga võrgumudel.

Järeldus

Graafik ja puu on mittelineaarne andmestruktuur, mida kasutatakse mitmesuguste keerukate probleemide lahendamiseks. Graafik on tippude ja servade rühm, kus serv ühendab tipude paari, samas kui puu peetakse minimaalselt ühendatud graafiks, mis peab olema ühendatud ja ilma silmusteta.