Una estructura de datos no lineal consiste en una colección de los elementos que se distribuyen en un plano, lo que significa que no existe tal secuencia entre los elementos como existe en una estructura de datos lineal.
Gráfica comparativa
| Bases para la comparación | Árbol | Grafico |
|---|---|---|
| Camino | Sólo uno entre dos vértices. | Se permite más de un camino. |
| Nodo raíz | Tiene exactamente un nodo raíz. | El gráfico no tiene un nodo raíz. |
| Bucles | No se permiten bucles. | La gráfica puede tener bucles. |
| Complejidad | Menos complejo | Más complejo comparativamente |
| Técnicas de travesía | Pre-order, In-order y Post-order. | Búsqueda en amplitud y búsqueda en profundidad. |
| Número de aristas | n-1 (donde n es el número de nodos) | No definida |
| Tipo de modelo | Jerárquico | Red |
Definición de árbol
Un árbol es una colección finita de elementos de datos generalmente denominados nodos. Como se mencionó anteriormente, un árbol es una estructura de datos no lineal que organiza los elementos de datos en orden ordenado. Se utiliza para mostrar una estructura jerárquica entre los diversos elementos de datos y organizar los datos en ramas que relacionan la información. La adición de un nuevo borde en un árbol da como resultado una formación del bucle o circuito.
Existen varios tipos de árboles, como un árbol binario, un árbol de búsqueda binario, un árbol AVL, un árbol binario, un árbol B, etc. La compresión de datos, el almacenamiento de archivos, la manipulación de la expresión aritmética y los árboles de juegos son algunas de las aplicaciones del árbol. estructura de datos.
Propiedades del arbol:
- Hay un nodo designado en la parte superior del árbol conocido como raíz del árbol.
- Los elementos de datos restantes se dividen en subconjuntos desunidos, se refieren como subárbol.
- El árbol se expande en altura hacia el fondo.
- Un árbol debe estar conectado, lo que significa que debe haber una ruta desde una raíz a todos los demás nodos.
- No contiene bucles.
- Un árbol tiene n-1 aristas.
Hay varios términos asociados con árboles, como nodo terminal, borde, nivel, grado, profundidad, bosque, etc. Entre esos términos, algunos de ellos se describen a continuación.
- Borde - Una línea que conecta dos nodos.
- Nivel : un árbol se divide en niveles de forma tal que el nodo raíz se encuentra en el nivel 0. Luego, sus hijos inmediatos están en el nivel 1, y sus hijos inmediatos están en el nivel 2 y así sucesivamente hasta el terminal o nodo hoja.
- Grado : es el número de subárboles de un nodo en un árbol determinado.
- Profundidad : es el nivel máximo de cualquier nodo en un árbol dado y también se conoce como altura .
- Nodo terminal: el nodo de nivel más alto es nodo terminal, mientras que otros nodos, excepto terminal y nodo raíz, se conocen como nodos no terminales.
Definición de gráfico
Un gráfico es también una estructura de datos matemática no lineal que puede representar varios tipos de estructura física. Consiste en un grupo de vértices (o nodos) y un conjunto de bordes que conectan los dos vértices. Los vértices en el gráfico se representan como puntos o círculos y los bordes se muestran como arcos o segmentos de líneas. Un borde está representado por E (v, w) donde v y w son los pares de vértices. La eliminación de un borde de un circuito o gráfico conectado crea un subgrafo que es un árbol.
Los gráficos se clasifican en varias categorías, tales como dirigido, no dirigido, conectado, no conectado, simple y multi-gráfico. Red de computadoras, sistema de transporte, gráfico de redes sociales, circuitos eléctricos y planificación de proyectos son algunas de las aplicaciones de la estructura de datos de gráficos. También se emplea en la técnica de gestión denominada PERT (técnica de evaluación y evaluación de programas) y CPM (método de ruta crítica) en la que se analiza la estructura del gráfico.
Propiedades de una gráfica:
- Un vértice en un gráfico se puede conectar a cualquier número de otros vértices usando bordes.
- Un borde puede ser bidireccionado o dirigido.
- Un borde puede ser ponderado.
En el gráfico también utilizamos varios términos como vértices adyacentes, trayectoria, ciclo, grado, gráfico conectado, gráfico completo, gráfico ponderado, etc. Entendamos algunos de estos términos.
- Vértices adyacentes : un vértice a es adyacente al vértice b si hay un borde (a, b) o (b, a).
- Ruta : una ruta desde un vértice aleatorio w es una secuencia adyacente de vértices.
- Ciclo : es una ruta en la que los vértices primero y último son iguales.
- Grado - Es una serie de bordes incidentes en un vértice.
- Gráfico conectado : si existe una ruta desde un vértice aleatorio a cualquier otro vértice, entonces ese gráfico se conoce como un gráfico conectado.
Diferencias clave entre árbol y gráfico
- En un árbol solo existe una ruta entre dos vértices, mientras que una gráfica puede tener rutas unidireccionales y bidireccionales entre los nodos.
- En el árbol, hay exactamente un nodo raíz, y cada hijo solo puede tener un padre. A diferencia de, en una gráfica, no hay un concepto del nodo raíz.
- Un árbol no puede tener loops y self-loops, mientras que el gráfico puede tener loops y self-loops.
- Los gráficos son más complicados, ya que puede tener bucles y auto-bucles. En contraste, los árboles son simples en comparación con el gráfico.
- El árbol se recorre utilizando técnicas de pre-orden, en orden y post-orden. Por otro lado, para el recorrido del gráfico, usamos BFS (búsqueda en amplitud) y DFS (búsqueda en profundidad).
- Un árbol puede tener n-1 aristas. Por el contrario, en el gráfico, no hay un número predefinido de bordes, y depende del gráfico.
- Un árbol tiene una estructura jerárquica, mientras que el gráfico tiene un modelo de red.
Conclusión
Gráfico y árbol son la estructura de datos no lineales que se utiliza para resolver varios problemas complejos. Un gráfico es un grupo de vértices y bordes donde un borde conecta un par de vértices, mientras que un árbol se considera como un gráfico mínimamente conectado que debe estar conectado y libre de bucles.
