Sadržaj

• Usporedni grafikon
• Definicija stabla
• Svojstva stabla:
• Definicija grafikona
• Svojstva grafikona:
• Zaključak

Stablo i graf spadaju u kategoriju nelinearne strukture podataka gdje stablo nudi vrlo koristan način predstavljanja odnosa čvorova u hijerarhijskoj strukturi, a graf slijedi mrežni model. Stablo i graf razlikuju se činjenicom da struktura stabla mora biti povezana i nikad ne može imati petlje, dok na grafu nema takvih ograničenja.

Nelinearna struktura podataka sastoji se od skupa elemenata koji su raspoređeni na ravnini, što znači da ne postoji takav niz između elemenata kao što postoji u linearnoj strukturi podataka.

1. 1. Usporedni grafikon
   2. definicija
   3. Ključne razlike
   4. Zaključak

Usporedni grafikon

Osnove za usporedbu	drvo	Grafikon
Staza	Samo jedna između dvije vrhove.	Dopušteno je više od jedne staze.
Korijenski čvor	Ima točno jedan korijenski čvor.	Grafikon nema korijenski čvor.
petlje	Nije dopuštena petlja.	Grafikon može imati petlje.
Složenost	Manje složen	Složenije komparativno
Tehnike prelaska	Predbilježba, narudžba i narudžba.	Prvo pretraživanje širine i prvo pretraživanje dubine.
Broj rubova	n-1 (gdje je n broj čvorova)	Nije definirano
Vrsta modela	hijerarhijski	Mreža

Definicija stabla

drvo je konačna zbirka podataka koja se obično naziva čvorovi. Kao što je gore spomenuto, stablo je nelinearna struktura podataka koja uređuje podatke s podacima sortiranim redoslijedom. Koristi se za prikazivanje hijerarhijske strukture između različitih elemenata podataka i organizira podatke u grane koje odnose podatke. Dodavanje novog ruba stablu rezultira formiranjem petlje ili kruga.

Postoji nekoliko vrsta stabala kao što su binarno stablo, binarno stablo pretraživanja, AVL stablo, binarno stablo s navojem, B stablo itd. Kompresija podataka, pohrana datoteka, manipulacija aritmetičkim izrazom i stabla igara neke su od primjena stabla struktura podataka.

Svojstva stabla:

• Na vrhu stabla je određen čvor poznat kao korijen stabla.
• Preostale stavke podataka podijeljene su u odvojene podskupove koji se nazivaju poddreva.
• Stablo se u visini širi prema dnu.
• Drvo mora biti povezano što znači da mora postojati put od jednog korijena do svih ostalih čvorova.
• Ne sadrži nikakve petlje.
• Stablo ima rubove n-1.

Postoje različiti izrazi povezani s drvećem, kao što su terminalni čvor, rub, razina, stupanj, dubina, šuma itd. Među tim su terminima neki od njih opisani u nastavku.

• Rub - Linija koja povezuje dva čvora.
• nivo - Stablo je podijeljeno na razine tako da korijenski čvor bude na razini 0. Zatim su njegova neposredna djeca na razini 1, a njegova neposredna djeca na razini 2 i tako dalje, do krajnjeg ili čvorova lista.
• Stupanj - To je broj podvrsta čvora na određenom stablu.
• Dubina - To je maksimalna razina bilo kojeg čvora na određenom stablu i također poznata kao visina.
• Terminalni čvor - Čvor najviše razine je terminalni čvor, dok su ostali čvorovi osim terminalnog i korijenskog čvora poznati kao ne-terminalni čvorovi.

Definicija grafikona

grafikon je također matematička nelinearna struktura podataka koja može predstavljati različite vrste fizičke strukture. Sastoji se od grupe vertikala (ili čvorova) i skupa rubova koji povezuju dva vrha. Vrhovi na grafu predstavljeni su kao točka ili krugovi, a rubovi su prikazani kao lukovi ili segmenti linija. Rub je predstavljen s E (v, w), gdje su v i w parovi vrhova. Uklanjanje ruba iz kruga ili povezanog grafa stvara podgraf koji je stablo.

Grafovi su svrstani u različite kategorije kao što su usmjereni, ne usmjereni, povezani, nepovezani, jednostavni i više-grafni. Računalna mreža, prometni sustav, graf društvenih mreža, električni krugovi i projektiranje neke su od primjena strukture podataka grafikona. Također se koristi u tehnici upravljanja nazvanoj kao OTRESIT (tehnika ocjenjivanja i ocjenjivanja programa) i CPM (metoda kritičnog puta) u kojoj se analizira struktura grafa.

Svojstva grafikona:

• Vrhovi u grafikonu mogu se povezati s bilo kojim brojem drugih vrhova pomoću rubova.
• Rub može biti dvosmjerni ili usmjeren.
• Rub se može vagati.

U grafikonu također koristimo različite izraze kao što su susjedni vrhovi, putanja, ciklus, stupanj, povezani graf, cjeloviti graf, ponderirani graf itd. Razumijemo neke od tih pojmova.

• Susjedni vrhovi - Vrhova a je uz vrh b ako postoji rub (a, b) ili (b, a).
• Staza - Put iz slučajne vrhove w susjedni je niz vrhova.
• Ciklus - To je put na kojem su prvi i zadnji vrhovi isti.
• Stupanj - To je veći broj rubova koji se događaju na jednoj vrhovi.
• Graf koji je povezan - Ako postoji put od slučajne vrhove do bilo koje druge vertexa, tada je taj graf poznat kao povezan grafikon.

1. U stablu postoji samo jedan put između svaka dva vrha, dok graf može imati jednosmjerne i dvosmjerne putove između čvorova.
2. U stablu postoji točno jedan korijenski čvor i svako dijete može imati samo jednog roditelja. Nasuprot tome, u grafikonu ne postoji koncept korijenskog čvora.
3. Stablo ne može imati petlje i samoobrat, dok graf može imati petlje i samoputajuće petlje.
4. Grafikoni su složeniji jer mogu imati petlje i samorezne petlje. Nasuprot tome, stabla su jednostavna u odnosu na graf.
5. Stablo se prelazi pomoću tehnika predbilježbe, narudžbe i narudžbe. S druge strane, za preslikavanje grafikona koristimo BFS (Prva širina širine) i DFS (Dubina prva pretraga).
6. Stablo može imati n-1 rubove. Naprotiv, u grafikonu nema unaprijed definirani broj rubova, a ovisi o grafu.
7. Drvo ima hijerarhijsku strukturu dok graf ima mrežni model.

Zaključak

Graf i stablo su nelinearna struktura podataka koja se koristi za rješavanje različitih složenih problema. Graf je skupina vrhova i rubova gdje rub povezuje par vertikala, dok se stablo smatra minimalno povezanim grafom koji mora biti povezan i bez petlji.