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

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 árboles y la búsqueda basada en gráficos?

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 un DAG). 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, los árboles no son una estructura de datos recursiva. No se pueden implementar como una estructura de datos recursiva debido a las restricciones anteriores. Pero también se puede usar cualquier implementación de DAG, que generalmente no es recursiva. Mi implementación preferida de Tree es una representación de mapa centralizada y no es recursiva.

Generalmente, los gráficos se buscan primero en anchura o en profundidad. Lo mismo se aplica al árbol.

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

Un árbol en tiempo real

Un gráfico en uso en la vida real

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

Verlos así hace la vida más fácil. Los árboles se usan en lugares donde sabemos que cada nodo tiene un solo padre. Pero los gráficos pueden tener múltiples predecesores (el término padre generalmente no se usa para los 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 múltiples puntos. Los puntos que conducen a este nodo se denominan predecesores y los puntos a los que conducirá este nodo se denominan sucesores.

El diagrama del circuito eléctrico, el plano de una casa, una red informática o un sistema fluvial son algunos ejemplos más de gráficos. Muchos ejemplos del mundo real pueden considerarse como gráficos.

El diagrama técnico podría ser así

Arbol

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

Las otras respuestas son útiles, pero les faltan las propiedades de cada una:

Grafico

^{Gráfico no dirigido, fuente de la imagen: Wikipedia}

^{Gráfico dirigido, fuente de la imagen: Wikipedia}

• Consiste en un conjunto de vértices (o nodos) y un conjunto de bordes que conectan algunos o todos
• Cualquier borde puede conectar dos vértices que no estén conectados por un borde idéntico (en la misma dirección, en el caso de un gráfico dirigido)
• No tiene que estar conectado (los bordes no tienen que conectar todos los vértices): un solo gráfico puede constar de unos pocos conjuntos de vértices desconectados

• Podría ser dirigido o no dirigido (lo que se aplicaría a todos los bordes en el gráfico)
  Según Wikipedia :

  Por ejemplo, si los vértices representan a personas en una fiesta, y hay un límite entre dos personas si se dan la mano, entonces este gráfico no está dirigido porque cualquier persona A puede darle la mano a una persona B solo si B también le da la mano a A. Por el contrario, si cualquier borde de una persona A a una persona B corresponde a A admirando a B, entonces este gráfico está dirigido, porque la admiración no es necesariamente recíproca.

Árbol

^{Fuente de la imagen: Wikipedia}

• Un tipo de gráfico
• Los vértices se denominan más comúnmente "nodos"
• Los bordes están dirigidos y representan una relación "es hijo de" (o "es padre de")
• Cada nodo (excepto el nodo raíz) tiene exactamente un padre (y cero o más hijos)
• Tiene exactamente un nodo "raíz" (si el árbol tiene al menos un nodo), que es un nodo sin un padre
• Tiene que estar conectado
• Es acíclico, lo que significa que no tiene ciclos : "un ciclo es una ruta [secuencia AKA] de bordes y vértices en los que se puede alcanzar un vértice desde sí mismo"

Existe cierta superposición en las propiedades anteriores. Específicamente, las dos últimas propiedades están implicadas por el resto de las propiedades. Pero todos ellos son dignos de mención.

En el árbol, cada nodo (excepto el nodo raíz) tiene exactamente un nodo predecesor y uno o dos nodos sucesores. Se puede atravesar usando los recorridos En orden, Preordenar, Postordenar y Breadth First. El árbol es un tipo especial de gráfico que no tiene ciclo, por lo que se conoce como DAG (gráfico acíclico dirigido). El árbol es un modelo jerárquico.

En el gráfico, cada nodo tiene uno o más nodos predecesores y nodos sucesores. El gráfico se recorre mediante el uso de algoritmos de búsqueda en profundidad (DFS) y búsqueda en profundidad (BFS). El gráfico tiene ciclo, por lo que es más complejo que el árbol. Graph es un modelo de red. Hay dos tipos de gráficos: gráficos dirigidos y gráficos no dirigidos.

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

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

Los mapas se pueden implementar usando árboles, espero que no te resulte confuso.

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

Los gráficos son más complejos que los árboles. Los árboles implican relaciones recursivas entre padres e hijos. Hay formas naturales de atravesar un árbol: primero en profundidad, primero en ancho, 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 rápida en cualquier texto de estructura de datos decente (por ejemplo, "Manual de diseño de algoritmos") daría más y mejor información que cualquier número de respuestas SO. Te recomendaría que no tomes la ruta pasiva y comiences a investigar por ti mismo.

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

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

También puede ver más detalles: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

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] Típicamente, 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.

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

Un árbol es un dígrafo tal que:

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

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

b) cada vértice menos uno, la raíz, tiene 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 un grado 0 o la suposición de que los nodos distintos de la raíz tienen grado 1

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

El árbol es básicamente un gráfico no dirigido que no contiene ciclo, por lo que podemos decir que el árbol es una forma de gráfico más restringida. Sin embargo, el árbol y el gráfico tienen una aplicación diferente para implementar varios algoritmos en la programación. Por ejemplo, el gráfico se puede usar para la hoja de ruta modelo y el árbol se puede usar para implementar cualquier estructura de datos jerárquica.