En esta unidad se abordará el tema de las estructuras dinámicas no lineales, o estructuras de datos multienlazadas, que a medida que el programa se ejecuta dinámicamente crecen o decrecen según lo que se necesiten. Además, cuentan con elementos denominados nodos y se diferencian con el registro porque el almacenamiento es fijo de acuerdo con el número de elementos.

Cuando cada elemento solo puede ir enlazado al siguiente o al anterior se dicen que son estructuras dinámicas lineales, en cambio en las no lineales el nodo puede enlazarse con cualquier otro elemento.

Cada nodo puede tener varios predecesores y/o varios sucesores, como se evidencia en los grafos y árboles.

Objetivo general

Emplear estructuras no lineales en la codificación de un algoritmo con el uso de un lenguaje de programación.

Objetivos específicos

• Definir el concepto de árboles y grafos.
• Reconocer las estructuras árboles y grafos.

Un árbol es una estructura dinámica no lineal que consiste en un conjunto finito de uno o más nodos, con un nodo llamado Raíz que apunta a la entrada del árbol y nodos restantes denominados sub-árboles. Cada nodo puede ser padre o hijo; cuando un nodo no tiene hijo, éste se llama nodo terminal u hoja.

Cada nodo está constituido por una parte que almacena información y dos partes tipo referencia que se utilizan para referenciar los subárboles izquierdo y derecho. Estas partes pueden ser nulos si el nodo no tiene hijos.

Se sugiere consultar los libros: Estructuras de datos en JAVA, por Mark Allen Weiss (2010). Estructuras de datos datos y algoritmos en Java, por Adam Drozdek (2007), en su capítulo 6: árboles binarios. Estructuras de datos, un enfoque moderno, por Marco Antonio Gómez, Pedro Antonio Gonzalez, & Mario Rodriguez (2011), en su capítulo 5: árboles.

Dentro de los algoritmos utilizados para las estructuras dinámicas no lineales se encuentran:

• Árbol binario: dado su nombre debido a que solo acepta dos sub árboles, a la izquierda o a la derecha.
• Árbol AVL (Adelson-Velskii-Landis): están equilibrados, la altura del lado izquierda no difiere en más de una unidad de la altura de la rama derecha y viceversa; la complejidad de búsqueda se mantiene en 0(log_n).
• Árboles sintáctico de expresiones: las hojas del árbol son operandos, mientras que el restos del árbol son operadores, en esencia son árboles binarios.
• Algoritmo de Huffman: se maneja un bosque de árboles, el peso de un árbol es igual a la suma de las frecuencias de sus hojas.
• Árbol completo: árbol cuyos nodos o bien son hojas o bien tienen hijos.
• Trie binario: estructuras de datos en la que una rama izquierda representa un 0 (cero) y una rama derecha representa un 1. El camino a cada nodo indica su codificación.
• Árbol Rojo-Negro: es un árbol binario de búsqueda equilibrada, originalmente creada por Rudolf Bayer, también llamados “Árboles Binarios simétricos”.

Material de apoyo

De los árboles más utilizados tenemos los árboles binarios, dado su nombre debido a que solo acepta dos sub-árboles, a la izquierda o a la derecha.

Un árbol binario se puede recorrer de las siguientes formas:

• Inorden: Se recorre el subárbol izquierdo; se muestra el nodo raíz; se recorre el subárbol derecho.
• Preorden: Se muestra el nodo raíz; se recorre el subárbol izquierdo en pre orden; recorre el subárbol derecho en preorden.
• Posorden: Se recorre el subárbol izquierdo en posorden; se recorre el subárbol derecho en posorden; se muestra el nodo raíz.

El recorrido se debe realizar de forma recursiva para optimizar su rendimiento.

• Los sub-árboles izquierdo y derecho deben tener subconjuntos disjuntos, es decir ningún nodo pueden estar en ambos sub-árboles.
• El número máximo de nodos en el nivel (profundidad), i de un árbol binario es: 2^i-1, i>=1, y el número máximo de nodos de un árbol binario de altura k es 2^k-1, k>=1.
• Para cualquier árbol binario no vacío, si n₀ es el número de nodos terminales y n₂ es el número de nodos de grado 2, entonces se cumple que .n₀ = n₂ + 1.
• Cuando un árbol binario de altura k tiene 2^k-1, éste se considera lleno.

Un grafo está compuesto de objetos llamados vértices y pares de vértices, llamados aristas, que son orientados o no.

