Conţinut

• Diagramă de comparație
• Definiția Tree
• Proprietățile arborelui:
• Definiția Graph
• Proprietățile unui grafic:
• Concluzie

Arborele și graficul se încadrează în categoria structurilor de date neliniare, în care arborele oferă un mod foarte util de a reprezenta o relație între nodurile dintr-o structură ierarhică și graficul urmează un model de rețea. Arborele și graficul sunt diferențiate prin faptul că structura unui arbore trebuie conectată și nu poate avea niciodată bucle, în timp ce în grafic nu există astfel de restricții.

O structură neliniară de date constă dintr-o colecție de elemente care sunt distribuite pe un plan ceea ce înseamnă că nu există o astfel de secvență între elemente, deoarece există într-o structură liniară de date.

1. 1. Diagramă de comparație
   2. Definiție
   3. Diferențele cheie
   4. Concluzie

Diagramă de comparație

Baza de comparație	Copac	Grafic
cale	Doar unul între două vârfuri.	Sunt permise mai multe căi.
Nodul rădăcină	Are exact un nod rădăcină.	Graficul nu are un nod rădăcină.
buclele	Nu sunt permise bucle.	Graficul poate avea bucle.
Complexitate	Mai puțin complex	Mai complex comparativ
Tehnici de traversare	Pre-comandă, comandă și post-comandă.	Primă căutare a lărgimii și căutare în profunzime.
Numărul de muchii	n-1 (unde n este numărul de noduri)	Nedefinit
Tip model	Ierarhic	Reţea

Definiția Tree

A copac este o colecție finită de elemente de date denumite de obicei noduri. După cum este menționat mai sus, un arbore este o structură de date neliniară care aranjează elementele de date în ordine ordonată. Este utilizat pentru a arăta o structură ierarhică între diferitele elemente de date și organizează datele în ramuri care se referă la informații. Adăugarea unei noi muchii într-un arbore duce la formarea buclei sau a circuitului.

Există mai multe tipuri de arbori, cum ar fi un arbore binar, arbore de căutare binară, arbore AVL, arbore binar filetat, arbore B, etc. Compresia datelor, stocarea fișierelor, manipularea expresiei aritmetice și arborii de joc sunt câteva dintre aplicarea arborelui structură de date.

Proprietățile arborelui:

• Există un nod desemnat în vârful arborelui cunoscut sub numele de rădăcină.
• Restul de articole de date sunt împărțite în subseturi disjuncte se referă la subtree.
• Arborele este extins în înălțime spre partea de jos.
• Un arbore trebuie conectat ceea ce înseamnă că trebuie să existe o cale de la o rădăcină la toate celelalte noduri.
• Nu conține bucle.
• Un copac are n-1 margini.

Există diverși termeni asociați cu arbori, cum ar fi nodul terminal, marginea, nivelul, gradul, adâncimea, pădurea etc. Printre acești termeni, unii dintre ei descriși mai jos.

• Margine - O linie care conectează două noduri.
• Nivel - Un arbore este împărțit în niveluri astfel încât nodul rădăcină să fie la nivelul 0. Apoi, copiii săi imediați sunt la nivelul 1, iar copiii săi imediați sunt la nivelul 2 și așa mai departe până la nodul terminal sau frunz.
• grad - Este numărul de subtrape ale unui nod dintr-un arbore dat.
• Adâncime - Este nivelul maxim al oricărui nod dintr-un arbore dat și cunoscut și sub denumirea de înălţime.
• Nodul terminal - Cel mai înalt nivel este nodul terminal, în timp ce alte noduri, cu excepția terminalului și nodului rădăcină, sunt cunoscute sub numele de noduri non-terminale.

Definiția Graph

A grafic este de asemenea o structură matematică neliniară de date care poate reprezenta diverse tipuri de structură fizică. Se compune dintr-un grup de vârfuri (sau noduri) și un set de muchii care leagă cele două vârfuri. Vertexurile din grafic sunt reprezentate ca puncte sau cercuri și marginile sunt arătate ca arcuri sau segmente de linie. O margine este reprezentată de E (v, w), unde v și w sunt perechile de vârfuri. Îndepărtarea unei margini dintr-un circuit sau grafic conectat creează un subgraf care este un arbore.

Graficele sunt clasificate în diferite categorii, cum ar fi direcționat, nerecomandat, conectat, neconectat, simplu și multi-grafic. Rețeaua de calculatoare, sistemul de transport, graficul rețelei sociale, circuitele electrice și planificarea proiectelor sunt câteva dintre aplicațiile structurii datelor grafice. Este, de asemenea, utilizat în tehnica de management numită ca PERT (tehnica de evaluare și revizuire a programului) și CPM (metoda căii critice) în care este analizată structura graficului.

Proprietățile unui grafic:

• Un vertex dintr-un grafic poate fi conectat la orice număr de alte vârfuri folosind muchii.
• O margine poate fi direcționată sau direcționată.
• O margine poate fi cântărită.

În grafic, de asemenea, utilizăm diferiți termeni precum vertexuri adiacente, traseu, ciclu, grad, grafic conectat, grafic complet, grafic ponderat, etc. Să înțelegem unii dintre acești termeni.

• Vârfurile adiacente - Un vertex a este adiacent vertexului b dacă există o margine (a, b) sau (b, a).
• cale - O cale dintr-un vertex aleatoriu w este o secvență adiacentă de vârfuri.
• Ciclu - Este o cale în care primul și ultimul vârf sunt identici.
• grad - Este un număr de margini incident pe un vertex.
• Grafic conectat - Dacă există o cale de la un vertex aleatoriu la oricare alt vertex, atunci acel grafic este cunoscut sub numele de grafic conectat.

1. Într-un arbore există o singură cale între oricare două vârfuri, în timp ce un grafic poate avea căi unidirecționale și bidirecționale între noduri.
2. În copac, există exact un nod rădăcină și fiecare copil poate avea un singur părinte. Spre deosebire, într-un grafic, nu există niciun concept al nodului rădăcină.
3. Un arbore nu poate avea bucle și auto-bucle în timp ce graficul poate avea bucle și auto-bucle.
4. Graficele sunt mai complicate, deoarece pot avea bucle și auto-bucle. În schimb, copacii sunt simpli în comparație cu graficul.
5. Arborele este traversat folosind tehnici de pre-comandă, ordine și post-comandă. Pe de altă parte, pentru traversarea graficului, folosim BFS (Breadth First Search) și DFS (Depth First Search).
6. Un copac poate avea n-1 margini. Dimpotrivă, în grafic, nu există un număr predefinit de muchii și depinde de grafic.
7. Un arbore are o structură ierarhică, în timp ce graficul are un model de rețea.

Concluzie

Graficul și arborele sunt structura de date neliniară care este utilizată pentru a rezolva diverse probleme complexe. Un grafic este un grup de vârfuri și margini în care o margine conectează o pereche de vârfuri, în timp ce un arbore este considerat un grafic minim conectat, care trebuie conectat și liber de bucle.