Universidad Nacional de San Cristbal de HuamangaIS241-Estructura de datosSemana 13PRIMERA UNIDAD 3Competencias Estructurar datos en orden no jerrquico. Conocer la terminologa bsica relativa a grafos Analizar los recorridos dentro de un grafo. Contenido Grafos dirigidos y grafos no dirigidos - Operaciones sobre grafos - Algoritmos de recorrido

.Listas enlazadas

Mapa ConceptualLineales

Operaciones

Pilas

ESTRUCTURAS DINAMICAS LINE

Colas

Arboles

No lineales

Grafos

VISTA OPERACIONAL DE LA ESTRUCTURA GRAFO

GrafosDetermina De vrticesConjunto Por aristasLista de adyacenciaRepresentaMatriz de adyacencia CaminosEconmicoCorto

1. GrafosLos grafos son estructuras de datos, representan relaciones entre objetos y son relaciones arbitrarias, es decir, no jerrquicas.Son aplicables en la qumica, geografa, ingeniera elctrica e industrial, modelo de redes, etc.Un grafo G = (V,A) V, el conjunto de vrtices o nodos (representa objetos)A, el conjunto de arcos (representan las relaciones)

ABEDC

V = {A, B, C, D, E} A= {(A,B), (B,C), (C,D), (D,E), (E,A), (A,E), (E,D), (D,C), (C,B), (B,A)}

2. TIPOS DE GRAFOSa. Grafos no dirigidos Si los pares de nodos que forman arcos son ordenados. Ejem plo.: (u->v)Un grafo es un multgrafo que tiene a lo sumo una rama entre dos vrtices y no tiene rulos. Los conceptos de camino, ciclo euleriano, conexo y grado coinciden con los ms arriba definidos. Adems decimos que un camino o ciclo es hamiltoniano si pasa por todos los vrtices una y solo una vez.. Si un par de puntos tiene una rama que los une decimos que son adyacentes,

Un grafo G lo representamos mediante (V,A) donde V es el conjunto de vrtices y A=VxV es el conjunto de ramas. Si un grafo tiene V =n vrtices el mximo numero de ramas es A . As, un grafo con 4 vrtices tiene a la sumo 6 ramas. Al grafo que tiene 4 vrtices y 6 ramas lo designamos con K4. La figura 1 muestra una representacin de K4 (izquierda).

Figura1K4 K4 (2,3)K4 {1} 1234

b. Grafos dirigidosUn grafo dirigido es un conjunto de vrtices tambin llamados nodos V y un subconjunto E de pares de vrtices de V llamados arcos donde el par se considerada dirigido, es decir, si AV y BV entonces (A,B) y (B,A) son arcos distintos. Si (A,B) es un arco entonces llamamos a A la cola y a B la punta de (A,B), Si V = n entonces el maximo numero de arcos que el digrafo puede tener es n(n-1). Un camino dirigido en un grafo G dirigido es una sucesion de vertices tal que si xn y xn+1 son dos vertices sucesivos entonces (xn , xn+1) es arco del grafo. Un camino es una sucesion de vertices tal que si xn y xn+1 son vertices sucesivos entonces (xn , xn+1) o (xn+1 , xn ) pertenece a E. Un digrafo es fuertemente conexo si cualquier par de vertices se puede unir por un camino dirigidofigura 2: Un digrafo fuertemente conexo

3. Recorridos

INTRODUCCIONEl rbol es una estructura de datos dinmica no lineales y muy importante en la programacin. Los rboles se manipulan para organizar frmulas algebraicas, para crear objetos en orden de tal forma que las bsquedas sean muy eficientes y en aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado. Casi todos los sistemas operativos almacenan sus archivos en rboles o estructuras similares a rboles. Adems de las aplicaciones citadas, los rboles se utilizan en diseo de compiladores, procesado de texto y algoritmos de bsqueda.En este tema se estudiara a esta estructura en sus tres perspectivas, nivel lgico, nivel de implementacin y aplicacin.1. RBOLES GENERALES y TERMINOLOGA

1.1 Definiciones

Un rbol consta de un conjunto finito de elementos, llamados nodos y de un conjunto finito de lneas dirigidas, llamadas ramas, que conectan los nodos.

Un rbol es un conjunto de uno o ms nodos tales que:Hay un nodo diseado especialmente llamado raz.Los nodos restantes se dividen en n 0 conjuntos disjuntos, T1 ...Tn, tal que cada uno de estos conjuntos es un rbol. A T1 ...Tn se les denomina subrboles del raz.

Estructura no lineal jerrquica en la que cada elemento tiene un nico antecesor y puede tener varios sucesores. En donde existe un nico camino entre el primer nodo de la estructura y cualquier otro nodo.

Vista de un rbol

1.2 Definicin recursiva

El concepto de subrbol conduce a una definicin recursiva de un rbol. Un rbol es un conjunto de nodos que:1. Es vaco.2. O tiene un nodo determinado, llamado raz, del que jerrquicamente descienden cero o ms subrboles, que son tambin rboles.

1.3 Terminologa

