INSTITUTO TECNOLÓGICO SUPERIOR DE LA MONTAÑA

MATERIA: ESTRUCTURA DE DATOS

TEMA: RESUMEN
· ARBOLES , GRAFOS Y SUS APLICACIONES
DOCENTE: ING. FRANCISCO CASTRO HURTADO

ALUMNA: Primavera Moran Cortes

SEMESTRE: TERCERO

CARRERA: LIC. EN INFORMATICA

FECHA DE ENTREGA: 13 DE DICIEMBRE DE 2009



ARBOLES

INTRODUCCIÒN
Árbol. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos.

Primero profundizaremos en un tipo especial de árbol, llamado árbol binario, un árbol así puede parecer muy restrictivo, en este capítulo le mostraremos que los árboles más generales pueden ser vistos como árboles binarios.

ARBOLES BINARIOS
Un árbol binario T se define como un conjunto finito de elementos, llamados nodos, de forma que:

(a) T es vacio (en cuyo caso se llama árbol nulo o árbol vacio) o

(b) T contiene un nodo distinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntos T1 y T2.

Si T contiene una raíz R, los dos árboles T1 y T2 se llaman, respectivamente, subárbols izquierdo y derecho de la raíz R. Si T1 no es vacio, entonces su raíz se llama sucesor izquierdo de R; y análogamente, si T2 no es vacio, su raíz se llama sucesor derecho de R.

Un árbol binario T se representa frecuentemente en forma de diagrama. El diagrama siguiente representa un árbol binario T como sigue. (i) T con 11 nodos, por las letras de la A, a la L, excluyendo la I. (ii) la raíz del árbol T es el nodo de A, en la parte superior del diagrama. (iii) una línea hacia abajo y ala izquierda de N señala un sucesor izquierdo de N, y una línea hacia abajo y ala derecha de N señala un sucesor derecho de N. Observe que:

(a) B es un sucesor izquierdo y C un sucesor derecho del nodo A.

(b) El subárbol izquierdo de la raíz A consiste en los nodos B, D, E y F, y el subárbol derecho de A consiste en los nodos C, G, H, J, k y L.

Cualquier nodo N de un árbol binario T tiene 0,1 o 2 sucesores. Los nodos A, B, C y H tienen dos sucesores, los nodos R y J solo tienen un sucesor, y los nodos D, F, G, L y K no tienen sucesores. Los nodos sin sucesores se llaman nodos terminales.

La definición anterior del árbol binario T es recursiva, ya que T se define en términos de los subàrboles binarios T1 y T2. Esto significa, en particular, que cada nodo N de T contiene un subárbol izquierdo y uno derecho. Más aun, si N es un nodo terminal, ambos subárboles están vacios.

Dos árboles binarios T y T’ se dice que son similares si tienen la misma estructura o, en otras palabras, si tienen la misma forma. Los arboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.

Considere los 4 árboles binarios de la siguiente figura. Los 3 arboles (a), (c) y (d) son similares. Los arboles (a) y (c) son copias, ya que además tienen los mismos datos en los correspondientes nodos. El árbol (b) no es ni similar ni una copia del (d), ya que en un árbol binario distinguimos entre sucesor izquierdo y sucesor derecho incluso cuando solamente existe un sucesor.

EXPRESIONES ALGEBRAICAS

Considere una expresión algebraica E que contenga solo operaciones binarias, tal como

E=(a-b)/ ((C * d) + e)

E puede ser representada en términos del árbol binario T como la siguiente figura. Así cada variable o constante de E aparece como un nodo <> de T cuyos subárboles izquierdo y derecho corresponden a los operandos de la operación. Por ejemplo:

(a) En la expresión E, los operandos del + son c*d y e.

(b) En el árbol T, los subárboles del nodo + corresponden a las subexpresiones c*d y e.

Claramente una expresión algebraica se corresponderá con un único árbol y viceversa.

TERMINOLOGÌA

Frecuentemente se usa una terminología de relaciones familiares para describir las relaciones entre los nodos de un árbol T. En particular, suponga que N es un nodo de T con un sucesor izquierdo S1 y un sucesor derecho S2. Entonces N se llama el padre de S1 y S2 se dice que son hermanos. Cada nodo N de un árbol binario T, excepto la raíz, tiene un único padre, llamado predecesor de N.

Los términos descendientes y antecesores tienen su significado usual. Así, un nodo L se dice descendiente de un nodo N (y N se dice antecesor de L) si existe una sucesión de hijos desde N hasta L. En particular, L se dice descendiente izquierdo o derecho de N dependiendo que si pertenece al subárbol izquierdo o al derecho de N.

También se usa terminología de teoría de grafos y de horticultura para un árbol binario T. específicamente, la línea dibujada entre un nodo N de T y un sucesor cuyo se llama arista, y una secuencia de aristas consecutivas se denomina camino. Un nodo terminal se llama hoja y un camino que termina en una hoja se llama rama.

Cada nodo de un árbol binario T tiene asignado un número de nivel, de la forma que sigue. A la raíz R del árbol T se le asigna el numero de nivel 0, y al resto de los nodos se le asigna un numero de nivel que es mayor en 1 que el numero de nivel de su padre. Más aun, aquellos nodos con el mismo número de nivel se dice que pertenecen a la misma generación.

La profundidad (o altura) de un árbol T es el número máximo de nodos de una rama de T. equivale a 1 más que el mayor numero de nivel de T.

ARBOLES BINARIOS COMPLETOS

Considere un árbol binario T. Cada nodo de T puede tener como mucho dos hijos. De acuerdo con esto, se puede probar que el nivel r de T puede tener como mucho 2r nodos. El árbol T se dice que es completo si todos sus niveles, excepto posiblemente el ultimo, tiene el máximo número de nodos posibles y si todos los nodos del último nivel están situados lo más posible a la izquierda. Así, solo existe un único árbol completo Tn con exactamente n nodos (por su puesto, ignoramos los contenidos de los nodos).

En la siguiente figura aparece el árbol completo T26 de 26 nodos. Los nodos del árbol binario completo T26 han sido intencionadamente etiquetados con los enteros 1,2…, 26, de izquierda a derecha y de generación en generación. Con este etiquetado, se puede determinar fácilmente los hijos o el padre de cada nodo K de un árbol completo Tn Específicamente, los hijos izquierdo y derecho de un nodo K son, respectivamente, 2*K y 2*K + 1, y el padre de k es el nodo [k/2]. Por ejemplo, los hijos del nodo 9 son los nodos 18 y 19, y su padre es el nodo [9/2]=4. La profundidad DN del árbol completo Tn de n nodos viene dada por
DN=[Iog2 n + 1]
Se trata de un número relativamente pequeño. Por ejemplo, si el árbol completo Tn tiene n=1.000.000 de nodos, entonces su profundidad es DN=21.

Arboles binarios extendidos: arboles-2
Un árbol binario T se dice que es un árbol-2 o árbol binario extendido si cada nodo N tiene 0 o 2 hijos. En ese caso, los nodos con 2 hijos se denominan nodos internos y los nodos con 0 hijos se denominan nodos externos. A veces los nodos se distinguen en los diagramas mediante el uso de círculos para los nodos internos y de cuadrados para los nodos externos.

El termino <<árbol binario extendido>> viene de la siguiente operación. Considere un árbol binario T, como en la siguiente figura. Entonces T puede ser <> a un árbol-2 reemplazando cada subárbol vacio por un nuevo nodo, como se ve en la figura observe que el nuevo árbol es, realmente, un árbol-2.Mas aun, los nodos del árbol T original son ahora los nodos internos del árbol extendido, y los nuevos nodos son los nodos externos del árbol extendido.

