Contenuto

• Tabella di comparazione
• Definizione di albero
• Proprietà dell'albero:
• Definizione di grafico
• Proprietà di un grafico:
• Conclusione

Albero e grafico rientrano nella categoria della struttura di dati non lineare in cui l'albero offre un modo molto utile di rappresentare una relazione tra i nodi in una struttura gerarchica e il grafico segue un modello di rete. Albero e grafico si differenziano per il fatto che una struttura ad albero deve essere connessa e non può mai avere anelli mentre nel grafico non vi sono tali restrizioni.

Una struttura di dati non lineare è costituita da una raccolta di elementi distribuiti su un piano, il che significa che non esiste una sequenza tra gli elementi esistente in una struttura di dati lineare.

1. 1. Tabella di comparazione
   2. Definizione
   3. Differenze chiave
   4. Conclusione

Tabella di comparazione

Base per il confronto	Albero	Grafico
Sentiero	Solo uno tra due vertici.	È consentito più di un percorso.
Nodo radice	Ha esattamente un nodo radice.	Il grafico non ha un nodo principale.
Loops	Non sono ammessi loop.	Il grafico può avere loop.
Complessità	Meno complesso	Più complesso relativamente
Tecniche trasversali	Pre-ordine, In-order e Post-order.	Ricerca in ampiezza e ricerca in profondità.
Numero di spigoli	n-1 (dove n è il numero di nodi)	Non definito
Tipo di modello	Hierarchical	Rete

Definizione di albero

UN albero è una raccolta finita di elementi di dati generalmente definiti come nodi. Come accennato in precedenza, un albero è una struttura di dati non lineare che dispone gli elementi di dati in ordine ordinato. Viene utilizzato per mostrare una struttura gerarchica tra i vari elementi di dati e organizza i dati in rami che mettono in relazione le informazioni. L'aggiunta di un nuovo bordo in un albero provoca una formazione del circuito o circuito.

Esistono diversi tipi di alberi come un albero binario, un albero di ricerca binario, un albero AVL, un albero binario filettato, un albero a B, ecc. La compressione dei dati, la memorizzazione dei file, la manipolazione dell'espressione aritmetica e gli alberi di gioco sono alcune delle applicazioni dell'albero struttura dati.

Proprietà dell'albero:

• C'è un nodo designato nella parte superiore dell'albero noto come radice dell'albero.
• Gli elementi di dati rimanenti sono divisi in sottoinsiemi disgiunti indicati come sottostruttura.
• L'albero si espande in altezza verso il fondo.
• Un albero deve essere collegato, il che significa che deve esserci un percorso da una radice a tutti gli altri nodi.
• Non contiene alcun loop.
• Un albero ha bordi n-1.

Ci sono vari termini associati ad alberi come nodo terminale, bordo, livello, grado, profondità, foresta, ecc. Tra questi termini, alcuni di essi descritti di seguito.

• Bordo - Una linea che collega due nodi.
• Livello - Un albero è suddiviso in livelli in modo tale che il nodo radice sia al livello 0. Quindi, i suoi figli immediati sono al livello 1, e i suoi figli immediati sono al livello 2 e così via fino al nodo terminale o foglia.
• Grado - È il numero di sottostrutture di un nodo in un determinato albero.
• Profondità - È il livello massimo di qualsiasi nodo in un determinato albero e noto anche come altezza.
• Nodo terminale - Il nodo di livello più alto è il nodo terminale mentre altri nodi tranne il nodo terminale e il nodo principale sono noti come nodi non terminali.

Definizione di grafico

UN grafico è anche una struttura matematica di dati non lineari che può rappresentare vari tipi di struttura fisica. È costituito da un gruppo di vertici (o nodi) e da una serie di bordi che collegano i due vertici. I vertici sul grafico sono rappresentati come punti o cerchi e i bordi sono mostrati come archi o segmenti di linea. Un bordo è rappresentato da E (v, w) dove v e w sono le coppie di vertici. La rimozione di un bordo da un circuito o da un grafico collegato crea un sottografo che è un albero.

I grafici sono classificati in varie categorie come diretto, non diretto, connesso, non connesso, semplice e multi-grafico. Rete di computer, sistema di trasporto, grafico dei social network, circuiti elettrici e pianificazione del progetto sono alcune delle applicazioni della struttura dei dati del grafico. È anche impiegato nella tecnica di gestione denominata come PERT (valutazione del programma e tecnica di revisione) e CPM (metodo del percorso critico) in cui viene analizzata la struttura del grafico.

Proprietà di un grafico:

• Un vertice in un grafico può essere collegato a qualsiasi numero di altri vertici usando i bordi.
• Un bordo può essere bidiretto o diretto.
• Un bordo può essere ponderato.

Nel grafico utilizziamo anche vari termini come vertici adiacenti, percorso, ciclo, grado, grafico collegato, grafico completo, grafico ponderato, ecc. Comprendiamo alcuni di questi termini.

• Vertici adiacenti - Un vertice a è adiacente al vertice b se è presente un bordo (a, b) o (b, a).
• Sentiero - Un percorso da un vertice casuale w è una sequenza adiacente di vertici.
• Ciclo - È un percorso in cui il primo e l'ultimo vertice sono uguali.
• Grado - È un numero di bordi incidenti su un vertice.
• Grafico collegato - Se esiste un percorso da un vertice casuale a qualsiasi altro vertice, quel grafico è noto come grafico collegato.

1. In un albero esiste un solo percorso tra due vertici mentre un grafico può avere percorsi unidirezionali e bidirezionali tra i nodi.
2. Nell'albero esiste esattamente un nodo radice e ogni figlio può avere un solo genitore. Al contrario, in un grafico, non esiste un concetto del nodo radice.
3. Un albero non può avere anelli e anelli automatici mentre il grafico può avere anelli e anelli automatici.
4. I grafici sono più complicati in quanto possono avere loop e loop automatici. Al contrario, gli alberi sono semplici rispetto al grafico.
5. L'albero viene attraversato utilizzando tecniche di pre-ordine, in ordine e post-ordine. D'altra parte, per l'attraversamento dei grafici, utilizziamo BFS (Breadth First Search) e DFS (Depth First Search).
6. Un albero può avere bordi n-1. Al contrario, nel grafico non esiste un numero predefinito di spigoli e dipende dal grafico.
7. Un albero ha una struttura gerarchica mentre il grafico ha un modello di rete.

Conclusione

Il grafico e l'albero sono la struttura di dati non lineari utilizzata per risolvere vari problemi complessi. Un grafico è un gruppo di vertici e bordi in cui un bordo collega una coppia di vertici mentre un albero è considerato un grafico minimamente connesso che deve essere collegato e privo di anelli.