type open example content compartir search data-structures map tree

search - open - ¿Cuál es la diferencia entre la estructura de datos Tree y Graph?



open graph (8)

Un árbol es un dígrafo tal que:

a) con las direcciones de borde eliminadas, está conectado y acíclico

  1. Puede eliminar la suposición de que es acíclico
  2. Si es finito, alternativamente puede eliminar la suposición de que está conectado

b) cada vértice menos uno, la raíz, tiene un grado 1

c) la raíz tiene indegree 0

  1. Si solo hay un número finito de nodos, puede eliminar la suposición de que la raíz tiene indegree 0 o la suposición de que los nodos que no sean la raíz tienen el grado 1

Referencia: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

Académicamente hablando, ¿cuál es la diferencia esencial entre la estructura de datos Tree y Graph? ¿Y qué hay de la búsqueda basada en árbol y la búsqueda basada en gráficos?

Diferencia entre Graph y Tree Data Structure

Árboles

  1. El árbol es una forma especial de gráfico, es decir, un gráfico mínimamente conectado y que tiene una sola ruta entre dos vértices.

  2. El árbol es un caso especial de gráfico que no tiene bucles, no tiene circuitos ni bucles automáticos.

  3. En el árbol hay exactamente un nodo raíz y cada hijo tiene solo un padre.

  4. En los árboles, existe una relación entre padres e hijos para que el flujo pueda estar allí con la dirección de arriba a abajo o viceversa.

5.Los árboles son menos complejos que los gráficos, ya que no tienen ciclos, no tienen circuitos automáticos y aún están conectados.

6.Tree transversal es una especie de caso especial de recorrido de gráfico. El árbol se recorre en Pre-Order, In-Order y Post-Order (los tres en DFS o en el algoritmo BFS)

7.En los árboles, hay muchas reglas / restricciones para hacer conexiones entre nodos a través de los bordes.

8.Tres vienen en la categoría de DAG: Gráficos acíclicos dirigidos es un tipo de gráfico dirigido que no tiene ciclos.

9.Diferentes tipos de árboles son: árbol binario, árbol de búsqueda binaria, árbol AVL, montículos.

10. Tres aplicaciones: ordenar y buscar como Tree Traversal & Binary Search.

11. El árbol siempre tiene n-1 bordes.

12. El árbol es un modelo jerárquico.

Gráficos

  1. En el gráfico, puede haber más de una ruta, es decir, el gráfico puede tener trayectorias (bordes) unidireccionales o bidireccionales entre los nodos.

    1. Graph puede tener bucles, circuitos y puede tener bucles automáticos.

3. En el gráfico no existe tal concepto de nodo raíz.

4. En Graph no existe tal relación padre-hijo.

5. Los grafos son más complejos en comparación con los árboles, ya que pueden tener ciclos, bucles, etc.

6.Graph es atravesado por DFS: primera búsqueda de profundidad y en BFS: primer algoritmo de búsqueda de amplitud

7. En los gráficos, no existen tales reglas / restricciones para conectar los nodos a través de los bordes.

8.Graph puede ser cíclico o acíclico.

9. Cabezas. Existen principalmente dos tipos de gráficos: gráficos dirigidos y no dirigidos.

10. Aplicaciones gráficas: coloración de mapas, en quirófano (PERT y CPM), algoritmos, coloreado de gráficos, programación de trabajos, etc.

  1. En Graph, no. de bordes depende del gráfico.

12.Graph es un modelo de red.

Árbol de ejemplo:

Grafico:

En lugar de explicar, prefiero mostrarlo en imágenes.

Un árbol en tiempo real

Un gráfico en el uso de la vida real

Sí, un mapa se puede visualizar como una estructura de datos de gráfico.

Verlos así hace la vida más fácil. Los árboles se usan en lugares donde sabemos que cada nodo tiene solo un padre. Pero los gráficos pueden tener múltiples predecesores (el término principal generalmente no se usa para gráficos).

En el mundo real, puedes representar casi cualquier cosa usando gráficos. Usé un mapa, por ejemplo. Si considera cada ciudad como un nodo, se puede llegar desde varios puntos. Los puntos que conducen a este nodo se denominan predecesores y los puntos a los que conducirá este nodo se denominan sucesores.

diagrama de circuito eléctrico, el plan de una casa, red de computadoras o un sistema fluvial son algunos ejemplos más de gráficos. Muchos ejemplos del mundo real se pueden considerar como gráficos.

Diagrama técnico podría ser así

Árbol:

Grafico :

Asegúrese de consultar los enlaces a continuación. Esos responderán a casi todas sus preguntas sobre árboles y gráficos.

Referencias

  1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

  2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

  3. Wikipedia

En matemáticas, un gráfico es una representación de un conjunto de objetos donde algunos pares de objetos están conectados por enlaces. Los objetos interconectados están representados por abstracciones matemáticas llamadas vértices, y los enlaces que conectan algunos pares de vértices se llaman bordes. [1] Normalmente, un gráfico se representa en forma de diagrama como un conjunto de puntos para los vértices, unidos por líneas o curvas para los bordes. Los gráficos son uno de los objetos de estudio en matemáticas discretas.

Los árboles son obvios: son estructuras de datos recursivas que consisten en nodos con niños.

Mapa (también conocido como diccionario) son pares clave / valor. Dale una clave al mapa y devolverá el valor asociado.

Los mapas se pueden implementar usando árboles, espero que no los encuentren confusos.

ACTUALIZACIÓN: Confundir "gráfico" para "mapa" es muy confuso.

Los gráficos son más complejos que los árboles. Los árboles implican relaciones recursivas entre padres e hijos. Existen formas naturales de atravesar un árbol: primero en profundidad, primero en anchura, orden de nivel, etc.

Los gráficos pueden tener rutas unidireccionales o bidireccionales entre nodos, ser cíclicos o acíclicos, etc. Consideraría que los gráficos son más complejos.

Creo que una búsqueda superficial en cualquier texto de estructuras de datos decentes (por ejemplo, "Algorithms Design Manual") daría más y mejor información que cualquier número de respuestas SO. Le recomendaría que no tome la ruta pasiva y empiece a investigar por usted mismo.

Un árbol es solo una forma restringida de un gráfico.

Los árboles tienen dirección (relaciones padre / hijo) y no contienen ciclos. Encajan en la categoría de Gráficos acíclicos dirigidos (o DAG). Entonces, los árboles son DAG con la restricción de que un niño solo puede tener un padre.

Una cosa que es importante señalar, Trees no es una estructura de datos recursiva. No se pueden implementar como una estructura de datos recursiva debido a las restricciones anteriores. Pero cualquier implementación de DAG, que generalmente no es recursiva, también se puede usar. Mi implementación de árbol preferida es una representación de mapa centralizada y no recursiva.

Los gráficos generalmente buscan primero la respiración o la profundidad. Lo mismo aplica a Tree.

un nodo raíz en el árbol y solo un padre para un niño. Sin embargo, no existe el concepto de nodo raíz. Otra diferencia es que el árbol es un modelo jerárquico, pero el gráfico es un modelo de red.