Un ejemplo importante de árbol-2 es el árbol T correspondiente a una expresión algebraica E que usa solo operaciones binarias.

PRESENTACION DE ARBOLES BINARIOS EN MEMORIA

Sea T un árbol binario. Esta sección discute dos formas de representar T en memoria. La primera y más usual forma, llamada representación enlazada de T, es análoga a la forma en que se representan las listas enlazadas en memoria. La segunda forma, que usa un array simple, se llama representación secuencial de T. El principal requerimiento para cualquier representación de T es que se tenga acceso directo a la raíz R de T y, dado cualquier nodo N de T; se tenga acceso directo a los hijos de N.

REPRESENTACIÓN ENLAZADA DE ARBOLES BINARIOS

Considere el árbol binario T. A menos que se especifique lo contrario, T se mantendrá en memoria en términos de una representación enlazada que usa 3 arrays paralelos, INFO, IZQ y DER, y una variable puntero RAIZ tal como sigue. En primer lugar, cada nodo N de T corresponderá a una posición K, tal que:

(1) INFO [K] contendrá los datos del nodo N.

(2) IZQ[K] contendrá la localización del hijo izquierdo del nodo N.

(3) DER[K] contendrá la localización del hijo derecho del nodo N.

Más aun, RAÍZ contendrá la posición de la raíz R de T. Si algún subárbol esta vacio, entonces el correspondiente puntero contendrá el valor nulo; si el árbol mismo T esta vacio, entonces RAIZ contendrá el valor nulo.

Nota 1: la mayoría de nuestros ejemplos mostraran un solo elemento de información en cada nodo N de un árbol binario T. En la práctica, en el nodo N se puede guardar un registro entero. En otras palabras, INFO puede ser realmente un arrays lineal de registros o una colección de arrays paralelos.

Nota 2: como los nodos pueden insertarse o borrarse en los arboles binarios, asumiremos implícitamente que las localizaciones vacías de los arrays INFO, IZQ, DER forman una lista enlazada con un puntero, DISP, normalmente dejaremos que sea el array IZQ el contenga los punteros de la lista DISP.

Nota 3: cualquier dirección inválida se puede elegir para el puntero nulo denotado por NULO. En la práctica, se usa el 0 o un numero negativo para el puntero NULO.

REPRESENTACION SECUENCIAL DE ARBOLES BINARIOS

Suponga que T es un árbol binario que es completo o casi completo. Entonces existe una forma eficiente de mantener T en memoria llamada representación secuencial de T. Esta representación usa únicamente un array lineal ARBOL de la forma siguiente:

(a) La raíz R de T se guarda en ÁRBOL[1].

(b) Si un nodo N esta en ÁRBOL[K], entonces su hijo izquierdo esta en ARBOL[2*K] y su hijo derecho en ARBOL[2*K+1].



De nuevo, se usa NULO para indicar un subárbol vacio. En particular, ÁRBOL[1]=NULO indica que el árbol esta vacio.


RECORRIDO DE ARBOLES BINARIOS

Existen tres modos estándar de recorrer un árbol binario T de raíz R. Estos tres algoritmos, denominados preorden, inorden y postorden, son así:

Preorden: (1) Procesar la raíz R.

(2) Recorrer el subárbol izquierdo de R en preorden

(3) Recorrer el subárbol derecho de R en preorden.

Inorden: (1) recorrer el subárbol izquierdo de R en inorden.

(2) procesar la raíz R.

(3) Recorrer el subárbol derecho de R en inorden.

Postorden: (1) Recorrer el subárbol izquierdo de R en postorden.

(2) Recorrer el subárbol derecho de R en postorden.

(3)Procesar la raíz R.

Observe que cada algoritmo contiene los mismos 3 pasos y que el subárbol izquierdo de R siempre se recorre antes que el subárbol derecho. La diferencia entre los algoritmos es el momento en que se procesa la raíz R. Específicamente, en el algoritmo <

>, la raíz R se procesa antes de recorrer los subárboles; en el algoritmo <>, la raíz R se procesa entre los dos recorridos de los subárboles; y en el algoritmo <>, la raíz se procesa tras recorrer los subárboles.



Los tres algoritmos se denominan a veces, respectivamente, recorrido nodo-izquierdo-derecho (NLR,), recorrido izquierdo-nodo-derecho (LNR) y recorrido izquierda-derecha-nodo (LRN).



Observe que cada uno de los algoritmos de recorrido anteriores está definido recursivamente, ya que involucran el recorrido de los subárboles en el orden dado.



En la siguiente figura observamos que A es la raíz, que su subárbol izquierdo LT consiste en lo nodos B, D y E y que su subárbol derecho RT consiste en los nodos C y F.



(a) El recorrido preorden de T procesa A, recorre LT y recorre RT .Entonces el recorrido preorden de LT procesa la raíz B y luego D y E y el recorrido preorden de RT procesa la raíz C y luego F. Así, el recorrido preorden de T es ABDECF.



(b) El recorrido inorden de T recorre LT, procesa A y recorre RT, entonces el recorrido inorden de LT procesa D, B y luego E, y el recorrido inorden de RT procesa C y luego F. así, DBACF, es el recorrido inorden de T.



(c) El recorrido postorden de T recorre LT, recorre RT y procesa A. entonces, el recorrido postorden de LT procesa D, E y luego B, y el recorrido postorden de RT precisa F y luego C. de acuerdo con esto el recorrido postorden de T es DEBFCA.



ALGORITMOS DE RECORRIDOS USANDO PILAS.



Suponga un árbol binario T manteniendo en memoria por una representación enlazada.



ÁRBOL(INFO, IZQ, DER, RAIZ)



Esa sección discute la implementación de los tres recorridos estándar de T, definidos recursivamente en la última sección, mediante procedimientos no recursivos que usan pilas.



RECORRIDO PRE ORDEN



El algoritmo de recorrido pre orden usa una variable PTR (puntero) que contendrá la posición del nodo N que se esté examinando. En la siguiente figura donde L(N) denota al hijo izquierdo del nodo N y R(N) denota al hijo derecho. El algoritmo también usa un array PILA, que obtendrá las direcciones de los nodos que allana de ser procesados.



RECORRIDO INORDEN



El algoritmo de recorrido inorden también usa una variable puntero PTR, que contenderá la posición del nodo N que se esté examinando, y un array PILA, que mantendrá las direcciones de los nodos que quedan por procesar, de hecho, en este algoritmo, un nodo D solo se procesa cuando se saca de la PILA.



RECORRIDO POSTORDEN