a. El primer nodo de un rbol, normalmente dibujado en la posicin superior, se denomina raz del rbol.b. Las flechas que conectan un nodo con otro se llaman arcos o ramas.c. Los nodos terminales, esto es, nodos de los cuales no se deduce ningn nodo, se denominan hojas.d. Los nodos que no son hojas se denominan nodos internos.e. En un rbol donde una rama va de un nodo n1 a un nodo n2, se dice que n1 es el padre de n2 y que n2 es un hijo de n1.f. n1 se llama ascendiente de n2, si n1 es el padre de n2 o si n1 es el padre de un ascendiente de n2.g. n2 se llama descendiente de n1, si n1 es un ascendiente de n2h. Un camino de n1 a n2 es una secuencia de arcos contiguos que van de n1 a n2i. La longitud de un camino es el nmero de arcos que contiene o, de forma equivalente, el nmero de nodos del camino menos uno.j. El nivel de un nodo es la longitud del camino que lo conecta al nodo raz.k. La profundidad o altura de un rbol es la longitud del camino ms largo que conecta la raz a una hoja.l. Un subrbol de un rbol es un subconjunto de nodos del rbol, conectados por ramas del propio rbol, esto es, a su vez un rbol.Sea S un subrbol de un rbol A: si para cada nodo n de SA, SA contiene tambin todos los descendientes de n en A, SA se llama un subrbol completo de A.m. Un rbol est equilibrado cuando, dado un nmero mximo k de hijos de cada nodo yLa altura del rbol h, cada nodo de nivel k < h-1 tiene exactamente k hijos.El rbol est equilibrado perfectamente, si cada nodo de nivel lizquierdo. Si el valor del nodo raz es menor que el elemento que buscamos, continuaremos la bsqueda en el rbol derecho: Padre=nodo, nodo=nodo->derecho. Si nodo no es NULL, el elemento est en el rbol, por lo tanto salimos. Si Padre es NULL, el rbol estaba vaco, por lo tanto, el nuevo rbol slo contendr el nuevo elemento, que ser la raz del rbol. Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo rbol izquierdo de Padre. Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un nuevo rbol derecho de Padre.Este modo de actuar asegura que el rbol sigue siendo ABB.Borrar el elementoPara borrar un elemento tambin nos basamos en el algoritmo de bsqueda. Si el elemento no est en el rbol no lo podremos borrar. Si est, hay dos casos posibles:1. Se trata de un nodo hoja: en ese caso lo borraremos directamente.2. Se trata de un nodo rama: en ese caso no podemos eliminarlo, puesto que perderamos todos los elementos del rbol de que el nodo actual es padre. En su lugar buscamos el nodo ms a la izquierda del subrbol derecho, o el ms a la derecha del subrbol izquierdo e intercambiamos sus valores. A continuacin eliminamos el nodo hoja.Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raz actual. El valor inicial para ese puntero es NULL. Padre = NULL Si el rbol est vaco: el elemento no est en el rbol, por lo tanto salimos sin eliminar ningn elemento. (1)Si el valor del nodo raz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos: El nodo raz es un nodo hoja: Si 'Padre' es NULL, el nodo raz es el nico del rbol, por lo tanto el puntero al rbol debe ser NULL. Si raz es la rama derecha de 'Padre', hacemos que esa rama apunte a NULL. Si raz es la rama izquierda de 'Padre', hacemos que esa rama apunte a NULL. Eliminamos el nodo, y salimos. El nodo no es un nodo hoja: Buscamos el 'nodo' ms a la izquierda del rbol derecho de raz o el ms a la derecha del rbol izquierdo. Hay que tener en cuenta que puede que slo exista uno de esos rboles. Al mismo tiempo, actualizamos 'Padre' para que apunte al padre de 'nodo'. Intercambiamos los elementos de los nodos raz y 'nodo'. Borramos el nodo 'nodo'. Esto significa volver a(1), ya que puede suceder que 'nodo' no sea un nodo hoja. (Ver ejemplo 3) Si el valor del nodo raz es mayor que el elemento que buscamos, continuaremos la bsqueda en el rbol izquierdo. Si el valor del nodo raz es menor que el elemento que buscamos, continuaremos la bsqueda en el rbol derecho.Ejemplo 1 para Borrar una hojaEn el rbol de ejemplo, borrar el nodo 3.1. Localizamos el nodo a borrar, al tiempo que mantenemos un puntero a 'Padre'.2. Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL.3. Borramos el 'nodo'.

Elemplo 2 Borrar un nodo rama con el intercambio de un nodo hija

En el rbol de ejemplo, borrar el nodo 4.1. Localizamos el nodo a borrar ('raz').2. Buscamos el nodo ms a la derecha del rbol izquierdo de 'raz', en este caso el 3, al tiempo que mantenemos un puntero a 'Padre' a 'nodo'.3. Intercambiamos los elementos 3 y 4.4. Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL.5. Borramos el 'nodo'.

Ejemplo 3 borrar un nodo rama con intercambio de nodo ramaEn ste borraremos el elemento 6

1. Localizamos el nodo a borrar ('raz').2. Buscamos el nodo ms a la izquierda del rbol derecho de 'raz', en este caso el 12, ya que el rbol derecho no tiene nodos a su izquierda, si optamos por la rama izquierda, estaremos en un caso anlogo. Al mismo tiempo que mantenemos un puntero a 'Padre' a 'nodo'.3. Intercambiamos los elementos 6 y 12.4. Ahora tenemos que repetir el bucle para el nodo 6 de nuevo, ya que no podemos eliminarlo.

5. Localizamos de nuevo el nodo a borrar ('raz').6. Buscamos el nodo ms a la izquierda del rbol derecho de 'raz', en este caso el 16, al mismo tiempo que mantenemos un puntero a 'Padre' a 'nodo'.7. Intercambiamos los elementos 6 y 16.8. Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL.9. Borramos el 'nodo'.

21

+*ab*cd+

*xa-by-z+

*abc/d+

bdc++a/

+-b

a

c*d+*+xy1

A

FD2

3

4

5

6

G7

BCE4

A

FD2

1

3

6

5

G7

BCE7

A

FD3

1

2

6

4

G5

BCE