Estructuras No Lineales PDF

Preview

Summary

Tipos Estructuras no lineales...

Description

INDICE Estructuras No Lineales Arboles

3

3

Clasificación de árboles.

3

Operaciones Básicas sobre árboles binarios ………………………………………………………………………….……4 Aplicaciones 4 Grafos

5

Representación de Grafos.

5

Operaciones Básicas 7 Referencias 8

Página 1|7

Estructuras No Lineales En una estructura lineal, cada elemento sólo puede ir enlazado al siguiente o al anterior. A las estructuras de datos no lineales se les llama también estructuras de datos multienlazadas. Cada elemento puede estar enlazado a cualquier otro componente. Se trata de estructuras de datos en las que cada elemento puede tener varios sucesores y/o varios predecesores. En estas estructuras cada elemento puede tener varios elementos “siguientes”, lo cual introduce el concepto de estructuras de ramificación. Estas estructuras de datos de ramificación son llamadas grafos y árboles.

Árboles Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto. Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Clasificación de árboles Existen cuatro tipos de árbol binario: -Distinto. -Similares. -Equivalentes. -Completos. DISTINTO Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. SIMILARES Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. EQUIVALENTES

Página 2|7

Son aquellos árboles que son similares y que además los nodos contienen la misma información. COMPLETOS Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.

Operaciones Básicas sobre árboles binarios Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles. De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas: *Añadir o insertar elementos. *Buscar o localizar elementos. *Borrar elementos. *Moverse a través del árbol. *Recorrer el árbol completo. Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles.

Aplicaciones Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de árboles con nodos de dos tipos, nodos directorio y nodos archivo, podríamos considerar que los nodos hoja son archivos y los nodos rama son directorios. Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo, de este mismo manual, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, como una lista, en el que cada capítulo sigue al anterior, también es posible acceder a cualquier punto de él a través de la tabla de contenido. También se suelen organizar en forma de árbol los organigramas de mando en empresas o en el ejército, y los árboles genealógicos.

Página 3|7

Grafos Un grafo es un conjunto de puntos y un conjunto de líneas, con cada línea se une un punto a otro. Los puntos se llaman los nodos del grafo, y las líneas se llaman aristas. Un grafo nulo es un grafo con orden cero. Una arista está determinada por los nodos que conecta. Un grafo está completamente definido por sus conjuntos de nodos y aristas. La posición real de estos elementos en la página no tiene importancia. Algunas aristas pueden conectar un nodo a sí mismo, a estas aristas se les llama bucles. Un grafo G se llama grafo simple si las siguientes condiciones son válidas. 1. No tiene ciclos (no existe una arista en E de la forma (v,v), donde V esta en V) 2.

No hay más de una arista uniendo un par de nodos, esto es, no existe más de una arista en E

de la forma (v1,v2), para cualquier par de elementos v y v en VG Un grafo que no es simple algunas veces es llamado multígrafo. Encontrará, que a las aristas también se les conoce como arcos y a los nodos como vértices. Un grafo conexo es una gráfica que no se puede dividir en dos gráficas, sin eliminar por lo menos una de las aristas.

Representación de Grafos Hay varias maneras de representar grafos, cada uno con sus ventajas y desventajas. Algunas situaciones, o algoritmos que queremos ejecutar que tengan grafos como entrada, requieren una representación, y otros requieren una representación diferente. Aquí, veremos tres formas de representar grafos. Veremos tres criterios. Una es cuánta memoria, o espacio, necesitamos en cada representación. Usaremos notación asintótica para eso. ¡Sí, podemos usar notación asintótica para otros fines además de expresar tiempos de ejecución! En realidad, es una forma de caracterizar funciones, y una función puede describir un tiempo de ejecución, una cantidad de espacio requerido, o algún otro recurso. Los otros dos criterios que usaremos se relacionan con el tiempo. Uno es cuánto se tarda en determinar si una arista dada está en el grafo. El otro es cuánto se tarda en encontrar los vecinos de un vértice dado.

Página 4|7

Es común identificar los vértices no por nombre (como "Audrey", "Boston" o "suéter") sino por un número. Es decir, típicamente numeramos los |V|∣V∣vertical bar, V, vertical bar vértices de 0 a | V|-1∣V∣−1vertical bar, V, vertical bar, minus, 1. Aquí está el grafo de la red social con sus 10 vértices identificados por números en lugar de nombres:

*Listas de aristas Una forma sencilla de representar un grafo es solo una lista, o un arreglo, de |E| ∣E∣vertical bar, E, vertical bar aristas, a la que llamamos una lista de aristas. Para representar una arista, solo tenemos un arreglo de dos números de vértices, o un arreglo de objetos que contienen los números de vértices sobre los que inciden las aristas. Si las aristas tienen pesos, agrega ya sea un tercer elemento al arreglo o más información al objeto, que dé el peso de la arista. Como cada arista contiene solo dos o tres números, el espacio total para una lista de aristas es \Theta(E)Θ(E)\Theta, left parenthesis, E, right parenthesis. *Matrices de adyacencia Para un grafo con |V|∣V∣vertical bar, V, vertical bar vértices, una matriz de adyacencia es una matriz de |V| \times |V|∣V∣×∣V∣vertical bar, V, vertical bar, times, vertical bar, V, vertical bar de ceros y unos, donde la entrada en el renglón iii y la columna jjj es 1 si y solo si la arista (i, j)(i,j)left parenthesis, i, comma, j, right parenthesis está en el grafo. Si quieres indicar un peso de la arista, ponlo en la entrada del renglón iii, columna jjj y reserva un valor especial (tal vez null) para indicar una arista ausente. *Listas de adyacencia Representar un grafo con listas de adyacencia combina las matrices de adyacencia con las listas de aristas. Para cada vértice iii, almacena un arreglo de los vértices adyacentes a él. Típicamente tenemos un arreglo de |V|∣V∣vertical bar, V, vertical bar listas de adyacencia, una lista de adyacencia por vértice.

Página 5|7

Operaciones Básicas En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas. Insertar vértice La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más, inicialmente aislado, ya que ninguna arista llegará a él. Insertar arista Esta operación es también muy sencilla. Cuando se inserte una nueva arista en el grafo, habrá que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino. Eliminar vértice Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la eliminación de la tabla de vértices del vértice en sí. A continuación, habrá que eliminar las aristas que tuviesen al vértice borrado como origen o destino. Eliminar arista Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.

Página 6|7

Referencias

Mary E. (2015). Estructura de Datos. Marzo 2020, de Blogspot. Recuperado de: http://estructuradedatos10111248.blogspot.com/2015/07/estructuras-lineales-y-no-lineales.html

Rodríguez L. (2012). Fundamentos de Programación II. Universidad Pontificia de Salamanca (campus Madrid): Escuela Superior de Ingeniería y Arquitectura.

Sin autor. Unidad IV: Estructuras no lineales. Marzo 2020, de Itpn. Recuperado de: http://itpn.mx/recursosisc/3semestre/estructuradedatos/Unidad%20IV.pdf

Balkcom D. & Corman T. (2017). Representar Grafos. Marzo2020, de Khanacademy. Recuperado de: https://es.khanacademy.org/computing/computer-science/algorithms/graphrepresentation/a/representing-graphs

Villanueva S. Operaciones básicas de los grafos. Marzo 2020, de DSTool. Recuperado de: http://www.hci.uniovi.es/Products/DSTool/grafos/grafos-operaciones.html

Página 7|7...