El algoritmo de recorrido postorden es más complicado que los dos algoritmos anteriores, ya que aquí tenemos que salvare el nodo N en dos situaciones distintas. Distingamos entre los dos casos metiendo en PILA N o su negativo, -N. (en realidad, la posición de N es lo que se mete en PILA, de forma que –N tiene un significado obvio. De nuevo se usa una variable PTR(puntero) que ha de contener la posición del nodo N que se esté examinando.



NODOS CABECERA; ARBOLES ENHEBRADOS



NODOS CABECERA

Suponga un árbol binario T dispuesto en memoria por representación enlazada. A veces se añade al principio de T un nodo extra, especial, llamado nodo cabecera.



Cundo se usa este nodo extra, la variable el árbol, que llamaremos CABEZA (en lugar de raíz), apuntara al nodo de cabecera, y el puntero izquierdo del nodo cabecera apuntara a la raíz de T.



Suponga un árbol binario T vacio. T aun contendrá al nodo cabecera, pero su puntero izquierdo contendrá el valor nulo. Así, la condición



IZQ [CABEZA]=NULO



Indicara que el árbol esta vacio.



Otra variación de la representación anterior de un árbol binario T es usar un nodo cabecera como centinela. Esto es, si un nodo tiene un subárbol vacio, entonces el campo puntero para el subárbol contendrá la dirección del nodo cabecera en vez del valor nulo. De esta forma, ningún puntero contendrá una dirección inválida, y la condición.



IZQ [CABEZA]=CABEZA



Indicara que el árbol esta vacio.





HEBRAS; ENHEBRADO INORDEN



Considere de nuevo la representación enlazada de un árbol binario T. aproximadamente la mitad de las entradas de los campos del puntero IZQ y DER contendrán valores nulos. Este espacio se puede aprovechar más eficientemente reemplazado las entradas nulas por algún otro tipo de información. Específicamente, reemplazaremos ciertas entradas nulas con punteros especiales que apuntaran a nodos superiores del árbol. Estos punteros especiales se llaman hebras, y los arboles binarios con ese tipo de punteros se llaman arboles enhebrados.



Las hebras en un árbol enhebrado se deben distinguir de alguna forma de los punteros normales. Las hebras en los diagramas de un árbol enhebrado se indican normalmente con líneas discontinuas. En la memoria de la computadora se puede usar un campo extra indicador de un bit para distinguir las hebras de los punteros ordinarios, o alternativamente, denotar las hebras por enteros negativos y los punteros normales por enteros positivos.



Existen muchas formas de enhebrar un árbol binario T, pero cada enhebrado corresponderá a un recorrido particular de T. además, se puede escoger un enhebrado unidireccional o bidireccional. A menos que se diga lo contrario, nuestro enhebrado corresponderá al recorrido inorden de T. Así, en el enhebrado unidireccional de T, las hebras también aparecerán en el campo derecho de los nodos y apuntaran al siguiente nodo en el recorrido inorden de T; y en el enhebrado bidireccional de T, las hebras también aparecerán en el campo izquierdo de los nodos apuntando al nodo precedente en el recorrido inorden de T. Además, en el puntero izquierdo del primer nodo y el puntero derecho del último (según recorrido inorden de T) contendrá el valor nulo cundo T no tenga nodo cabecera, pero apuntaran al nodo de cabecera, pero apuntaran al nodo de cabecera de T si existe.



ARBOLES BINARIOS DE BUSQUEDA



Esta estructura permite buscar y encontrar un elemento con una media de tiempo de ejecución (n)=0(log2n). También permite insertar y borrar elementos fácilmente. Esta estructura contrasta con las siguientes estructuras:



a) Array lineal ordenado. Aquí se puede buscar y encontrar un elemento con un tiempo de ejecución (n)=0(log2n), pero es costoso el insertar y borrar elementos.



b) Lista enlazada. Aquí se puede insertar y borrar elementos fácilmente, pero es costoso el buscar y encontrar un elemento, ya que se debe usar una búsqueda secuencial.



Aunque cada nodo de un árbol binario de búsqueda puede contener un registro entero de datos.



T se dice que es un árbol binario de búsqueda (o árbol binario ordenado) si cada nodo N de T tiene la siguiente propiedad: el valor de N es mayor que cualquier valor del subárbol izquierdo de N y es menor de cualquier valor del subárbol derecho de N.



La definición de un árbol binario de búsqueda asume que todos los valores de los nodos son distintos. Existe una definición análoga de árbol binario de búsqueda que permite duplicaciones, esto es, en la que cada nodo N tiene la siguiente propiedad: el valor de N es mayor que cualquier subárbol izquierdo N y es menor o igual que cualquier valor del subárbol derecho de N.



BÚSQUEDA E INSERCIÓN EN ÁRBOLES BINARIOS DE BÚSQUEDA



El recorrido de T es el mismo recorrido de un árbol binario.



El siguiente algoritmo encuentra la posición de ITEM en el árbol binario de búsqueda T o inserta ITEM en el árbol binario de búsqueda T o inserta ITEM como un nuevo nodo en su sitio apropiado en el árbol.



(a) Comparar ITEM con el nodo raíz N del árbol.



(i) Si ITEM N, proceder con el hijo derecho de N.



(b) Repetir el paso (a) hasta que se dé una de las siguientes condiciones:



(i) Se encuentra un nodo N tal que ITEM=N. En este caso se ha completado la búsqueda.



(ii) Se encuentra un subárbol vacio, lo que indica que la búsqueda ha sido infructuosa, y se inserta ITEM en el lugar del subárbol vacio.



En otras palabras, se procede hacia abajo desde la raíz R por el árbol T hasta que se encuentra ITEM en T o hasta insertar ITEM como un nodo terminal de T.

COMPLEJIDAD DEL ALGORITMO DE BÚSQUEDA



Suponga que buscamos un elemento de información en un árbol de búsqueda binaria T. Nos dan n datos, A1, A2,…, AN, y suponga que esos elementos se insertan por orden en un árbol binario de búsqueda T. Cada permutación dará lugar a un árbol correspondiente. Se puede probar que la profundidad media de los n! arboles es aproximadamente c log2 15n, donde c=1.4. De este modo, el tiempo de ejecución medio f(n) para la búsqueda de un elemento de un árbol binario T con n elementos es proporcional al log2 n, o sea, f(n)=0(log2 n).



APLICACIÓN DE LOS ARBOLES DE BUSQUEDA BINARIA



Suponga que queremos encontrar y borrar todos los duplicados del conjunto. Una forma directa de hacerlo es la siguiente:



Algoritmo A: Examinar los elementos desde A1 hasta AN (de izquierda a derecha).



(a) Para cada elemento Ak, compara Ak con A1, A2,…, Ak-1, comparar Ak con aquellos elementos que preceden a Ak.



(b) Si Ak se da en A1, A2,…,Ak-1, entonces borrar Ak



Tras haber examinado todos los elementos, no habrá duplicados.



Algoritmo B: Construir un árbol de búsqueda binaria T usando los elementos A1, A2,…, AN. Al construir el árbol, borrar Ak ya aparezca en el árbol.



La principal ventaja del algoritmo B es que cada elemento Ak se compara solo con los elementos de una rama del árbol. Se puede demostrar que la longitud media de esa rama es aproximadamente c log k, donde c=1.4. Así, el número total f(n) de comparaciones requeridas por el algoritmo B es aproximadamente n log2 n, o sea, f(n)=0(n log2 n). Por ejemplo, para n comparaciones del algoritmo A.



ELIMINACION EN UN ARBOL DE BUSQUEDA BINARIA



El algoritmo de eliminación usa primero el procedimiento para encontrar la posición del nodo N que contiene a ITEM, así como la posición del nodo padre P(N). La forma en que N es eliminado del árbol depende principalmente del número de hijos de N. existen tres casos:



Caso 1. N no tiene hijos. Entonces N se elimina de T simplemente reemplazando la posición de N en P(N) por el puntero nulo.



Caso 2. N tiene exactamente un hijo. Entonces N se elimina de T simplemente reemplazando la posición de N en P(N) por la posición del hijo único de N.



Caso 3. N tiene dos hijos. Sea S(N) el sucesor inorden de N. [El lector puede verificar que S(N) no tiene hijo izquierdo.] Entonces N es eliminado de T primero eliminando S(N) de T (mediante los casos 1 o 2) y luego reemplazando N en T por el nodo S(n).



En los tres casos, el espacio de memoria del nodo N eliminado se devuelve a la lista DISP.



ARBOLES EN MONTON; ORDENACION POR MONTON



El árbol en montón se usa en un elegante algoritmo de ordenación llamado ordenación por montón.



