UNIDAD 5 APUNTADORES

UNIDAD 4 RECURSIVIDAD

UNIDAD 3

Tarea 3

Graficas

.- Resumen del capítulo 7 Graficas del libro Estructura de Datos de Osvaldo Cairo y Silvia Guardati

 Las gráficas son estructuras de datos no lineales en donde cada componente puede tener uno o más predecesores y sucesores. En una gráfica se distinguen dos elementos: los nodos, mejor conocidos como vértices y los arcos, llamados aristas, que conectan un vértice a otro. Los vértices almacenan información y las aristas representan relaciones entre dicha información.

Definición de graficas

Una gráfica G consta de dos conjuntos: V (G) y A (G). El primero lo integran elementos llamados nodos o vértices, el segundo arcos o aristas. Por lo cual podemos representar una gráfica G de la siguiente manera.

                                   

Conceptos básicos de gráficas

·         Grado de un vértice: se escribe como grado (V), consta del número de aristas que conforman el vértice.  Si v =0 representa que no tiene aristas y se define como nodo aislado

·         Lazo o bucle: Es la arista que conecta consigo mismo a V. se define como a= (u, u).

·         Camino: representado por P de longitud n se define como la secuencia de n vértices que se debe seguir para llegar al vértice V1 –origen- al vértice n –destino-.

·         Camino cerrado:  P es cerrado si el primero y el ultimo vértices son iguales

·         Camino simple:  cuando todos sus nodos son distintos, con excepción del primero y el ultimo, que pueden ser iguales

·         Ciclo: es un camino simple cerrado de longitud 3 o mayor. Un ciclo de longitud k se llama k-ciclo

·         Gráfica conexa: cuando existe un camino entre cualesquiera dos de sus nodos

·         Gráfica árbol: es una gráfica conexa sin ciclos

·         Gráfica completa: si cada vértice v de G es adyacente a todos los demás V de G.

·         Gráfica Etiquetada: cuando sus aristas tienen asignado un valor, es decir, cada arista a tiene un valor numérico no negativo c(a), llamado costo, peso o longitud de a, entonces G tiene peso o esta etiquetado.

·         Multigráfica: cuando al menos dos de sus vértices están conectados entre sí por medio de dos aristas. Estas aristas también se conocen por aristas múltiples o paralelas.

·         Subgráfica: se denomina Subgráfica de G, donde cada arista de A´ es incidente de V´

Las gráficas dirigidas se caracterizan porque sus aristas tienen asociada una dirección: es decir, son pares ordenados. Los vértices se utilizan para representar información, mientras que las aristas representan una relación con dirección o jerarquía entre aquellos.

Una gráfica dirigida G, también llamada digráfica se caracteriza porque cada arista a tiene una dirección asignada; es decir, cada arista está asociada a un par ordenado (u.v) de vértices G.

Representación de gráficas dirigidas

Las digráficas son estructura de datos abstractas. Para su representación se requiere usar otras estructuras de datos. Para la elección de la más adecuada depende del uso que se le vaya  a dar a la información almacenada en los vértices y en las aristas. Las representaciones más usadas para este tipo de gráficas son las matrices y las listas de adyacencia.

Matriz de adyacencia: es una matriz booleana de orden n, donde n indica el número de vértices de G. los renglones y columnas de la matriz representan a los vértices y su contenido a no de arcos entre ellos.

Lista de adyacencia

Es una lista ordenada de todos los vértices adyacentes de a. Por lo cual esta lista puede representar una gráfica dirigida, estará formada por tantas listas como vértices tenga G. Para que puedan guardarse los vértices de G se puede utilizar otra lista o un arreglo.

Obtención de caminos dentro de una digráfica

Buscamos en una estructura de datos el ajuste a las características especiales a nuestros problemas, se busca también que sobre dicha estructura se puedan realizar operaciones que faciliten el manejo de la información almacenada en ella. Los algoritmos más usados para este fin son: Dijkstra, Floyd y Warshall. Los tres algoritmos utilizan una matriz de adyacencia etiquetada donde:  

                M [i, j]= 0 Si i=j

                M [i, j]= ∞ si no existe un camino de i a j, donde i ≠ j

                M [i, j]=  costo de ir del vértice i al vértice j, si existe a (i, j).

Algoritmo Dijkstra