• Arista: es la unión de dos vértices de un grafo. Si la línea carece de dirección se denota indistintamente los vértices que une.
• Aristas adyacentes: cuando dos aristas en el mismo vértice confluyen.
• Aristas paralelas: dos aristas son paralelas si los vértices iniciales y el final son iguales.
• Aristas cíclicas: sale y llega de al mismo vértice.
• Cruce: es la intersección de dos aristas sobre un punto.
• Vértice : son los puntos de un grafo.
• Grado de un vértice: total de aristas extremo.
• Vértices adyacentes: es la arista que une un par de vértices.
• Vértice aislado: cuyo grado es cero.
• Vértice terminal: es aquel que tiene un grado 1.
• Caminos: serie de vértices unidos por aristas.
• Circuitos: los vértices iniciales y finales de un camino llegan al mismo sitio.

Se sugiere consultar el libro Estructuras de datos y algoritmos en JAVA (segunda edición) de Roberto Tamassia, & Michael Goodrich (2002), en la sección "travesía de grafo", página 642.

Material de apoyo

Existen tres métodos clásicos para recorrer un grafo:

• A lo ancho: se recorre por niveles
• En profundidad: se asemeja al recorrido inorden de un árbol.
• Topológicamente: consiste en recorrerlo de manera que no se visite un vértice sin haberse visitado sus predecesores.

El recorrido a lo ancho debe informar:

• El orden de visita a cada vértice
• El padre de cada vértice.

Así se realiza el recorrido en profundidad:

• Debe hacerse uso de la recursividad.
• Se visita el vértice original, luego el primer adjunto a ese vértice original, luego el adjunto segundo vértice adjunto y así sucesivamente.
• Se generan líneas de regreso, si el vértice almacenado en p->V ya fue visitado; adicionalmente, si el vértice p->v no es el padre del vértice almacenado en v del ambiente en el que se esté en ese momento.

Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos A. Los vértices se denominan nodos o puntos. Los arcos pueden llamarse arcos dirigidos o líneas dirigidas. Un arco es un par ordenado de vértices A(v,w) donde v es la cola y w es la cabeza del arco.

Un camino es simple si todos sus vértices, excepto el primero y el ultimo son distintos. Un ciclo simple es un camino simple de longitud uno que comienza y termina en el mismo vértice.

Un grafo ponderado está conformado por números reales y es simple si tiene agregada una función de ponderación.

Se pone el valor del peso si se tiene y el símbolo infinito cuando no se encuentre valor alguno. La suma de los pesos de un camino es la suma de los pesos de las aristas que la conforman.

El algoritmo de caminos más cortos entre todos los pares (CMCP) o Dijkstra, con un vértice origen y con peso en cada arista, consiste en revisar todos los caminos y evaluar los pesos en cada vértice y escoger el menos costoso hasta llegar al final. Se trata de un algoritmo que no aplica a costos negativos.

El algoritmo consiste en determinar cuál es la distancia mínima entre un vértice y todos los demás, las distancias desconocidas se asignan con un valor infinito menos el valor del nodo inicial que se coloca en 0 (cero).

Se recorren los nodos adyacentes del nodo actual, excepto los nodos donde se han evaluado. Tomamos como el próximo nodo, al de menor valor con relación al nodo actual y volvemos a realizar los pasos anteriores, mientras existan nodos no marcados.

La ruta crítica es empleada, con la ayuda de los grafos, para el control de proyectos y para calcular tiempos y plazos. Fue un método desarrollado por Dupont y Remington Rand en 1957 para optimizar costos por medio de la planificación y programación de las actividades del proyecto.

Adicionalmente, la ruta crítica hace uso de tiempos reales o determinístico y consisten en:

• Identificación de todas las actividades del proyecto, determinando relaciones de precedencia y tiempos.
• Realizar un grafo que permita plasmar el proyecto.
• Identificar la ruta crítica y holguras para cada actividad del proyecto.

Se trata de un grafo ponderado o grafo con pesos; es un grafo G(V,E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso. El peso de un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas.

Un árbol generador mínimo de un grafo conexo G con pesos es un árbol generador de G que tiene el menor peso. En general no es único. Se denota por MST(G) (minimum spanning tree).

Para hallar los árboles generadores mínimos, se hace uso de los algoritmos de Prim y Kruskal.

Los árboles y grafos son utilizados en ingeniería industrial para el control de procesos industriales. Las estructuras dinámicas no lineales son empleadas además en muchos algoritmos para la solución de problemas.

La mayoría de las aplicaciones se evidencian en el campo de la ofimática, como las hojas electrónicas, son utilizadas; además los expertos utilizan algoritmos de ruta crítica para determinar el costeo de producción

Son utilizados para resolver problemas como:

• El problema de los siete puentes
• El problema del caballo de ajedrez
• El problema de los cuatro colores