Suponga que H es un árbol binario completo con n elementos. (A menos de que se indique lo contrario, asumiremos que H se tiene en memoria como un array lineal ARBOL mediante representación secuencial, no en representación enlazada.) Se dice que H es un árbol en montón, o montón máx., si cada nodo N de H tiene la siguiente propiedad: El valor de N es mayor o igual que el valor de cualquier hijo de N. (Un montón min se define análogamente: el valor de N es menor o igual que el valor de cualquier hijo de N.)



INSERCION EN UN ARBOL EN MONTON



Suponga que H es un montón con N elementos y suponga que se da un ITEM de información.



Insertamos ITEM en el montón H tal como sigue:



(1) Primero se añade ITEM al final de H, de forma que H siga siendo árbol completo, aunque no necesariamente un montón.



(2) Entonces se hace subir a ITEM hasta su “lugar apropiado” en H para que H sea finalmente un montón.



La forma en que funciona este procedimiento se ilustra a continuación antes de presentarlo formalmente.



La siguiente figura muestra el árbol final. La línea sombreada indica donde ha habido intercambios.







Suponga que queremos construir en motón H con la siguiente lista de números:

Se puede hacer insertando los ocho números tras otro en un árbol en motón H vacío mediante el anterior procedimiento. Las figuras 7-31(a) a (h) muestran los respectivos dibujos del montón tras insertar cada uno de los ocho elementos. De nuevo, las líneas punteadas indican que se ha dado un intercambio durante el proceso de inserción de ITEM dado de información.



ITEM no se asigna a ningún elemento del array ÁRBOL hasta que se encuentra su posición adecuada. El paso 7 se ocupa del caso especial de que ITEM llegue a la raíz ÁRBOL [1]. Suponga un array A con N elementos dados. Podemos construir un montón H sobre el array A aplicando repetidamente el procedimiento 7.9 a A o sea, ejecutado.



Llamar a INSMONTÓN(A, J, A[J+1])



Para j= 1, 2…., N-1.



ELIMINACIÓN DE LA RAIZ DE UN MONTON.



Suponga que H es un montón con n elementos y suponga que queremos eliminar la raíz R de H. esto se lleva a cabo como sigue:



(1) Asignar la raíz R a alguna variable ITEM.



(2) Reemplazar el nodo R a eliminar con el último nodo L de H de forma que H sigue siendo completo, aunque no necesariamente un montón.



(3) (Reamontonar). Hacer que L se mueva a su sitio adecuado en H para que H sea finalmente un montón.







De nuevo ilustraremos la forma en que trabaja el procedimiento entes de definirlo formalmente.



Ejemplo 7.22



Considere el motón H de la figura 7.32 (a), donde R = 95 es la raíz y L = 22 es el ultimo nodo del árbol. El paso 1 de este procedimiento eliminar R=95 y el paso 2 remplazar R = 95 por L = 22. Esto da el árbol completo de la fig. 7-32(b), que no es un montón. Observe sin embargo que tanto el subárbol izquierdo como el derecho de 22 son todavía montones, aplicando el paso 3 encontramos el lugar adecuado de 22 en el montón como sigue:



(A) compramos 22 con sus 2 hijos, 85 Y 70 como 22 es menor que el hijo mayor, 85, intercambiamos 22 y 85 de forma que el árbol aparece en la figura 7-32(c).



(B) comparamos 22 con sus 2 nuevos hijos 55 y 33. como 22 es menor que el mayor hijo, 55. intercambiamos 22 y 55 quedando el árbol como aparece en la figura7-32(d).



(C) comparamos 22 con sus nuevos hijos 15 y 20. como 22 es mayor que ambos, el que era el ultimo nodo, 22, ha llegado a su lugar adecuado en H.



El bucle del paso 4 se repite mientras que UTL tenga hijo derecho. El paso 8 se encarga del caso especial en que UTL no tenga hijo derecho, pero si hijo izquierdo (que ha de ser el ultimo nodo de H). La razón de que haya dos sentencias condicionales en el paso 8 es que ÁRBOL[IZQ] puede no estar definido cuando IZQ>N.



Aplicación en ordenación.



Suponga que un array A de N elementos dado. El algoritmo de ordenación por montón para ordenar A consiste en las dos siguientes fases.



Fase A: construir un árbol en montón H con los elementos de A.



Fase B: Eliminar repetidamente en elemento raíz de H.



Como la raíz de H siempre contiene el mayor elemento de H, la fase B elimina los elementos de A en orden descendente. A continuación se da una definición formal del



El propósito del paso 2(b) es ahorrar espacio. Así, se puede usar otro array B para mantener los elementos ordenados de A reemplazando el paso 2(b) por



Hacer B[N+1]: = ITEM



Sin embargo, el lector puede verificar que el paso 2(b) dado no interfiere con el algoritmo, ya que A[N+1] no pertenece al montón H.



COMPLEJIDAD DE LA ORDENACION POR MONTÓN



Suponga que el algoritmo de ordenación por montón se aplica a un array A con n elementos. El algoritmo tiene dos fases, así que analizaremos, la complejidad de cada fase por separado.



Fase A: suponga que H es un montón. Observe que el numero de comparaciones para encontrar el sitio adecuado para un nuevo elemento ITEM de H no puede exceder la profundidad de, como H es un árbol completo, su profundidad está limitada por log2 m, donde m es el número de elementos de H. de acuerdo con esto, el número total de comparaciones g(n) para insertar los n elementos de A en H está limitado por lo siguiente.



g(n)≤n log2 n.



Consecuentemente el tiempo de ejecución de la fase A de la ordenación por montón es proporcional a n log2 n.



Fase B: suponga que H es un árbol completo con m elementos y que los subárboles izquierdo y derecho de H son montones para moverle nodo L un paso abajo en el árbol H. como la profundidad de H no excede a log2 m, al reamontar se efectúan como mucho 4 log2 m comparaciones para encontrar el lugar, adecuado de L en el árbol H. esto significa que el número total h(n) de comparaciones para eliminar los n elementos de A en H, lo que requiere el reamontar n veces esta, está limitado por:



H(n)≤4n log2 n.



Así el tiempo de ejecución de, m la dase B de la ordenación por montón también es proporcional a n log2 n.



El tiempo de ejecución para ordenar el array A de n elementos con la ordenación por montón es proporcional a n log2 n, o sea ∫(n) = O(n log2 n), ya que cada fase requiere un tiempo proporcional a n log2 n. observe que esto da el peor caso en complejidad para el algoritmo. Esto contrasta con los 2 siguientes algoritmos de ordenación y estudiados.



(1) Ordenación por el método de la burbuja (secc 4.6). El tiempo de ejecución de esta ordenación es O(n2).



(2) Ordenación rápida (secc 6.5). El tiempo medio de ejecución de la ordenación rápida es O(N log2 n), lo mismo que la ordenación por montón, peor el tiempo de ejecución para el peor caso en la ordenación rápida en proporcional a O(n2), igual que por el método de la burbuja.



LONGITUD DE CAMONO; ALGORITMO DE HUFFMAN.



Recuerde que un árbol binario extendido o arbol-2 es un árbol binario T en el que cada nodo tiene 0 o 2 hijos. Los nodos con 0 hijos se llaman nodos externos y los nodos con 2 hijos se llaman nodos internos.



Frecuentemente, un algoritmo se puede representar por un arbol-2 T en el que los nodos internos representan test y los nodos externos representan acciones. Así, el tiempo de ejecución del algoritmo dependerá de las longitudes de los caminos den el árbol. Teniendo esto presente, definimos la longitud de camino extra LE dé un arbol-2 como la suma de todas las longitudes de camino obtenidas sobre cada camino desde la raíz R de T hasta un nodo externo. La longitud de camino interna LI de T se define analógicamente usando los nodos internos en vez de los externos.