Encuentra el camino más corto de un vértice elegido a cualquier otro vértice de la digráfica, donde la longitud de un camino es la suma de los pesos de las aristas que lo forman. Las aristas deben poseer un valor de peso no negativo

Los siguientes pasos deben considerarse cuando se desea aplicar un algoritmo Dijkstra:

S es un arreglo formado por los vértices de los cuales ya se conocen la distancia mínima entre ellos y el origen. Esto se almacena al nodo origen

D es un arreglo formado por la distancia del vértice origen a cada uno d los otros. Es decir D almacena la menor distancia, o costo, entre el origen y el vértice. A este camino se le conoce como especial.

M es una matriz de distancias de n x n elementos, tal que M [i, j] almacena la distancia o costo entre los vértices i y j, si entre ambos existe una arista, en caso contrario M [i, j] será un valor muy grande (∞).

Algoritmo de Floyd

Encuentra el camino más corto entre todos los vértices de la digráfica. El algoritmo de Floyd permitirá encontrar el camino más corto entre cada par ordenado u y v.

La matriz de distancia sirve como punto de partida para este algoritmo. Se realizan k iteraciones sobre la matriz buscando el camino más corto; por lo tanto, en la k-ésima iteración, M [I, J] tendra el camino de menor costo para llegar de i a j, pasando por un numero de vértices menor de k, el cual se calculará según la siguiente forma:

Algoritmo de Warshall

Esta estructura encuentra, solo si es posible, un camino entre cada uno de los vértices de la gráfica dirigida, esto es, que la solución encontrada no presenta la distancia entre los vértices, solo te mostrara si hay caminos o no entre ellos.

Se  basa en un concepto de cerradura transitiva de la matriz de adyacencia. Sea la gráfica dirigida G (V, A) y su matriz de adyacencia M donde M [i, j]=1 si hay un arco de i a j y 0 si no lo hay. La cerradura transitiva de M es la matriz de C. Para generar la matriz de C se establece que existe un camino del vértice i a j que no pasa por un número de vértices mayor que k si:

·         ya existe un camino de  i a j que no pasa por un número de vértices mayor que -1.

·         Hay un camino de i a k  que no pasa por un numero de vértices mayor que k-1

Hay un camino de k a j que no pasa por un número de vértices mayor que k-1

Ejemplo:

Gráficas no Dirigidas

La característica principal es que sus aristas son pares no ordenados de vértices, es decir, que si existe un camino del vértice i a la j, será exactamente el mismo camino del vértice j a i.

Estas gráficas se utilizan para poder modelar relaciones simétricas entre objetos diferentes, que son representados por medio de los vértices, mientras que las aristas se utilizan para indicar la relación existente entre ellos.

Ejemplo:

Construcción del árbol abarcador del costo mínimo

Este tipo de árbol se define como un árbol libre que conecta todos los vértices de V. El costo del árbol abarcador resulta de la suma de las aristas incluidas en el. Por lo que, un árbol abarcador de costo mínimo de forma a partir de las aristas de menor costo. Este tipo de arboles posee una propiedad que sirve como base para todos los algoritmos utilizados para su construcción.

Algoritmos de Prim

Permite encontrar el árbol abarcador de costo mínimo en una gráfica. Para que esto pueda llevarse a cabo, se utilizan dos conjuntos de V, conjunto de todos los vértices, y U conjunto auxiliar iniciado con el primer vértice.

Antes de representar algún algoritmo, resulta conveniente explicar los elementos que se usarán en él:

·         V es el conjunto de vértices de G: V (1,2,……n). se usan los números enteros de 1 en adelante para identificar los vértices.

·         U es un subconjunto propio del conjunto V, siendo su valor inicial el del primer vértice.

Para muestra de implementación: U= {1}

·         L es una lista de aristas que se va formando con las aristas de menor costo que se van seleccionando. Inicialmente L está vacía L=Ø

               

Algoritmo de Kruskal

Este algoritmo es igual al Prim, permiten encontrar el árbol abarcador de menor costo de una gráfica. La construcción de un árbol abarcador mínimo  se lleva a cabo llevando la arista de menor costo y agregándola al árbol abarcador.

Espacio-Estado.

