Una struttura di dati non lineare è costituita da una raccolta di elementi che sono distribuiti su un piano, il che significa che non esiste una tale sequenza tra gli elementi così come esiste in una struttura di dati lineare.
Grafico comparativo
| 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 radice. |
| Loops | Non sono permessi loop. | Il grafico può avere loop. |
| Complessità | Meno complesso | Più complesso in confronto |
| Tecniche di attraversamento | Pre-ordine, in-order e post-order. | Ricerca in ampiezza e ricerca in profondità. |
| Numero di bordi | 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 solitamente definiti come nodi. Come accennato sopra, un albero è una struttura di dati non lineare che organizza gli elementi di dati in ordine ordinato. È usato 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 determina una formazione del circuito o del circuito.
Ci sono diversi tipi di alberi come un albero binario, albero di ricerca binario, albero AVL, albero binario filettato, albero B, ecc. La compressione dei dati, l'archiviazione 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.
- I restanti elementi di dati sono divisi in sottoinsiemi disgiunti che si riferiscono a come sottostruttura.
- L'albero è espanso in altezza verso il basso.
- Un albero deve essere connesso, il che significa che deve esserci un percorso da una radice a tutti gli altri nodi.
- Non contiene alcun anello.
- Un albero ha bordi n-1.
Ci sono vari termini associati con alberi come nodo terminale, bordo, livello, grado, profondità, foresta, ecc. Tra questi termini, alcuni di essi sono 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 sottoalberi di un nodo in un dato albero.
- Profondità - È il livello massimo di qualsiasi nodo in un dato albero e noto anche come altezza .
- Terminal node - Il nodo di livello più alto è il nodo terminale mentre altri nodi, ad eccezione del nodo terminale e root, sono noti come nodi non terminali.
Definizione del grafico
Un grafico è anche una struttura dati matematica non lineare che può rappresentare vari tipi di struttura fisica. Consiste in un gruppo di vertici (o nodi) e un insieme di spigoli che collegano i due vertici. I vertici sul grafico sono rappresentati come punti o cerchi e i bordi vengono visualizzati come archi o segmenti di linea. Un bordo è rappresentato da E (v, w) dove vew sono le coppie di vertici. La rimozione di un bordo da un circuito o 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 della rete sociale, circuiti elettrici e pianificazione del progetto sono alcune delle applicazioni della struttura dei dati del grafico. Viene anche impiegato nella tecnica di gestione denominata PERT (tecnica di valutazione e revisione del programma) 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 bidirezionato o diretto.
- Un bordo può essere ponderato.
Nel grafico usiamo anche vari termini come vertici adiacenti, percorso, ciclo, grado, grafico connesso, grafico completo, grafico ponderato, ecc. Comprendiamo alcuni di questi termini.
- Vertici adiacenti - Un vertice a è adiacente al vertice b se c'è un bordo (a, b) o (b, a).
- Percorso : un percorso da un vertice casuale w è una sequenza adiacente di vertici.
- Ciclo : è un percorso in cui il primo e l'ultimo vertice sono gli stessi.
- Grado : è un numero di bordi incidente su un vertice.
- Grafico connesso - Se esiste un percorso da un vertice casuale a qualsiasi altro vertice, allora tale grafico è noto come un grafico connesso.
Differenze chiave tra albero e grafico
- In un albero esiste un solo percorso tra due vertici, mentre un grafico può avere percorsi unidirezionali e bidirezionali tra i nodi.
- Nell'albero, esiste esattamente un nodo radice e ogni bambino può avere un solo genitore. Per contro, in un grafico non esiste il concetto del nodo radice.
- Un albero non può avere loop e self-loops mentre il grafico può avere loop e self-loops.
- I grafici sono più complicati in quanto possono avere loop e self-loops. Al contrario, gli alberi sono semplici rispetto al grafico.
- L'albero viene attraversato utilizzando le tecniche di preordine, in ordine e post-ordine. D'altra parte, per il traversal grafico, usiamo BFS (Larghezza prima ricerca) e DFS (Depth First Search).
- Un albero può avere bordi n-1. Al contrario, nel grafico non esiste un numero predefinito di spigoli e dipende dal grafico.
- Un albero ha una struttura gerarchica mentre il grafico ha un modello di rete.
Conclusione
Grafico e struttura ad albero sono la struttura dati non lineare utilizzata per risolvere vari problemi complessi. Un grafico è un gruppo di vertici e spigoli in cui un bordo collega una coppia di vertici mentre un albero è considerato come un grafo minimamente connesso che deve essere connesso e libero da anelli.