ARBOLES GENERALES



Un árbol general (a veces llamado árbol) se define como un conjunto finito no vacio T de elementos, llamados nodos, tales que:



(1) T contiene un elemento distinguido R, llamado raíz de T.



(2) Los restantes elementos de T forman una colección ordenada de cero o más arboles disjuntos T1, T2,….Tm.



Los árboles T1, T2,…, Tm son llamados subárboles de la R, y las raíces de T1, T2,…, Tm se llaman sucesores de R.



La terminología de relaciones familiares, de teoría de grafos y de horticultura se usa para los arboles generales de la misma forma que para los arboles binarios. En particular, si N es un nodo con sucesores S1, S2,…, Sm se dice que N es el padre de los Si son hijos de N y los Si son hermanos unos de otros.



El término “árbol” aparece, con significados ligeramente diferentes, en muchas áreas diferentes de las matemáticas y de la informática. Aquí asumimos que nuestro árbol general T está enraizado, es decir, que T tiene un nodo distinguido R llamado raíz de T; y que T esta ordenado, o seo, que los hijos de cada nodo N de T tienen un orden especifico. Estas dos propiedades no se requieren siempre para definir un árbol.



REPRESENTACION DE ARBOLES GENERALES EN LA COMPUTADORA



Suponga que T es un árbol general. A menos que se diga lo contrario. T se mantendrá en memoria en términos de una representación enlazada que usa tres arrays paralelos, INFO, HIJO Y HERM, y una variable puntero RAIZ, tal como sigue. En primer lugar, cada nodo N de T corresponderá a una posición K tal que:



(1) INFO[K] contiene los datos del nodo N.



(2) HIJO[K] contiene la posición del primer hijo de N. La condición HIJO[K]=NULO indica que N no tiene hijos.



(3) HERM[K] contiene la posición del siguiente hermano de N. La condición HERM[K]=NULO indica que N es el último hijo de su padre.







Más aún, RAIZ contendrá la posición de la raíz R de T. aunque la anterior representación puede parecer artificial, tiene la importante ventaja de que cada nodo N de T, independientemente del número de hijos de N, contendrá exactamente tres campos.



Esta representación se puede extender fácilmente para representar un bosque F formado por arboles T1, T2, …, Tm, asumiendo que la raíces de los árboles son hermanas. En ese caso, RAIZ contendrá la posición de la raíz R1 del primer árbol T1; o cuando f este vacío, RAIZ será igual a NULO.





              GRAFOS Y SUS APLICACIONES



Se dice que un grafo g es completo si cada nodo u de g es adyacente a todos los demás nodos de g. claramente, un grafo así es conexo. Un grafo completo de n nodos tendrá n(n-1)¬¬/2 aristas. Un grafo conexo t sin ciclos se llama grafo árbol o árbol libre o simplemente árbol.



Un grafo g se dice que esta etiquetado si sus aristas tienen datos asignados. En particular, se dice g tiene peso si cada arista e de g tiene asignado un valor numérico no negativo w(e) llamado peso o longitud de e. en ese caso, a cada camino p de g se le asigna un peso o una longitud que es la suma de los pesos de las aristas que constituyen el camino p.



La definición de un grafo puede ser generalizada si permitimos lo siguiente:



1) aristas múltiples. dos aristas e y e’ distintas se llaman aristas múltiples si conectan los mismos extremos, o sea, si e=[u,v] y e´=[u,v].



2) bucles. una arista e se llama bucle si tiene extremos idénticos, o sea, si e=[u,v].



Tal generalización M se llama multígrafo. en otras palabras, la definición de un grafo normalmente no permite ni aristas múltiples ni bucles.



Un multígrafo M se dice que es finito si tiene un numero finito de nodos y de aristas. observe que un grafo g con un numero finito de nodos debe automáticamente tener un numero finito de aristas y por tanto debe ser finito; pero esto no es necesariamente cierto para un multígrafo M, ya que M puede tener múltiples aristas. A menos que se indique lo contrario, los grafos y multígrafos de este texto serán finitos.



Grafos dirigidos



Un grafo dirigido g, también llamado dígrafo o grafo, es lo mismo que un multígrafo, solo que cada arista e de g tiene una dirección asignada o, en otras palabras, arista e esta identificada por un par ordenado (u,v) de nodos de g en vez del par desordenado [u,v].



Suponga que g es un grafo dirigido con una arista dirigida e=(u,v). Entonces e también se llama arco. Mas aun, se usa la siguiente terminología:



1) e empieza en u y termina en v.



2) u es el origen o punto inicial de e, y v es el destino o punto terminal de e.



3) u es un predecesor de v y v es un sucesor o vecino de u.



4) u es adyacente hacia v y v es adyacente desde u.



El grado de salida de un nodo u de g, escrito gradsal (u), es el numero de aristas que empiezan en u. similarmente, el grado de entrada de u, escrito gradent (u), es el numero de aristas que terminan en u. un nodo u se llama fuente si tiene un grado de sallida positivo y un grado de entrada nulo. Similarmente, u se llama sumidero si tiene un grado de salida nulo y un grado de entrada positivo. las nociones de camino, camino simple y ciclo se aplican en los grafos dirigidos igual que los grafos no dirigidos excepto que la dirección de cada arista de un camino (ciclo) debe coincidir con la dirección del camino (ciclo). se dice que un nodo v es alcanzable desde un nodo u si existe un camino (dirigido) de u a v. un grafo dirijo g se dice que es conexo, o fuertemente conexo, si para cada par u, v de nodos de g existe un camino de u a v y también un camino de v a u. por otro lado, g se dice que es unilateralmente conexo si para cada par u, v de nodos de g hay un camino de u a v o un camino de v a u.