Consiste en la selección de una forma de representar los estados de un determinado problema. Las estructuras de datos que se utilizan mayormente para describir los estados son: arreglos unidimensionales, arreglos bidimensionales, listas ligadas, árboles y gráficas.

En el planteamiento del problema en espacio-estado, una solución se obtiene mediante la aplicación de operadores desde el estado inicial hasta alcanzar el estado final o meta.

Métodos de búsqueda en espacio-estado

Los métodos de búsqueda se caracterizan por el orden en que se expanden sus nodos: los dos básicos muy conocidos son:

Breadth-first o búsqueda de lo ancho: se expanden los nodos por el orden en que han sido generados

Depth-first

 o búsqueda en la profundidad: se expanden los nodos que han sido generados recientemente.

Estos métodos de búsqueda elementales son para encontrar las trayectorias, pero son exhaustivos porque expanden demasiados nodos.

  

UNIDAD 3 Tarea 2

ARBOLES

.- RESUMEN DEL TEMA ARBOLES DEL LIBRO ESTRUCTURA DE DATOS AUTOR OSVALDO CAIRO Y SILVIA GUARDATI

Los árboles son las estructuras no lineales y dinámicas de datos. Se dicen dinámicas porque pueden cambiar de tamaño o de forma durante la ejecución de un programa. A su vez no lineales porque cada elemento del árbol puede tener más de un sucesor.

Los árboles balanceados o AVL son la estructura de datos más eficiente para poder trabajar con la memoria principal del procesador

Estructuras Estáticas	Estructuras Dinámicas
Arreglos	Listas
Registros	Árboles
	Gráficas

Estructuras de datos clasificas de acuerdo con su capacidad para cambiar de forma y tamaño.

Estructuras Linéales	Estructuras No Linéales
Arreglos	Árboles
Registros Pilas Colas Listas	Gráficas

Principales estructuras de datos clasificadas según la distribución de sus elementos.

 

Árboles en General

Un árbol puede definirse como una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, uno de los cuales es conocido como ramificaciones.

Formalmente se define como un árbol de tipo T como una estructura homogénea resultado de una concatenación de un elemento de tipo T con un número finito de árboles disjuntos, llamados subárboles. Los árboles son estructuras recursivas porque cada subárbol es a su vez un árbol.

Un árbol puede representarse en  diferentes formas y todas ellas se consideran equivalentes.

Características y propiedades de los árboles

·         Todo árbol que no es vacío tiene un único nodo raíz

·         Un nodo X es descendiente de un nodo Y,  y si el nodo X, es apuntado por el nodo Y, entonces se utiliza el termino X es hijo de Y.

·         Un nodo X es antecesor directo de un nodo Y, y si el nodo X apunta al nodo Y, se utiliza la expresión, el nodo X es padre de Y.

·         Se dice que todos los nodos que son descendientes directos –hijos- de un mismo nodo –padre- son hermanos

·         Todo nodo que no tiene ramificaciones –hijos- se conoce como terminal y hoja.

·         Todo nodo que no es raíz ni terminal u hoja se conoce como interior

·         Grado es el número de descendientes directos de un determinado nodo

·         Grado del Árbol es el máximo grado de todos los nodos del árbol

·         Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo

·         Altura del árbol es el máximo número de todos los nodos de un árbol

Longitud de Camino externo e interno

Esto se define como la longitud que debe caminar el nodo X en los arcos que deben recorrer para que lleguen de la raíz al nodo X

Ejemplo

El nodo B tiene de camino de longitud 2, el nodo I tiene de camino de longitud 4 y  el nodo H un camino de longitud 3.

Longitud de camino Interno

Es la suma de las longitudes de camino de todos los nodos del árbol. Esto es importante ya que permite conocer los caminos que contiene el árbol. Se calcula de la siguiente forma:

                      

Longitud de camino Externo

Para poder comprender este concepto necesitamos definir antes que es un árbol extendido y un nodo especial.

Árbol extendido: aquel en el que el número de hijos de cada nodo es igual al grado del árbol

Nodos Especiales: tiene como objetivo reemplazar las ramas vacías o nulas y poseen forma de un cuadrado.

Ahora sabiendo esto podemos definir la LCE de un árbol como la suma de caminos de todos los nodos especiales del árbol. Se calcula de la forma en que se muestra a continuación:

Árboles Binarios

