A livello accademico, qual è la differenza essenziale tra la struttura dei dati Albero e Grafico? E che dire della ricerca ad albero e della ricerca basata sui grafici?Qual è la differenza tra la struttura dei dati Albero e Grafico?
Gli alberi sono ovvi: sono strutture dati ricorsive composte da nodi con bambini.
Mappa (alias dizionario) sono coppie chiave/valore. Assegna una chiave a una mappa e restituirà il valore associato.
Le mappe possono essere implementate utilizzando gli alberi, spero che non ti confonda.
AGGIORNAMENTO: confondere il "grafico" per "mappa" è molto confuso.
I grafici sono più complessi degli alberi. Gli alberi implicano relazioni ricorsive genitori/figli. Esistono modi naturali per attraversare un albero: profondità prima, larghezza, ordine di livello, ecc.
I grafici possono avere percorsi unidirezionali o bidirezionali tra i nodi, essere ciclici o aciclici, ecc. considera i grafici più complessi.
Penso che una ricerca rapida in qualsiasi testo di strutture dati decente (ad esempio "Algorithms Design Manual") fornisca più e migliori informazioni rispetto a qualsiasi numero di risposte SO. Ti raccomando di non seguire la via passiva e iniziare a fare qualche ricerca per te stesso.
Un albero è solo una forma limitata di un grafico.
Gli alberi hanno direzione (relazioni padre/figlio) e non contengono cicli. Si adattano alla categoria dei grafici aciclici diretti (o di un DAG). Quindi gli alberi sono DAG con la restrizione che un bambino può avere solo un genitore.
Una cosa che è importante sottolineare, Trees non è una struttura di dati ricorsiva. Non possono essere implementati come una struttura dati ricorsiva a causa delle restrizioni di cui sopra. Ma qualsiasi implementazione di DAG, che in genere non è ricorsiva, può anche essere utilizzata. La mia implementazione Tree preferita è una rappresentazione centralizzata della mappa ed è non ricorsiva.
I grafici sono in genere il respiro di ricerca prima o la profondità prima. Lo stesso vale per Tree.
I grafici sono molto utili e possono essere utilizzati per modellare una quantità enorme di cose. Un sacco di altre strutture dati può essere visto come un grafico con restrizioni. Ad esempio, un elenco collegato singolarmente è un caso speciale di un DAG. –
@ user785287 cosa intendi per * rappresentazione della mappa centralizzata *? – Geek
"Gli alberi non sono una struttura dati ricorsiva" è fuorviante e sbagliato. Un albero * può * essere rappresentato con una struttura dati non ricorsiva (ad esempio un array di spigoli, un albero completo, come quello sottostante un heap binario, può essere rappresentato in modo molto compatto in un array, ci sono altre rappresentazioni * succinte * ecc. ecc.), ma probabilmente il modo più popolare e utile per rappresentarli è l'utilizzo di una struttura basata su puntatori ricorsivi. La rappresentazione non è unica per gli alberi senza radici, ma è irrilevante. –
In matematica, un grafico è una rappresentazione di un insieme di oggetti in cui alcune coppie di oggetti sono collegate da collegamenti. Gli oggetti interconnessi sono rappresentati da astrazioni matematiche chiamate vertici, ei collegamenti che connettono alcune coppie di vertici sono chiamati bordi. [1] Tipicamente, un grafico è rappresentato in forma schematica come un insieme di punti per i vertici, uniti da linee o curve per i bordi. I grafici sono uno degli oggetti di studio nella matematica discreta.
un nodo radice nell'albero e un solo genitore per un figlio. Tuttavia, non esiste un concetto di nodo radice. Un'altra differenza è che l'albero è un modello gerarchico ma il grafico è un modello di rete.
Invece di spiegare preferisco mostrarlo nelle immagini.
Un albero in tempo reale
Un grafico in uso vita reale
Sì una mappa può essere visualizzato come una struttura di dati del grafico.
vederli così rende la vita più facile. Gli alberi vengono utilizzati nei luoghi in cui sappiamo che ogni nodo ha un solo genitore. Ma i grafici possono avere più predecessori (il termine parent è generalmente non utilizzato per i grafici).
Nel mondo reale, è possibile rappresentare quasi tutto utilizzando i grafici. Ho usato una mappa, per esempio. Se consideri ciascuna città come un nodo, può essere raggiunta da più punti. I punti che portano a questo nodo sono chiamati predecessori e i punti a cui questo nodo porteranno sono chiamati successori.
diagramma di circuito elettrico, il piano di una casa, rete di computer o un sistema fluviale sono pochi altri esempi di grafici. Molti esempi del mondo reale possono essere considerati come grafici.
schema tecnico potrebbe essere come questo
Albero:
Grafico:
Assicurarsi di fare riferimento al di sotto del link. Quelli risponderanno a quasi tutte le tue domande su alberi e grafici.
Riferimenti:
mi piacciono le immagini +1 – iliketocode
Albero è speciale forma di grafico cioè mi grafico collegato in via definitiva e con un solo percorso tra due vertici.
Nel grafico può esserci più di un percorso, ad es.grafico può avere percorsi unidirezionali o bidirezionali (bordi) tra i nodi
Inoltre è possibile vedere ulteriori dettagli: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/
L'albero è una forma speciale di grafico, cioè un grafico minimamente connesso e con un solo percorso tra due vertici.
L'albero è un caso speciale di grafico senza loop, senza circuiti e senza auto-loop.
Nell'albero esiste esattamente un nodo radice e ogni bambino ha un solo genitore.
Negli alberi, esiste una relazione padre figlio in modo che il flusso possa essere lì con direzione dall'alto verso il basso o viceversa.
5. I trilogi sono meno complessi dei grafici poiché non hanno cicli, non sono self-loop e sono ancora connessi.
6. Il traversal è un tipo di caso speciale di attraversamento del grafico. L'albero è attraversato in preordine, in ordine e post-ordine (tutti e tre in DFS o nell'algoritmo BFS)
7. Negli alberi, ci sono molte regole/restrizioni per effettuare connessioni tra i nodi attraverso i bordi.
8.Tre sono nella categoria di DAG: Diretti Grafici aciclici è un tipo di grafico diretto che non ha cicli.
9. I diversi tipi di alberi sono: Albero binario, Albero di ricerca binaria, Albero AVL, Mucchi.
10. Applicazioni: selezione e ricerca come Tree Traversal & Ricerca binaria.
11.Aree ha sempre bordi n-1.
12.Tree è un modello gerarchico.
Nel grafico ci possono essere più di un percorso cioè grafico può avere unidirezionali o bidirezionali percorsi (bordi) tra nodi
- Il grafico può avere loop, circuiti e può avere cicli self-loop.
3.In grafico non esiste il concetto di nodo radice.
4.In Graph non esiste una relazione genitore-figlio.
5.I grafici sono più complessi in confronto agli alberi come può avere cicli, cicli ecc
6.Graph è attraversato da DFS: ricerca in profondità e in BFS: ricerca in ampiezza algoritmo
7.In grafici tali regole/restrizioni sono lì per collegare i nodi attraverso i bordi.
8. Il grafico può essere ciclico o aciclico.
9. Mucchi. Esistono principalmente due tipi di grafici: grafici diretti e non diretti.
applicazioni 10.Graph: Colorazione delle mappe, in OR (PERT & CPM), algoritmi, grafico coloranti, pianificazione dei processi, ecc
- Nel grafico, n. dei bordi dipendono dal grafico.
12.Graph è un modello di rete.
Esempio Albero:
Grafico:
dispiace, voglio dire il grafico, ho digitato la mappa. – user918304
"Confondere" il grafico "per" mappa "è molto confuso." :) – cpz
Dire "i grafici sono più complessi degli alberi" è come dire "I corvi sono più specializzati degli uccelli". Non dovremmo invece dire che "Tutti gli alberi sono grafici, ma non tutti i grafici sono alberi"? – dudewad