REPRESENTACIÓN SECUENCIAL DE GRAFOS: MATRIZ DE ADYACENCIA; MATRIZ DE CAMINOSExisten dos formas estándar de mantener un grafo g en la memoria de una computadora. una forma, llamada representación secuencial de G, se basa en la matriz de adyacencia A. La otra forma , llamada representación enlazada de G, se basa en listas enlazadas de vecinos. esta sección cubre la primera representación y muestra como se puede usar la matriz de adyacencia A de G para responder fácilmente ciertas cuestiones sobre conectividad de G.Independientemente de la forma en que se mantenga el grafo G en la memoria de la computadora, el grafo G normalmente se introduce en la computadora por su definición: un conjunto de órdenes y un conjunto de aristas.Matriz de adyacenciaSuponga que G es un grafo dirigido simple de m nodos y suponga que ,los nodos de G han sido ordenados y llamados v1, v2…, vm. así la matriz de adyacencia A=(aij) del grafo G es la matriz de m*m elementos. Una matriz A así, que contiene solo entradas de 0 y 1, se llama matriz de bits o matr4iz booleana. la matriz de adyacencia A del grafo G depende de la ordenación de los nodos de G; esto es, diferentes ordenaciones de los nodos pueden resultar en diferentes matrices de adyacencia. sin embrago, las matrices obtenidas por dos ordenaciones diferentes están fuertemente relacionadas en cuanto que una puede ser obtenida de la otra simplemente cambiando filas y columnas. a menos que se indique lo contrario, asumiremos que los nodos de nuestro grafo G tienen un orden fijo. Suponga que G es un grafo no dirigido. Entonces la matriz de adyacencia de G, A será una matriz simétrica, o sea, con aij =aji para cada iy j. esto viene del hecho de que cada arista no dirigida [u , v] corresponde a las dos aristas dirigidas (u , v) y (v , u). la anterior representación matricial de un grafo se puede extender a multígrafos. específicamente , si G es un multígrafo, entonces la matriz de adyacencia de G es la matriz A de m*m=(aij) definida haciendo aij igual al numero de aristas desde vi , hasta vj.Matriz de caminosSea G un grafo dirigido simple con m nodos, v1,v2,…vm. la matriz de caminos o matriz de alcance de G es la matriz m-cuadrada P=(pij). Suponga que hay un camino desde vi hasta vj. Entonces tiene que haber un camino simple desde vi hasta vj cuando vi=vj, o un ciclo de vi a vj cuando vi=vj. Como G solo tiene m nodos, un camino simple así ha de tener longitud m-1 o menor, o un ciclo así ha de tener longitud m o menor. Esto significa que existe una entrada ij no nula de la matriz Bm, definida al final de la anterior subseccion. De acuerdo con esto, tenemos la siguiente relación entre la matriz de caminos P y la matriz de adyacencia A. 8.4 ALGORITMO DE WARSHALL; CAMINOS MINIMOSSea G un grafo dirigido con m nodos , v1,v2,…,vm. Suponga que queremos encontrar la matriz de caminos p para el grafo G. Warshall dio un algoritmo para este propósito que es mucho mas eficiente que calcular la potencias de la matriz de adyacencia A.por su matriz adyacente A. este algoritmo encuentra la matriz de caminos(booleana) P del grafo G.1. [inicializar P]. repetir para I,J=1,2,…M:Si A[I,J]=0, entonces: Hacer P[I,J]:=0;Si no: Hacer P[I,J]:=1[Fin del bucle].2. [actualizar P]. repetir pasos 3y4 para K=1,2,..,M:3. repetir paso 4 para 1=1,2,…,M:4. repetir para J=1,2,…,M:hacer P[I,J]:=P[I,J] v (P[I,K] ^ P[K,J]).[Fin del bucle].[Fin del bucle del paso 3].[Fin del bucle del paso 2].5. salir.ALGORITMO DEL CAMINO MÍNIMOSea G un grafo dirigido con m nodos, v1,v2,…,vm. Suponga que G tiene peso; o sea, suponga que cada arista e de G tiene asignado un numero no negativo w(e) llamado peso o longitud de la arista e. entonces G se puede mantener en memoria por su matriz de pesos w=(wij).La matriz de caminos P nos dice si hay o no caminos entre los nodos. ahora queremos encontrar una matriz Q=(qij) que nos diga las longitudes de los caminos mínimos entre los nodos o, mas exactamente, una matriz Q=(qij), dondeqij=longitud del camino mínimo de vi a vjAhora describiremos una modificación del algoritmo de warshall que encuentra la matriz Q. definimos una secuencia de matrices Q0,Q1,…,Qm (análogas a las anteriores matrices p0,,P1,…,Pm) cuyas entradas vienen dadas por:QK[i,j]= la menor de las longitudes de los anteriores caminos de vi a vj o la suma de las longitudes de los anteriores caminos de vi a vk y vk a vjMás exactamente,QK[i,j]=MIN(Qk-1[i,j], Qk-1[i,k]+Qk-1[k,j])La matriz inicial Q0 es la misma que la matriz de pesos W excepto que cada 0 de W se reemplaza por 00 (o un numero muy, muy grande). la matriz final Qm será la matriz Q deseada.Algoritmo 8.2: (algoritmo del camino mínimo). Un grafo con peso G de M nodos esta en memoria mediante su matriz de pesos W. este algoritmo encuentra la matriz Q tal que [I,J] es la longitud delo camino mínimo del nodo VI al nodo VJ. INFINITOes un número muy grande y MIN es la función del valor mínimo.1. [inicializar Q]. Repetir para I,J=1,2,…, M:Si W[I,J]=0, entonces: Hacer Q[I,J]:=INFINITO;Si no: Hacer Q[I,J]:=W[I,J].[fin del bucle].2. [Actualizar Q]. Repetir pasos 3 y 4 para K=1,2,…, M:3. Repetir paso 4 para I=1,2,…, M:4. Repetir para J=1,2,…, M: Hacer Q[I,J]:=MIN(Q[I,J], Q[I,K]+Q[K,J]).[Fin del bucle].[Fin del bucle del paso 3].[Fin del bucle del paso 2].5. salir.REPRESENTACIÓN ENLAZADA DE UN GRAFO

Sea G un grafo dirigido con m nodos. la representación secuencial de G en memoria- o sea, la representación de G por su matriz de adyacencia A- tiene unas cuantas desventajas importantes. en primer lugar, puede ser difícil insertar y eliminar nodos de G. esto es porque el tamaño de A debería de ser cambiado y los nodos deberían ser reordenados, así que habría muchos cambios en la matriz A. mas aun, si el numero de aristas es 0(m) o 0(m log2 m), entonces la matriz A estará desperdiciada (contendrá muchos ceros); por tanto, se desperdiciara una gran cantidad de espacio. Por tanto, G normalmente se representa en memoria por una representación enlazada, también llamada estructure de adyacencia.



Aquí NODO será el nombre o valor clave del nodo, SIG será un puntero al siguiente nodo de la lista NODO y ADY será un puntero al primer elemento de la lista de adyacencia del nodo, que se mantiene en la lista ARISTA. el área sombreada indica que puede haber otra información en el registro, tal como el grado de entrada GRADENT del nodo, el grado de salida GRADSAL del nodo, el ESTADO del nodo durante la ejecución de un algoritmo, etc. (alternativamente se puede asumir que NODO es un array de registro contenido campos como NOMBRE, GRADENT, GRADSAL, ESTADO, …)





El campo DEST apuntara en la posición en la lista NODO del nodo destino o terminal de la



arista. el campo ENL enlazara juntas las aristas con el mismo nodo inicial, o sea, los nodos con



la misma lista de adyacencia. el área sombreada indica que puede haber otra información en el



registro correspondiente a la arista, tal como un campo ARIS conteniendo los datos etiquetados



de la arista cuando G es un grafo con etiquetas, un campo PESO conteniendo el peso de la



arista cuando G es un grafo con peso, etc.



OPERACIONES SOBRE GRAFOS



Suponga que un grafo G se mantiene en memoria mediante la representación enlazada



GRAFO (NODO, SIG, ADY, PRINCIPIO, NDISP, DEST, ENL, ADISP)



Esta sección discute las operaciones de búsqueda, inserción y eliminación de nodos y aristas en el grafo G. la operación de recorrido de trata en la siguiente sección.



las operaciones de esta sección usan ciertos procedimientos del capitulo 5, de listas enlazadas. por completitud, mostramos esos procedimientos a continuación:



Procedimiento 8.3: BUSCA (INFO, ENL, PRINCIPIO, ITEM, POS) [Algoritmo 5.2]



Busca la posición POS del primer nodo que contiene a ITEM, o hace



POS:=NULO.



1. Hacer PTR:=PRINCIPIO.



2. Repetir mientras PTR≠NULO:



Si ITEM=INFO [PTR], entonces: Hacer POS:=PTR y volver.



Si no: Hacer PTR:=ENL [PTR].



[Fin del bucle].



3. Hacer POS:=NULO y volver.



BUSQUEDA EN UN GRAFO



Suponga que queremos encontrar la posición POS de un nodo N de un grafo C. Esto se puede llevar a cabo mediante el procedimiento 8.3, tal como sigue:



Procedimiento 8.4 ELIMINAR (INFO, ENL, PRINCIPIO, DISP, ITEM, INDIC)



[Algoritmo 5.10]