En un árbol binario solo podemos colocar como máximo dos subárboles y estos se distinguen a su vez como subárbol izquierdo y subárbol derecho, según estén ubicados respecto al nodo raíz.

Se define como un árbol binario de tipo T, como una estructura homogénea, resultado de la concatenación de un elemento de tipo T, llamado raíz con dos árboles binarios disjuntos, llamados subárbol izquierdo y subárbol derecho.

Ejemplo

Se representa (A*B)+(C/D)ᶺ3.5  que se define como la multiplicación de A y B, más la división entre Cy D a la potencia 3.5

Árboles binarios distintos, similares y equivalentes

Distintos: cuando la estructura es distinta

Similares: cuando sus estructuras son identicas, pero la información que contienen sus nodos difiere entre si.

Equivalentes: son similares y ademas contienen la misma información

Ejemplo:

Árboles Binarios Completos

Es aquel en el que todos sus nodos excepto los del último nivel, contienen dos hijos el subárbol derecho e izquierdo

Representación de un bosque como un árbol binario

Un bosque representa un conjunto ordenado de uno o más árboles generales.

A continuación se muestra el esquema de un bosque de árboles generales:

1

2

3

 

A continuación se muestra como convertir este bosque de árbol general en un árbol binario de acuerdo a los siguientes pasos:

1.       Enlazar de forma horizontal las raíces de los distintos árboles generales

2.       Relacionar los hijos de cada nodo en forma horizontal

3.       Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Debe eliminarse el vínculo padre e hijos

4.       Rotar el diagrama resultante aproximadamente 45º a la izquierda y así se obtendrá el árbol binario correspondiente

4

3

2

1

Representación de árboles binarios en memoria

Las formas más comunes de representar un árbol binario en memoria son:

·         Por medio de datos tipo punteros, también conocidas como variables dinámicas

·         Por medio de arreglos

Los nodos de árbol binario se representan como registros, en donde cada uno de ellos contiene como mínimo tres campos. En un campo se almacenara la información del nodo.

Los campos restantes se utilizaran para indicar cuál es el subárbol izquierdo y derecho, respecto al nodo en cuestión (en este caso el campo que almacenara la información). +

Representación:

T: equivale al nodo en cuestión.

IZQ: es el campo en donde se almacena la dirección del subárbol izquierdo del nodo T

INF: es el campo donde se almacenara la información del nodo

DER: es el campo donde se almacena la dirección del subárbol derecho del nodo T

Definición en lenguaje algorítmico:

ENLACE=ᶺNODO

NODO= REGISTRO

IZQ: tipo ENLACE

INF: tipo de dato

DER: tipo ENLACE

(Fin de la definición)

Operación en árboles binarios

Una de las operaciones básicas de un árbol binario es la creación del mismo en memoria

Una de las operaciones más importantes son el recorrido de los mismos, esto significa que pueden visitarse los nodos pero en forma ordenada, de tal manera que los nodos del mismo puedan visitarse una vez.

Tres formas para realizar el recorrido (forma recursiva).

·         Recorrido en Preorden

o   Visitar la Raíz

o   Recorrer el subárbol izquierdo

o   Recorrer el subárbol derecho

·         Recorrido en Inorden

o   Recorrer el subárbol izquierdo

o   Visitar la Raíz

o   Recorrer el subárbol derecho

·         Recorrido en Posorden

o   Recorrer el subárbol izquierdo

o   Recorrer el subárbol derecho

o   Visitar la Raíz

Árboles binarios de Búsqueda

Para todo nodo T del árbol se debe cumplir que todos los valores almacenados en el subárbol izquierdo sean menores o iguales a la información guardada en el noto T, ahora bien, en el subárbol derecho los valores almacenados deben ser mayores o iguales a la información guardada en el nodo T.

En este tipo de estructura de árboles binarios de búsqueda pueden realizarse eficientemente las operaciones de búsqueda, inserción y eliminación

Ejemplo

Árboles Balanceados

Con el objetivo de mantener la eficiencia de una búsqueda, surgen los árboles balanceados o también conocidos como AVL (en honor a sus creadores). Lo que les caracteriza es que realizan reacomodos o balanceos, después de inserciones o eliminaciones de elementos.