Elimina el primer nodo de la lista que contenga a ITEM, o hace



INDIC:=FALSO si ITEM no aparece en la lista.



1. [¿Lista vacía?]S i PRINCIPIO=NULO, entonces: Hacer



INDIC:=FALSO y volver.



2. [¿ITEM en primer nodo?]Si INFO[PRINCIPIO]=ITEM, entonces:



Hacer PTR:=PRINCIPIO,



PRINCIPIO:=ENL[PRINCIPIO],



ENL[PTR]:=DISP, DISP,:=PTR,



INDIC:=VERDADERO y volver.



[Fin del condicional],



3. Hacer PTR:=ENL [PRINCIPIO] y SALVA:=PRINCIPIO.



[Inicializar punteros].



4. Repetir pasos 5,6 mientras PTR≠NULO:



5. Si INFO [PTR]=ITEM, entonces:



Hacer ENL[SALVA]:=ENL[PTR],



ENL[PTR]:=DISP, DISP:=PTR,



INDIC:=VERDADERO y volver.



[Fin del condicional].



6. Hacer SALVA:=PTR y PTR:=ENL[PTR].



[Actualizar punteros].



[Fin del bucle del paso 4].



7. Hacer INDIC:=FALSO y volver.



INSERCION EN UN GRAFO



Suponga que va a insertar un nodo N en el grafo G. observe que N será asignado a NODO [NDISP], el primer nodo disponible. Más aun, como N será un nodo aislado, se debe hacer ADY [NDISP]:=NULO. EL PROCEDIMIENTO 8.6 hace esto mediante una variable lógica INDIC que indica si hay desbordamiento.



Procedimiento 8.6 INSNODO (NODO, SIG, ADY, PRINCIPIO, NDISP, N, INDIC)



Este procedimiento inserta el nodo N en el grafo G.



1. [¿DESBORDAMIENTO?]Si NDISP=NULO, entonces: hacer



INDIC:=FALSO y volver.



2. Hacer ADY[NDISP]:=NULO.



3. [quitar el nodo de la lista NDISP]



Hacer NUEVO:=NDISP y NDISP:=SIG[NDISP].



4. [Insertar nodo N en la lista NODO].



Hacer NODO[NUEVO]:=N, SIG[NUEVO]:=PRINCIPIO y



PRINCIPIO:=NUEVO.



5. Hacer INDIC:=VERDADERO y volver.



ELIMINACION EN UN GRAFO



Suponga que se va a eliminar una arista (A,B) del grafo G. (Nuestro procedimiento asumirá que A y B son nodos de G.) De nuevo debemos encontrar primero la posición POSA de A y la posición POSB de B en la lista de nodos.



Procedimiento 8.8: ELIMARISTA (NODO, SIG, ADY, PRINCIPIO, DEST, ENL, ADISP, A, B, INDIC)



Este procedimiento elimina la arista (A,B) del grafo G.

 1. Llamar BUSCA (NODO, SIG, PRINCIPIO, A, POSA). [Localizar nodo A].

2. Llamar BUSCA (NODO, SIG, PRINCIPIO, B, POSB). [Localizar nodo B].

3. Llamar ELIMINAR (DEST, ENL, ADY[POSA], ADISP, POSB, INDIC).

4. Volver.Suponga que se va a eliminar un nodo N del grafo G.

esta operación es mas complicada que las operaciones de búsqueda e inserción y que la de eliminar una arista, ya que debemos eliminar todas las aristas que contengan a N.

RECORRIDO DE UN GRAFO

Muchos algoritmos de grafos requieren que se examinen sistemáticamente los nodos y las aristas de un grafo G. esto se puede hacer de dos formas estándar. Una forma se llama búsqueda en anchura y la otra búsqueda en profundidad.

La búsqueda en anchura usara una cola y la otra búsqueda en profundidad.durante la ejecución de nuestros algoritmos, cada nodo N de G estará en uno de tres estados, lo que se llama estado de N, tal como sigue:ESTADO =1: (Estado de preparado).

El estado inicial del nodo N.ESTADO =2: (Estado de espera). El nodo N esta en la cola o en la pila, esperando a ser procesado.ESTADO =3: (Estado de procesado). El nodo N ha sido procesado.

BÚSQUEDA EN ANCHURA

La idea general de la búsqueda en anchura comenzando en un nodo de partida A es la siguiente. Primero examinamos el nodo de partida A. luego examinamos todos los vecinos de A. luego examinamos todos los vecinos de los vecinos de A. y así sucesivamente. naturalmente, necesitamos seguir la pista a los vecinos de un nodo y tenemos que garantizar que ningún nodo se procesa mas de una vez. Esto se hace usando una cola para mantener los nodos que estén esperando para ser procesados y usando un campo ESTADO que nos diga el estado actual de los nodos.

BUSQUEDA EN PROFUNDIDAD

La idea general de la búsqueda en profundidad comenzando en un nodo A es la siguiente. Primero examinamos el nodo inicial A. luego examinamos cada nodo N de un camino P que comience en A; o sea, procesamos un vecino de A, luego un vecino de un vecino de un vecino A así sucesivamente tras llegar un “punto muerto “o sea, el final del camino P, volveremos atrás por P hasta que podamos conseguir por otro camino P´. y a si sucesivamente. (Este algoritmo es similar al recorrido inorden de un árbol binario, y también a la forma en que se debe pasar a través de un laberinto). El algoritmo es muy similar al de búsqueda en anchura excepto que usamos una pila en lugar de una cola. De nuevo se usa un campo ESTADO para indicar el estado actual de un nodo.

El algoritmo es el siguiente:

Algoritmo B: este algoritmo realiza una búsqueda en profundidad en el grafo G comenzando en un nodo A.

1. Inicializar con todos los nodos al estado de preparado (ESTADO =1).

2. Meter el nodo inicial A en la pila y cambiar su estado a estado de espera (ESTADO=2).

3. Repetir paso 4 y 5 hasta que la pila esta vacia.

4. Sacar el nodo N en la cima de la pila. Procesar el nodo N y cambiar un estado al de procesado (ESTADO =3).