Un árbol balanceado se define como un árbol binario de búsqueda, en la cual debe cumplirse la siguiente condición: Para todo nodo T del árbol la altura de los subárboles izquierdo y derecho no deben diferir en más de una unidad.

Reestructuración del árbol balanceado

Realizar una reestructuración de un árbol balanceado es muy sencillo, solo requiere de operaciones auxiliares que dificultan algunas partes del proceso. Primero debemos localizar el lugar donde hay que insertar el elemento. Luego calculamos el FE de los distintos nodos visitados, que obviamente dará 0, y regresamos por el mismo camino de búsqueda calculando de la misma forma el FE de los nodos que se están visitando. Cuando en alguno de los nodos se viola el criterio de equilibrio, es cuando se debe reestructurar el árbol. Este proceso finalizara cuando logremos llegar a la raíz del árbol o cuando hemos reestructurado el mismo.

Tipos de rotación para la reestructuración:

A continuación se muestran las formas de las rotaciones:

ROTACION II

ROTACION DD

ROTACION DI

ROTACION ID

Eliminación de árboles balanceados

Consiste en poder eliminar un nodo del árbol sin modificar los principios del cual se rige un árbol balanceado (la altura del subárbol izquierdo como del derecho no deben diferir en más de una unidad).

Pasos para llevar a cabo una eliminación

·         Si el elemento a eliminar es terminal u hoja, fácilmente se suprime.

·         Si el elemento a eliminar tiene un solo descendiente, solo se sustituye por el descendiente

·         Si el elemento a eliminar tiene los dos descendientes, se sustituirá por el nodo que se encuentre más a la izquierda en el subárbol derecho o a su vez por el nodo que se encuentre más a la derecha en el subárbol izquierdo

Para poder eliminar un nodo del árbol, primero debes localizar la posición que tiene en el árbol, y así eliminarlo con los pasos que ya mencionamos anteriormente y regresas por el camino de búsqueda calculando el FE de los nodos visitados. Si se ha modificado el equilibrio de uno de ellos, entonces se tendrá que reestructurar nuevamente. Este proceso finalizara cuando hayamos llegado a la raíz del árbol.

Ejemplo:

Árboles multicaminos

Existen diferentes técnicas para la organización de archivos indizados, sin embargo la organización en árboles-B.

Arboles-B

Es la generalización de los árboles balanceados, representan un método para poder almacenar y recuperar la información en medios externos. En este tipo de árboles, un grupo de nodos recibe el nombre de página. En la cual se almacena la información de un grupo de nodos y se identifican por medio de una clave o llave.

Ejemplo de un árbol-B de orden 2

Ejemplo:

Búsqueda en árboles-B

Se define como la generalización de un proceso de búsqueda en un árbol binario de búsqueda. Los pasos para localizar una clave X en un árbol-B son los siguientes. Utilizamos NIL para indicar que la página está vacía.

Inserción en arboles-B

Este proceso es sencillo, aunque requiere un trato especial ya que posee ciertas características propias de este árbol. Tiene un comportamiento típico, las hojas están en el mismo nivel y por tanto cualquier camino desde la raíz hasta alguna de las hojas tiene la misma longitud. Este tipo de árboles tiene un forma extraña de crecer, ya que crecen de abajo hacia arriba. Quiere decir que desde las hojas hacia la raíz.

Pasos para llevar a cabo una inserción.

1.       Localizar la página donde corresponde, e insertar la clave

2.       Si (m<2d) el número de elementos a la página es menor a 2d

Entonces

La clave se inserta en el lugar que le corresponde

Si no

La página afectada se divide en dos y se distribuye las m+1

Claves equitativamente entre las mismas. La clave de en medio sube a la 

página del antecesor

3.       Fin del condicional del paso 2

Eliminación de árboles-B

Es mucho más complicada que la inserción. Consiste en quitar una de las claves del árbol sin violar la condición de que en una página, a excepción de la raíz, no puede haber menos de d claves siendo m el orden del árbol.

Para realizar una eliminación deben seguirse los siguientes pasos:

La clase árbol

Tiene como atributos a la raíz de la estructura y como método a todas las operaciones analizadas, según sea el tipo de árbol que se represente.

El siguiente ejemplo tiene acceso a los miembros de un objeto de la clase árbol por medio de su notación de puntos, asumiendo que la variblae AROBJ es un objeto de la clase árbol previamente realizado.