5. Meter en la pila todos los vecinos de N que estén en estado de preparados (ESTADO=1) y cambiar su estado al de espera (ESTADO =2). [fin del bucle del paso 3

6. salir De nuevo este algoritmo procesa solo los nodos que sean alcanzables desde el nodo de partida A. si queremos examinar todos los nodos G entonces el algoritmo debe ser modificado para que comience de nuevo con otro nodo que llamaremos B que este en estado de preparado, este nodo se puede obtener recorriendo la lista de nodos.



CONJUNTOS PO; ORDENACION TOPOLOGICA

Suponga que S es un grafo tal que cada nodo vi de S representa una tarea y cada arista (u, v) significa que la finalización de la tarea u es un prerrequisito para que comience la tarea u. suponga que tal grafo S contiene un ciclo tal que P= (u, v, w, u)Esto significa que no podemos empezar u hasta completar w. así no podemos completar ninguna tarea del ciclo. Por tanto, grafo S así, que representa tareas y relaciones de procedencia, no puede tener ciclos.Si S es un grafo sin ciclos. Considere la relación <>

(1) para cada elemento u de S, tenemos que u

(2) si u

(3) Si u

Tal relación <>

ORDENACION TOPOLOGICA

Sea S un grafo dirigidos sin ciclos (o conjunto parcialmente ordenado). Una ordenación topológica T de S es una ordenación lineal de los nodos de S que preserva la ordenación parcial de S original. Escogido como primer elemento de la ordenación T. de acuerdo con esto, nuestro algoritmo repetirá los siguientes pasos hasta que el grafo S este vacio.

(1) Buscar el nodo N con grado de entrado nulo.

(2) Eliminar N y sus aristas del nodo S.

El orden en que los nodos son eliminados del grafo S usaran un array auxiliar COLA que contendrá temporalmente todos los nodos con el grado de entrada nulo. El algoritmo también usa un campo GRADENT tal que GRADENT(N) contendrá el grado de entrado actual del nodo N. el algoritmo es el siguiente:Algoritmo C: este algoritmo encuentra una ordenación topológica T de un grafo S sin ciclos.

(1) Encontrar el grado de entrada GRADENT(N)de cada nodo N de S.( se puede hacer recorrido cada lista de adyacencia.

(2) Poner en una cola todos los nodos con grado de entrada nulo.

(3) Repetir pasó 4 y 5 hasta que la cola este vacía.

(4) Quitar el nodo N al frente de la cola (haciendo FRENTE:=FRENTE+1)(5) Repetir lo siguiente para cada vecino M a N

Hacer GRADENT (M):=GRADENT (M)-1[Esto elimina la arista de N a M]Si GRADENT (M)=0, entonces: añadir M al final de la cola.[fin del bucle].

[Fin del bucle del paso 3](6) salir.

Códigos compilados de listas enlazadas

#include

#include

#include int Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

int InsPr(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento)

{

clrscr();int Info[8]={12,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2,Elemento,Res;cout<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Insertar?";

cin>>Elemento;

InsPr(Info,Indice,Inicio,Disp,Elemento);

getch();

}

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

{

int Apuntador=Inicio;

while(Apuntador!=-999)

{

cout<

Apuntador=Indice[Apuntador];

}

}

void InsPr(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento)

{

if(Disp!=-999){int Apuntador=Disp;

Disp=Indice[Disp];

Info[Apuntador]=Elemento;

Indice[Apuntador]=Inicio;

Inicio=Apuntador;

Recorrido(Info,Indice,Inicio,Disp);

}

elsecout<<"Overflow...";

}

{

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp);

void EliBusq(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento);

{

clrscr();int Info[8]={12,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2,Elemento,Res;

cout<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Eliminar?";

cin>>Elemento;

EliBusq(Info,Indice,Inicio,Disp,Elemento);

getch();

}

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

{

int Apuntador=Inicio;

while(Apuntador!=-999){cout<

Apuntador=Indice[Apuntador];

}

}

void EliBusq(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento){int Temp=Inicio,Temp2;

if(Temp==-999)

{

cout<<"Lista Vacia... Imposible Eliminar";

return;

}while(Temp!=-999)

{

if(Elemento==Info[Temp])

{

if(Temp==Inicio)

{

Inicio=Indice[Inicio];

elseºIndice[Temp2]=Indice[Temp];

Indice[Temp]=Disp;

Disp=Temp;

Recorrido(Info,Indice,Inicio,Disp);

return;

}

else

{

Temp2=Temp;

Temp=Indice[Temp];

}

}

cout<<"Dato no encontrado... Imposible Eliminar"

;return;

}

{

int Busqueda(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento);

{

clrscr();

int Info[8]={12,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2,Elemento,Res;

cout<<"Que Numero deseas buscar?";

cin>>Elemento;

Res=Busqueda(Info,Indice,Inicio,Disp,Elemento);

if(Res==-999)cout<<"Dato No Encontrado...";getch();

}

int Busqueda(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento)

{

int Apuntador=Inicio;

while(Apuntador!=-999)

{

if(Elemento==Info[Apuntador])

{

cout<<"Numero "<

return Apuntador;

}

Apuntador=Indice[Apuntador];

}

return Apuntador;

}

{

int InsOrd(int Info[8],int Indice[8],int Inicio,int Elemento);

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp);

void InsNd(int Info[8],int Indice[8],int Inicio,int Disp, int Elemento, int Npos);

{

clrscr();

int Info[8]={12,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2,Elemento,Res;

cout<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Insertar?";

cin>>Elemento;Res=InsOrd(Info,Indice,Inicio,Elemento);

InsNd(Info,Indice,Inicio,Disp,Elemento,Res);getch();

}

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

{

int Apuntador=Inicio;

while(Apuntador!=-999)

{

cout<

Apuntador=Indice[Apuntador];

}

}

void InsNd(int Info[8],int Indice[8],int Inicio,int Disp, int Elemento, int Npos)

{

if(Disp!=-999)

{

int Apuntador=Disp;

Disp=Indice[Disp];

Info[Apuntador]=Elemento;

if(Npos==-999)

{

Indice[Apuntador]=Inicio;

Inicio=Apuntador;

}

else

{

cout<

Apuntador=Indice[Apuntador];

}

}

void InsPr(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento)

{

if(Disp!=-999)

{

int Apuntador=Disp;

Disp=Indice[Disp];

Info[Apuntador]=Elemento;

Indice[Apuntador]=Inicio;

Inicio=Apuntador;

Recorrido(Info,Indice,Inicio,Disp);

}

elsecout<<"Overflow...";

}

{

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp);

void EliBusq(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento);

{

clrscr();

int Info[8]={12,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2,Elemento,Res;

cout<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Eliminar?";

cin>>Elemento;

EliBusq(Info,Indice,Inicio,Disp,Elemento);

getch();

}

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

{

int Apuntador=Inicio;

while(Apuntador!=-999)

{

cout<

Apuntador=Indice[Apuntador];

}

}

void EliBusq(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento)

{

int Temp=Inicio,Temp2;

if(Temp==-999)

{

cout<<"Lista Vacia... Imposible Eliminar";

return;

}

while(Temp!=-999)

{

if(Elemento==Info[Temp])

{

if(Temp==Inicio)

{

Inicio=Indice[Inicio];

elseºIndice[Temp2]=Indice[Temp];

Indice[Temp]=Disp;

Disp=Temp;

Recorrido(Info,Indice,Inicio,Disp);

return;

}else{Temp2=Temp;

Temp=Indice[Temp];

}

}

cout<<"Dato no encontrado... Imposible Eliminar";

return;

}

{

int Busqueda(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento);

{

clrscr();

int Info[8]={12,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2,Elemento,Res;

cout<<"Que Numero deseas buscar?";

cin>>Elemento;

Res=Busqueda(Info,Indice,Inicio,Disp,Elemento);

if(Res==-999)cout<<"Dato No Encontrado...";

getch();

}

int Busqueda(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento)

{

int Apuntador=Inicio;

while(Apuntador!=-999)

{

if(Elemento==Info[Apuntador])

{

cout<<"Numero "<

return Apuntador;

}

Apuntador=Indice[Apuntador];

}

return Apuntador;

}

{

int InsOrd(int Info[8],int Indice[8],int Inicio,int Elemento);

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp);

void InsNd(int Info[8],int Indice[8],int Inicio,int Disp, int Elemento, int Npos);

{

clrscr();

int Info[8]={12,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2,Elemento,Res;cout<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Insertar?";

cin>>Elemento;

Res=InsOrd(Info,Indice,Inicio,Elemento);

InsNd(Info,Indice,Inicio,Disp,Elemento,Res);

getch();

}

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

{

int Apuntador=Inicio;

while(Apuntador!=-999)

{

cout<

Apuntador=Indice[Apuntador];

}

}

void InsNd(int Info[8],int Indice[8],int Inicio,int Disp, int Elemento, int Npos)

{

if(Disp!=-999)

{

int Apuntador=Disp;

Disp=Indice[Disp];

Info[Apuntador]=Elemento;

if(Npos==-999)

{

Indice[Apuntador]=Inicio;

Inicio=Apuntador;

}

else