resumen grafos y arboles.victor
DESCRIPTION
resumenTRANSCRIPT
1
Cuestionario.
Lic. En informática.
Unidad 5. Tema: grafos y arboles.
Materia: estructura de datos
Alumno: Estrada Mosso Víctor Daniel.
3er semestre.
Grupo: A.
Tlapa de comonfort gro. A 13 de septiembre de 2009
2
ÁRBOLES
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, T2.
Si T contiene una raíz R, los dos árboles T1, T2, se llaman, respectivamente subárboles
izquierdo y derecho de la raíz R. si T1 no es vacio, entonces su raíz se llama sucesor derecho
de R.
Un árbol binario T se presenta frecuentemente en forma de diagrama. En particular, el
diagrama de la figura 7-1 representa un árbol T como sigue. (i) T con 11 nodos. Representados
por las letras de la A a la L. excluyendo la I. (ii) La raíz del árbol T es el nodo de la A, en la
parte superior del diagrama. (iii) una línea hacia abajo y a la izquierda de N señala un sucesor
derecho de N. observe que:
B es un sucesor izquierdo y C un sucesor derecho del nodo A.
El subárbol izquierdo de la raíz A consiste en los nodos B,D,E,F, y el subárbol derecho de A
consiste en los nodos C,G,H,J,K y L.
B A
D E C
F G
H
J
L K
3
Cualquier nodo de N de un árbol binario T tiene 0,1 ó 2 sucesores. Los nodos A, B,C Y H
tienen dos sucesores, los nodos R,J solo tienen un sucesor, y los nodos D,F,G,L y Y no tienen
sucesores. Los nodos sin sucesor se llaman nodos terminales.
Dos árboles binarios T y T se dice que son similares si tienen la misma estructura ó, en otras
palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen
los mismos contenidos en sus correspondientes nodos.
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 si un sucesor S2. Entonces N se llama el padre de S1, S2 analógicamente, S1 se
llama el hijo de izquierdo de N y S2 el hijo derecho de N. es mas S1, S2 se dice que son
hermanos. Cada nodo de N de un árbol binario T, excepto la raíz, tiene un único padre
predecesor.
I
+
- .
b
a c d
4
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 le 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
numero nodos posibles y si todos los nodos del último nivel están situados. Lo más posible a la
izquierda.
Así solo existe un árbol completo Tn con exactamente n nodos (por supuesto, ignoramos los
contenidos de los nodos). Los nodos de los árboles completos T26 ha sido intencionalmente
etiquetados con los enteros 1, 2,….., 26, de izquierda a derecha y de generación en
generación. Con este etiquetado, se pueden determinar fácilmente los hijos o del padre de
cada nodo k son, de un árbol completo Tn. Específicamente, los hijos izquierdo y derecho de
un nodo k son, respectivamente, 2*k y 2*k +, 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 d n del
árbol completo Tn de n nodos viene dada por: D n= [log2 n+1]
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 se caso, los nodos con dos hijos se denomina 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 los cuadrados para los nodos
externos.
El termino <<árbol binario extendido>> viene de la siguiente operación. Considere un árbol
binario T, como el de la figura 7-5 (a). Entonces T puede ser <<convertido>> a un árbol-2
reemplazando cada subárbol vacía por un nuevo nodo, como se ve en la figura 7-5(b). un
ejemplo importante de árbol-2 es el árbol T correspondiente a una expresión algebraica E que
usa solo operaciones binarias.
5
(a)Árbol binario T
(b)Árbol-2 extendido
Representación de árboles binarios en memoria
Sea T un árbol binario. Esta sección discute dos formas de representar T en la memoria. La
primera y más usual forma, llamada representación enlazada de T, es analógica a la forma en
que se representan las listas enlazadas en memoria. La segunda forma, que usa un arrray
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 de R de T y, dado cualquier nodo
de N de T, se tenga acceso directo a los hijos de N.
Representación enlazada de árboles binarios
Considere el árbol T. a menos que se especifique lo contrario, T se mantendrá en memoria
en términos de una enlazada que usa tres arrays paralelos, INFO,IZQ y DER, y una variable
puntero RAIZ tal como sigue en el 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[Z}contendrá la localización de hijo izquierdo del nodo N
(3)DER[K]contendrá la localización del hijo derecho del nodo N
Más aun, RAIZ contendrá la posición de la raíz R de T. si algún subárbol está vacío, entonces
el correspondiente puntero contendrá el valor nulo; si el árbol mismo T está vacío, entonces
RAIZ contendrá el valor nulo.
6
INFO IZQ DER
1 K 0 0
2 C 3 6
RAIZ
3 G 0 0
5
4 14
5 A 10 2
DISP
6 H 17 1
8
7 L 0 0
8 9
9 4
10 B 18 13
11 19
12 F 0 0
13 E 12 0
14 15
15 16
16 11
17 J 7 0
18 D 0 0
19 20
20 0
FIG. 7-7
7
NOMBRE
NSS
SEXO
SALRIO
IZQ
DER
1
0
RAIZ
2 Davis
192-38-7282
Hembra
22800
0
12
14
3 Kellly
165-64-3351
Varón
19000
0
0
4 Green
175-56-2261
Varón
27200
2
0
5
1
DISP
6 Brown
178-52-1056
Hembra
14700
0
0
8
7 Lewis
181-58-9939
Hembra
16400
3
10
8
11
9 Cohen
177-44-4557
Varón
19000
6
4
10 Rubin
135-46-6262
Hembra
15500
0
0
11
113
12 Evans
168-56-8113
Varón
34200
0
0
13
5
14 Harris
208-56-1654
Hembra
22800
9
7
FIG. 7-8
8
Representación secuencial de árboles binarios
Suponga que T es un árbol binario que es completo a casi es completo. Entonces una forma
eficiente de mantener T en memoria llamada representación secuencial de T. Esta
representación usa únicamente un array lineal ÁRBOL de la forma siguiente.
(a)la raíz R de T se guarda en ÁRBOL[1]
(b)si un nodo N esta en el ÁRBOL[K], entonces su hijo izquierdo esta en ÁRBOL[2*k] y su hijo
derecho en ÁRBOL[2*K+1].
ÁRBOL
Harris
Cohen Lewis
Brown Green Kelly Rubin
Davis
Evans
De nuevo, se usa NULO para indicar un subárbol vacio. En particular, ÁRBOL [1]=NULO indica
que el árbol está vacío.
9
RECORRIDO DE ÁRBOLES 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í:
Presorden: (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) procesar la raíz R
(3) recorrer el subárbol derecho de R en postorden
Observe que cada algoritmo contiene los mismos tres 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 e algoritmo <<pre>>, la raíz R se
procesa antes de recorrer l0os árboles; en el algoritmo <<in>>, la raíz R se procesa entre
los dos recorridos de los subárboles; y en le algoritmo <<post>>, la raíz se procesa tras
recorrer los subárboles.
Los tres algoritmos se denominan a veces, respectivamente, recorrido nodo-izquierdo-nodo-
derecha (de ingles, LNR) y recorrido izquierdo-derecho-nodo (LRN, del ingles).
ÁRBOLES
A
LT C
B Rt
D E F
10
ALGORITMOS DE RECORRIDO USANDO PILAS
Suponga un árbol binario T mantenido en memoria por una representación enlazada.
ÁRBOL (INFO, IZQ, DER, RAIZ)
Esta 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 reorden:
El orden del recorrido preorden usa una variable PTR (puntero) que contendrá la posición del
nodo N que se está examinando. Esto se en la figura 7-15, donde L(N) denota al hijo izquierdo
del nodo N y R(N) denotado al hijo derecho. El algoritmo también usa un array pila, que
contendrá las direcciones de los nodos que hayan de ser procesados.
PTR
N
L(N) R(N)
FIG. 7-15
ALGORITMO: Inicialmente meter NULO en PILA y entonces PTR:=RAIZ. Entonces
repetir los siguientes pasos hasta que PTR o, lo que es el mismo, mientras PTR≠NULO.
Una presentación formal de nuestro algoritmo de recorrido pre orden será:
ALGORITMO: PREORD (INFO,IZQ, DER, RAIZ)
UN ÁRBOL BINARIO Testa en memoria, el algoritmo hace un recorrido preorden T,
aplicando una operación PORCESO a cada uno de sus nodos. Se usa un array PILA
para mantener temporalmente las direcciones de los nodos
1.- [inicialmente meter NULO en PILA e iniciar PTR].
Poner SUP:=1,PILA[1]:=NULO Y PTR:=RAIZ
2.- Repetir pasos 3 a 5 mientras PTR≠NULO
3.- Aplicar PROCESO a INFO[PRT}.
4.- [¿hijo derecho?]
Si DER [PTR]≠NULO, entonces :[meterlo en PILA].
Poner SUP:=SUP+1 y PILA[SUP]:=DER[PTR]
[Fin de condicional].
5.- [¿Hijo izquierdo?]
Si IZQ [PTR]≠NULO, entonces:
Poner PTR:=PILA [SUP] y SUP:=SUP-1
[Fin del condicional]
11
Recorrido Inorden
El algoritmo de corrido inorden también usa una variable puntero PTR, que contendrá la
posición del nodo N que se está examinando, y un array PILA, que mantendrá las direcciones
de los nodos que queden por procesa. De hecho, en este algoritmo, un nodo sólo se procesa
cuando se saca de la PILA.
Recorrido postorden.
El algoritmo de recorrido postorden es mas complicado que los dos algoritmos anteriores, ya
que aquí tenemos que salvar el nodo N en dos situaciones distintas, distinguimos 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 objetivo obvio.) de nuevo se usa una variable PTR
(puntero)que a de contener la posición del nodo N que se esté examinando.
ALGORRIMO: INOR (INFO, IZQ,DER, RAIZ)
Un árbol binario está en memoria. Este algoritmo hace un recorrido inorden de
T, aplicando una operación PORCESO a cada uno de sus nodos. Se usa en
array PILA para mantener temporalmente las direcciones de los nodos.
1.- [meter NULO en PILA e inicializar PTR]
Hacer SUP:=1, PILA [1], PILA [1]:=NULO y PTR :=RAIZ
2.- Repetir mientras que PTR ≠NULO:[meter el camino izquierdo en PILA ].
(a) hacer SUP:=SUP+1 y PILA +1 y PILA [SUP]:=PTR [guardar nodo].
(b) hacer PTR:=PTR:=IZQ [PTR],[Actualizar PTR].
3.- hacer PTR:=PILA y SUP:=SUP=:=SUP-1. [sacar nodo de PILA].
4.- repetir pasos 5 a 7 mientras PTR ≠NULO:[vuelta atrás].
5.- aplicar el PROCESO a INFO[PTR].
6.- [¿hijo derecho?]. si DER [PTR]≠NULO entonces:
(a) hacer PTR :=DER[PTR].
(b)ir al paso 2
[Fin de condicional].
7.- hacer PTR:=PILA [SUP] Y SUP:=SUP-1. [sacar nodo].
[Fin del bucle del paso 4]
8.-salir.
12
7.6 NODOS CABECERA; ÁRBOLES ENHEBRADOS
Nodos con 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, llamada nodo cabecera. Cuando se usa este
nodo extra, la variable puntero el árbol, que llamaremos CABEZA (en lugar de raíz), apuntara al
nodo cabecera, el puntero izquierdo del nodo cabecera apuntara a la raíz de T.
Hebras; enhebrado inorden
Considere de nuevo la representación enlazada de un árbol binario T. aproximadamente la
mitad de las entradas de los campo puntero IZQ y DER contendrá valores nulos. Este espacio
se puede aprovechar más eficientemente reemplazados las entradas nulas por algún otro tipo
de información. Específicamente, reemplazaremos ciertas entradas nulas con punteros
especiales que apuntaran a nodos supriores de árbol. Estos punteros especiales se llaman
hebras, y los árboles binarios con este tipo de punteros se llaman árboles enhebrados.
Las hebras de 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 las
líneas discontinuas. En la memoria de la computadora se pude 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.
13
Cabecera
Fig. 7-18
ARBOLES BINARIOS DE BÚSQUEDA
Esta sección discute una de las estructuras de datos mas importantes de la informática, el árbol
binario de búsqueda. 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 al insertar y borrar elementos.
(b) lista enlazada. Aquí se puede insertar y borrar fácilmente, pero es costoso el buscar y encontrar
un elemento, ya que se pude buscar una búsqueda secuencial.
x
A
C B
X D X E X X G X H
X F X J X X K X
X L X
14
Supongamos que T es un árbol binario. Entonces T se dice que es un árbol binario de
búsqueda (o árbol binario ordenado) se cada 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 que cualquier valor del
subárbol derecho de N. (no es difícil ver que esta propiedad garantice que el recorrido inorden
de T dará una lista ordenado de los elementos de T).
38
56
14 82
8 23 45
18 70
Fig. 7-12
Búsqueda e inserción en arboles binarios en búsqueda
Supongamos que T es un árbol binario de búsqueda. Esta sección discute las operaciones
básicas de búsqueda e inserción sobre T, de hecho, la búsqueda e inserción se darán por
único algoritmo de búsqueda e inserción. La operación de borrado se trata en la siguiente
sección. El recorrido de T es el mismo de un recorrido de binario.
Supongamos un ITEM de información dado. El siguiente algoritmo encuentra la posición de
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 RAIZ N del árbol
(i) si ITEM<N, proceder con el hijo izquierdo de N
(ii) 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 a
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 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.
15
Ejemplo 7-14:
(a) Considere el árbol binario de búsqueda T de la figura 7-21. Suponga que se da ITEM=20
simulando el algoritmo anterior, tendríamos los siguientes pasos.
1.- se compra ITEM=20 con la raíz, 38, del árbol T. como 20<38, se procede con el hijo
derecho de 38, que es 14.
2.- se compra ITEM=20 con 14. Como 20>14, se procede con el hijo derecho de 14, que es 23.
3.- se compra ITEM=20 con 23. Como 20<23, se procede con el hijo izquierdo de 23, que es
18.
4.- se compra ITEM=20 con 18. Como 20>18 y 18 no tiene hijo derecho, se inserta 20 como
hijo derecho de 18.
38
56
14 82
8 23 45
18 70
Fig. 7-22 ITEM=20 insertado
Complejidad del algoritmo de búsqueda
Suponga que buscamos un elemento de información en un árbol de búsqueda binaria T.
observe que el número de operaciones está limitado por la profundidad del árbol. Esto viene
16
del hecho de que bajamos por un único camino del árbol. Así, el tiempo de ejecución de la
búsqueda será proporcional a la profundidad del árbol.
Aplicaciones de los arboles de búsqueda binaria.
Considere un conjunto de N datos A1,A2,……AN. 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 (o sea, de izquierda a derecha).
(a)para cada elemento Ak con A1,A2,….,AK -1, o sea, comparar AK con aquellos elementos que
preceden a Ak
(b)si Ak se en A1,A2,…., AK -1, entonces borrar Ak
Tras a ver examinado todos los elementos, no habrá duplicados.
Ejemplo 7-16
Suponga que aplicamos A a la siguiente lista de 15 números:
14,10,17,12,10,11,20,12,18,25,20,,8,22,11,23.
Observe que los primeros cuatro números (14,10, 17 y 12) no se borran sin embargo.
A5= 10 se borra ya que A5=A2
A8= 12 se borra ya que A8=A4
A11= 20 se borra ya que A11=A7 A4= 11w se borra ya que A14=A6
Cuando el algoritmo A termina, quedaran los 11 números. 14,10,17,12,11,20,18,25,8,22,23. Que son todos distintos.
7.9 eliminación en un árbol de búsqueda binaria Suponga que T es un árbol de búsqueda binaria, y suponga un ITEM de información dado. Esta sección da un algoritmo que elimina ITEM del árbol T. El algoritmo de eliminación, 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.
17
Caso1.- N no tiene hijos. Entonces se elimina de T simplemente reemplazado 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 Reemplazado la posición de N en P(N) por la posición del hijo único de N. Caso 3.- N tiene dos sea S(N) el sucesor inorden de N. [el elector 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 ó 2) y luego reemplazando N en T por el nodo S(N). Observe que el tercer paso es mucho más complicado que los dos primeros, en los tres casos, el espacio de memoria del nodo N eliminando se devuelve a la lista DISP. 60
66
25
15 50
33
44
(a) el nodo 75 es eliminado.
INFO IZQ DER
RAIZ 1 33 0 9
2 25 8 10
3 60 2 4
4 66 0 0
DISP 5 6
6 0
7 5
8 15 0 0
9 44 0 0
10 50 1 0
3
7
18
(B) representación enlazada
Arboles en montón; ordenación por montón. Suponga que H es un árbol binario completo con N elementos. (al menos de que se indique lo contrario , asumiremos que H se tiene un memoria como un array lineal árbol mediante representación secuencial, no en representación enlazada). Se dice que H es u árbol en montón, montón máx. si cada nodo de 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 analógicamente: el valor de N es menor o igual que el valor de cualquier hijo de N). Ejemplo 7.19 Considere el árbol completo H de la figura 7-29(a). Observe que H es un árbol en montón. Esto significa, en particular, que el mayor elemento de H aparece en lo <<alto>> del montón, o sea, en la raíz del árbol. La figura 7-19 (b) muestra la presentación secuencial de H en el array ARBOL [1] es la raíz d3el árbol H, y los hijos de izquierdo y derecho de un nodo ARBOL [K] son, respectivamente, ARBOL [2K] y árbol [2K+1]. Esto significa en particular, que el padre de cualquier nodo de raíz árbol [J] es el nodo ARBOL [J÷2] (donde J÷2 significa división entera). Observe que los nodos de H del mismo nivel aparecen uno tras otro en el array ARBOL. 96 95 88 95 48 66 55 66 35 48 25 62 77 25 48 18 40 30 26 24
19
(a) montón
97 88 95 66 55 95 48 66 35 48 55 62 77 25 38 18 40 30 26 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
(b) Representación secuencial Fig. 7-29
Inserción en un árbol en montón 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 y como sigue:
(1) Primero se añade ITEM al final de H, de forma que H sigue siendo un árbol completo aunque no necesariamente un montón.
(2) Entonces se 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. Ejemplo 7-20 Considere el montón H de la figura 7-29. Suponga que queremos añadir ITEM=70 a H. primero ajuntamos 70 como el siguiente elemento del árbol completo, esto es, hacemos ARBOL [21]=70. Entonces 70 es el hijo derecho del ÁRBOL [10]=48. En la figura 7-30(a) esta dibujado el camino desde la raíz de H hasta 70. Ahora buscamos el sitio adecuado para 70 en el montón como sigue: (a) Comparamos 70 con su padre, 48. Como 70 es mayor que 48, intercambiamos 70 y
48; el camino ahora aparece como en la figura 7-30(b). (b) Comparamos 70 con su nuevo padre 55. Como 70 es mayor que 55,
intercambiamos; el camino ahora aparece como en la figura 7-30(c). (c) Comparamos 70 con su nuevo padre, 88. Como 70 no excede a 88, ITEM=70 ha
llegado a su lugar adecuado en H.
20
97 97 97 88 88 88 55 55 55 48 48 48
(a) (b) (c) 97 95 88 95 48 66 66 35 55 55 62 77 25 38
70
70
70
0
70
21
18 40 30 26 24 48
Fig. 7-30 ITEM=70 es insertado
LA DECLARACIÓN FORMAL DE PROCEDIMIENTO ES: Observe que ITEM no se asigna a ningún elemento del array ARBOL hasta que se encuentre su posición adecuada. El paso 7 se ocupa del paso especial de que IETM llegue a la raíz ARBOL [1]. Suponga un array A con N elementos dados. Podemos construir un montón H sobre el arrray A aplicando repetidamente el procedimiento 7.9 a A, o sea, ejecutando. Llamar INSMONTON (A, J, A [J+1]) Para j=1,2,……., N-1.
Eliminación de la raíz de un montón Suponga que H es un montón con N elementos y suponga que queremos eliminar la raíz R de H. esto se lleva acabo 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) (Re amontonar.) hacer que L se mueva a su sitio adecuado en H para que H sea
finalmente un montón. De nuevo ilustramos la forma en que trabaja el procedimiento antes de definirlo formalmente.
Procedimiento 7.9: INSMONTON (ARBOL, N, ITEM)
Árbol en montón H con N elementos está guardado en el array ARBOL, y se da
un ITEM de información. Este procedimiento inserta ITEM como nuevo de H. PTR
de la posición de ITEM a medida que sube por el árbol, y PAD indica la posición de
padre de ITEM.
1. [Añadir el nuevo nodo a H e inicializar PTR].
Hacer N:=N+1 y PTR:=N.
2. [buscar la posición a insertar ITEM].
Repetir pasos 3 y 6 mientras PTR<1.
3. Hacer PAD:=[PTR/2].[posición del nodo padre].
4. Si ITEM ≤ARBOL [PAD], entonces:
Hacer ARBOL [PTR]:=ITEM y volver.
[Fin del condicional].
5. Hacer ARBOL [PTR]:=ARBOL [PAD].[mover nodo abajo].
6. Hacer PTR:=PAD. [actualizar PTR]
[Fin del bucle del paso 2].
7. [asignar ITEM como la raíz de H].
Hacer ARBOL [1]:=ITEM.
8. Volver.
22
85 70 85 70
55 33 30 65 55 33 30 65 65
15 20 15
15 20 15
85 85
70 85 70
55 33 30 65 33 30 65
15 20 15 15 20 15
Fig. 7-32 reamontonamiento
95
22
22
22
22
23
El bucle del paso 4 se repite que ULT tenga hijo derecho. El paso 8 se encarga del caso
especial en que ULT no tenga hijo derecho, pero si hijo izquierdo (que a de ser el último nodo
de H). La razón de que haya dos sentencias condicionales en el paso 8 es que ARBOL [IZQ]
puede no estar definido cuando IZQ>N.
APLICACIÓN EN ORDENACIÓN.
Suponga un array A de N elementos dados. El algoritmo de ordenación por un montón 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 el elemento de la raíz de H.
Procedimiento 7.11: ELIMONTON (ARBOL, N, ITEM)
Un árbol en memoria H con N elementos se tiene en el array ARBOL,
este procedimiento asigna
La raíz ARBOL [1] de H a la variable ITEM y entonces reamontona
los restantes elementos. La
Variable ULT guarda el valor del último nodo original de H. los
punteros PTR, IZQ y DER dan las
Posiciones de ULT y de sus hijos izquierdo y derecho a medida que
ULT se mueve por el árbol.
1. Hacer ITEM:=ARBOL [1]. [eliminar la raíz de H].
2. Hacer ULT:=ARBOL [N] Y N:=N-1. [quitar el último nodo de H].
3. Hacer PTR:=1, IZQ:=2 y DER:=3. [inicializar punteros],
4. Repetir pasos 5 a 7 mientras DER≤N:
5. Si ULT≥ARBOL [IZQ] y ULT≥ARBOL [DER], entonces: hacer
ARBOL [PTR]:=ULT y volver.
[Fin de condicional].
6. Si ÁRBOL [DER]≤ARBOL [IZQ], entonces:
Hacer ARBOL [PTR]:=ARBOL [IZQ] y PTR:=IZQ Y PTR:=IZQ
Si no:
Hacer ARBOL [PTR]:=ARBOL [DER] y PTR:=DER.
[Fin de condicional].
7. Hacer IZQ :=2*PTR y DER:=IZQ+1.
[Fin del bucle del paso 4].
8. Si IZQ=N y si ULT<ARBOL [IZQ], entonces: hacer
PTR:=IZQ.
9. Hacer ARBOL [PTR]:=ULT
10. Volver.
24
Como la raíz de H siempre contiene el mayor de elemento de H, la fase B elimina los
elementos de A en orden descendente.
Complejidad de la ordenación por montón
Fase A. suponga que H es un montón. Observe que el numero de comparación para encontrar
el sitio adecuado para un nuevo elemento ITEM de H no puede exceder la por fundida de H.
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 la 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 long2 n.
Fase B: suponga que H es 8un árbol completo con m elementos y que los subárboles
izquierdo y derecho de H son montones y que L es la raíz de H. observe que al reamontonar se
efectúan cuatro comparaciones para mover el nodo L un paso abajo en el árbol H. como la
profundidad H no excede a long2 m, al reamontonar 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, los que
requieren el reamontonar n veces, está eliminado por:
Así el tiempo de ejecución de la fase B de la ordenación por montón también es proporcional a
n long2 n.
El tiempo de ejecución para ordenar el array A de n elementos por montón es proporcional a n
long2 n, o sea, ʄ(n)=0 (n long2 n), ya que cada fase requiere un tiempo proporcional a n long2 n. observe
que esto da el peor caso en complejidad para el algoritmo. Esto contrasta con los dos
siguientes algoritmos de ordenación ya estudiados.
Ordenación por el método de la burbuja. El tiempo de ejecución de esta ordenación es 0(n2).
Ordenación rápida. El tiempo medio de ejecución de la ordenación rápida es 0(n long2 n), lo
mismo que la ordenación por montón, pero el tiempo ejecución para el peor caso en la
ordenación rápida es proporcional a 0(n2), igual que por el método de la burbuja.
Longitud de camino; algoritmo de huffman.
Recuerde que un árbol binario extendido o árbol 2 es un árbol binario T en el cada nodo tiene 0
ó 2 hijos. Los nodos con 0 hijos se llaman nodos externos y los nodos con 2 hijos se llaman
nodos internos. En cualquier árbol-2 el número NE de nodos externos es 1 más que el número
N1 de nodos internos, o sea:
25
NE=N1+1
Por ejemplo, para el árbol-2 de la figura 7-33, N1=6 y NE=N1+1=7
FIG. 7-33
Frecuentemente, un algoritmo se puede representar por un árbol-2 T en el que los nodos
internos representan tests y los nodos externos representan acciones. Así, el tiempo de
ejecución del algoritmo dependerá de las longitudes de los caminos en el árbol. Teniendo esto
presente, definimos la longitud de camino externo LE de un árbol-2 T como la suma de todos las
longitudes de camino obtenidos sobre cada camino desde la raíz R de T hasta un nodo
externo. La longitud de camino interna L1 de T se define analógicamente usando los nodos
internos en vez de los externos para el árbol de la figura 7-33.
LE =2+2+3+4+4+3+3=21 y L1=0+1+1+2+3+2=9
Observe que
L1 +2n=9+2. 6=9+12=21=LE
Donde n=6 es el numero de nodos internos. De hecho, la formula
LE=L1+2n
Es cierto que para cualquier árbol-2 con nodos internos.
26
IMPLEMENTACIÓN DEL ALGORITMO DE HUFFMAN
Suponga que queremos implementar el algoritmo de Hoffman en una computadora. Lo primero
necesitaremos un array extra WT para contener los pesos de los nodos; o sea, que nuestro
árbol esté contenido en cuatro arrays lineales en la INFO, WT, IZQ, Y DER. La figura 7-36(a)
muestra como aparecerán inicialmente en la computadora los datos dados. Observe que hay
suficiente sitio para los nodos adicionales. Observe que el valor NULO aparece en los punteros
izquierdo y derecho de los nodos iníciales, ya que estos nodos serán terminales en el árbol
final.
INFO WT IZQ DER
1 A 22 0 0
2 B 5 0 0
3 C 11 0 0
4 D 19 0 0
5 F 2 0 0
6 G 11 0 0
7 H 25 0 0
8 5 0 0
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 0
DISP=9
(a)
Fig. Implantación del algoritmo de Hoffman
Aplicación en codificación
Suponga un conjunto de N nodos A1, A2,…… AN, a ser codificados mediante cadenas de bits.
Una forma de hacerlo es codificar cada uno por una cadena de r bits donde.
2r-1 <n≤2r
Por ejemplo, un conjunto de 48 caracteres frecuentemente es codificado en memoria usando
cadenas de 16 bits. No se puede usar cadenas de 5 bits, ya que 25<48≤2r.
27
Suponga que los elementos no se dan con la misma probabilidad. Entonces se puede
preservar espacio de memoria usando cadenas de longitud variable, de forma que a los
elementos que aparezcan más frecuentemente se le asigna cadenas de menor frecuentes.
Esta sección discute una codificación que usa cadenas de longitud variable y que está basada
en el árbol T de huffman para datos con peso. Elementos U, V, W, X, Y y Z. Observe que cada
arista de un nodo interno hacia su hijo izquierdo esta etiquetada con un 0 y cada arista
derecha con un 1. El código Huffman asigna a cada nodo. Así, el árbol T de la figura 7-37
determinará siguiente código para los nodos externos.
U:00 V:01 W:100 X:1010 Y:1011 Z:11
0 1
0 1 0 1
0 1
0 1
Fig. 7-37
Considere de nuevo los ocho datos A, B, C, D, E, F, G y H del ejemplo 7-24. Suponga que los
pesos representan las probabilidades porcentuales de que seden los elementos. Entonces el
árbol T de longitud de camino con peso mínimo.
A: 00 B: 11011 C: 001 D: 111
E: 11010 F: 010 G: 10 H: 1100
Z
Y X
W
U V
28
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 ordenado de cero o mas arboles
disjuntos T1,T2,……..TM.
0 1
0 1
0 1
A G 0 1
0 1 D
F C 0 1
H
0 1
E B
Fig. 7-38
Los arboles T1, T2,……Tm son llamados subárboles de la raíz 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
árboles generales de la misma forma que para los árboles binarios. En particular, si N es un
nodo con sucesores S1, S2,……Sm, se dice que N es el padre de los si, los si son hijos de N y
los si son hermanos de uno de otros.
El termino <<á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 T; y que T esta ordenado, o
sea, que los hijos de cada nodo N de T tiene un orden específico. Estas dos propiedades no se
requieren siempre para definir un árbol.
29
Representación de árboles en la computadora.
Suponga que T es un árbol general. A menos que se diga lo contario, T se mantendrá en
memoria en términos de una representación enlazada que usa tres arrays paralelos, INFO,
HIJO (o BAJO), 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 aun, RAIZ contendrá la posición de la RAIZ R de T. aunque lo anterior representación
puede parecer artificial, tiene la importante ventaja de que cada nodo R 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 árboles T1, T2,……Tm asumiendo que las raíces de los árboles son hermanas. En este
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.
INFO
HIJO HERM
1
1 5
2 A
2 3 0
3 B
3 15 4
4 C
4 6 16
5
5 13
6 G
6 0 7
7 H
7 11 8
8 J
8 0 0
9 N
9 0 0
10 M
10 0 9
11 L
11 0 0
12 K
12 10 0
13
13 0
14 F
14 0 0
15 E
15 0 14
16 D
16 12 0
(a) RAIZ=2 DISP=13
Fig.7-41
30
Correspondencia entre árboles generales y árboles binarios.
Suponga que T es un árbol general. Podemos asignar un árbol binario único T a T de la forma
siguiente. En primer lugar, los nodos del árbol binario T. sea N un nodo arbitraria del árbol
binario T´ serán los mismos que los del árbol general T, y la raíz de T´ será la raíz de T. sea N
un nodo arbitrario del árbol binario T´. Entonces el hijo izquierdo de N en T´ será el primer hijo
del nodo N en el árbol general T y del hijo derecho de N en T´ será el siguiente hermano de N
en el árbol general T.
Ejemplo 7-27
Considere el árbol general T de la figura 7-39. El lector puede verificar que le binario T´ de la
figura 7-42 corresponde el árbol general T. observe que rotando el dibujo de T´ en sentido
contrario a las agujas de reloj hasta que los aristas que apuntan a los hijos derechos estén
horizontales, obtenemos un dibujo en el que los nodos ocupan las mismas posiciones relativas
que en la figura 7-39.
A
B
C C
F G D
H K
L J M
N
Fig. 7-42 Árbol binario T
31
La representación en la computadora del árbol general T y la representación del
correspondiente árbol binario T´ son exactamente las mismas excepto por los nombres de los
arrays HIJO Y HERM para el árbol general T que corresponden a los nombres de los arrays
IZQ y DER para el árbol binario T. la importancia de esta correspondencia es que ciertos
algoritmos de recorrido, se pueden aplicar a los árboles generales.
Códigos sobre arboles
#include <alloc.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>#include <alloc.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
struct nodoarbol{
struct nodoarbol *izqnodo;
int info;
struct nodoarbol *dernodo;
};
typedef struct nodoarbol NODO;
typedef NODO *ARBOL;
void insertanodonuevo(ARBOL *,int);
void inorden(ARBOL);
void preorden(ARBOL);
void postorden(ARBOL);
void treefree(ARBOL);
main(){
int i;
char newnod,chain[200],elementos;
clrscr();
ARBOL raiz=NULL;
printf(“\nINTRODUSCA UNA CADENA DE CARACTERES\n”);
gets(chain);
elementos=strlen(chain);
for(i=1;iinfo=nuevo;
(*rarbol)->izqnodo=NULL;
(*rarbol)->dernodo=NULL;
}
32
else{printf(“\n memoria no disponible!!!\n”);}
}
else
if(nuevoinfo)
insertanodonuevo(&((*rarbol)->izqnodo),nuevo);
else
if(nuevo>(*rarbol)->info)
insertanodonuevo(&((*rarbol)->dernodo),nuevo);
}
void preorden(ARBOL rarbol){
if(rarbol!=NULL){
printf(” %c “,rarbol->info);
preorden(rarbol->izqnodo);
preorden(rarbol->dernodo);
}
}
void inorden(ARBOL rarbol){
if(rarbol!=NULL){
inorden(rarbol->izqnodo);
printf(” %c “,rarbol->info);
inorden(rarbol->dernodo);
}
}
void postorden(ARBOL rarbol){
if(rarbol!=NULL){
postorden(rarbol->izqnodo);
postorden(rarbol->dernodo);
printf(” %c “,rarbol->info);
}
}
void treefree(ARBOL rarbol){
if(rarbol!=NULL){
treefree(rarbol->izqnodo);
treefree(rarbol->dernodo);
free(rarbol);
}
}
#include <string.h>
#include <ctype.h>
struct nodo
33
{
struct nodo *izq, *der;
char *dato;
};
int cont=0;
struct nodo *crear(char s[30])
{
struct nodo *p;
p=(struct nodo *) malloc (sizeof(struct nodo));
p->izq=NULL;
p->der=NULL;
p->dato=s;
return (p);
} void insertar(struct nodo *raiz, char s[30]) { struct nodo *nuevo,*q,*p; nuevo=crear(s); q=NULL; p=raiz; while(p!=NULL && strcmp( p->dato,nuevo->dato)!=0) {
q=p;
if(strcmp(p->dato,nuevo->dato)<0)
p=p->izq;
else
// if (strcmp(p->dato,nuevo->dato)<0) p=p->der;
}
if(strcmp(p->dato,nuevo->dato)!=0)
if(strcmp(q->dato,nuevo->dato)>0)
q->izq=nuevo;
else
q->der=nuevo;
}
cargar()
{
struct nodo *raiz=NULL;
FILE *archivo;
char caracter[30],espa, tem[30];
int b=0;
34
archivo = fopen("c:\prueba.txt","r");
if (archivo == NULL)
{
printf("\nEl archivo no existe \n\n");
getch();
exit(1);
} else { printf("\nEl contenido del archivo de prueba es \n\n"); while (feof(archivo) == 0) { espa=getc(archivo); if (espa==' ') {
printf("\n");
cont++; }
else
{
printf("%c",espa);
}
b++;
// getch(); //llenar arbol binario /*if (raiz==NULL)
{
raiz=crear(caracter); }
else
{
insertar(raiz,caracter);
}*/
// printf("%c",caracter); }
printf("\nEL NUMERO DE PALABRAS ES: %d",cont);
}
35
getch();
return 0;
} void main() {
//struct nodo *raiz=NULL; char opc;
int dato,x,s;
do
{
clrscr();
gotoxy(27,8);printf("1. Cargar Archivos");
gotoxy(27,10);printf("2. Contar palabras");
gotoxy(27,12);printf("3. Mostrar palabras");
gotoxy(27,20);printf("4. Salir");
gotoxy(27,22);printf("opcion: []\b\b");
opc=getche();
switch(opc)
{
case '1':
clrscr();
cargar();
break; case '2': clrscr();
printf("EL NUMERO DE PALABRAS ES: %d",cont);
getch();
break; case '3':
clrscr();
// orden(raiz);
getch();
break; case '4': break default:
36
clrscr(); gotoxy(31,10);printf("La opcion no existe"); gotoxy(24,12);printf("presione una tecla para continuar..."); getch(); break; } }while(opc!='4');
}
Otro código sobre árbol.
#include <alloc.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
struct nodoarbol{
struct nodoarbol *izqnodo;
int info;
struct nodoarbol *dernodo;
};
typedef struct nodoarbol NODO;
typedef NODO *ARBOL;
void insertanodonuevo(ARBOL *,int);
void inorden(ARBOL);
void preorden(ARBOL);
void postorden(ARBOL);
void treefree(ARBOL);
main(){
int i;
char newnod,chain[200],elementos;
clrscr();
ARBOL raiz=NULL;
printf(“\nINTRODUSCA UNA CADENA DE CARACTERES\n”);
gets(chain);
elementos=strlen(chain);
for(i=1;iinfo=nuevo;
(*rarbol)->izqnodo=NULL;
(*rarbol)->dernodo=NULL;
}
37
else{printf(“\n memoria no disponible!!!\n”);}
}
else
if(nuevoinfo)
insertanodonuevo(&((*rarbol)->izqnodo),nuevo);
else
if(nuevo>(*rarbol)->info)
insertanodonuevo(&((*rarbol)->dernodo),nuevo);
}
void preorden(ARBOL rarbol){
if(rarbol!=NULL){
printf(” %c “,rarbol->info);
preorden(rarbol->izqnodo);
preorden(rarbol->dernodo);
}
}
void inorden(ARBOL rarbol){
if(rarbol!=NULL){
inorden(rarbol->izqnodo);
printf(” %c “,rarbol->info);
inorden(rarbol->dernodo);
}
}
void postorden(ARBOL rarbol){
if(rarbol!=NULL){
postorden(rarbol->izqnodo);
postorden(rarbol->dernodo);
printf(” %c “,rarbol->info);
}
}
void treefree(ARBOL rarbol){
if(rarbol!=NULL){
treefree(rarbol->izqnodo);
treefree(rarbol->dernodo);
free(rarbol);
}
}
Códigos de arboles
38
#include<conio.h>
#include<iostream.h>
main()
{
int lista[4];
int i,res;
int x, z;
printf(“Inserte un numero para convertirlo en binario: “);
scanf(“%d”, &x);
while (x > 2) {
res=0;
if (x-(x/2)==(x/2))
{
for (i=0;i<4;i++)
{
res=(x/2);
if (res-(res/2)==(res/2))
lista[i]=0;
else
lista[i]=1;
}
else
for (i=0;i<4;i++)
{
res=(x/2);
if (res-(res/2)==(res/2))
lista[i]=0;
else
lista[i]=1;
}
}
}
printf(“”);
getche();
getche();
}
39
GRAFOS Y SUS APLICACIONES
Proposición 8.1: un grafo es conexo si y solo si existe un camino simple entre cualesquiera dos nodos
de G.
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
40
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 CAMINOS
Existen 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 adyacencia
Suponga 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 definida como sigue:
aij = 1 si vi es adyacente a vj, o sea, si hay una arista (vi , vj)
0 en caso contrario
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.
41
Matriz de caminos
Sea 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) definida como sigue:
pij 1 si hay un camino desde vi hasta vj
0 en otro caso
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 MINIMOS
Sea 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.
Algoritmo 8.1: (algoritmo de warshall). Un grafo dirigido G con M nodos esta en memoria
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.
42
ALGORITMO DEL CAMINO MÍNIMO
Sea 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), definida como sigue:
w(e) si hay una arista e de vi a vj
wij=
0 si no hay arista de vi a vj
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), donde
qij=longitud del camino mínimo de vi a vj
Ahora 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 vj
Má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. INFINITO
es 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].
43
[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.
a) LISTA DE NODOS. cada elemento de la lista NODO corresponderá a un nodo de G y será un
registro de la forma:
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, …)
b) LISTA DE ARISTAS. cada elemento de la lista ARISTA corresponderá a un arista de G y será un
registro de la forma:
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.
SIG ADY NODO
DEST ENL
44
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,
45
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.
46
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).
47
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 < sobre S definida como sigue:
u<v si existe un camino de u a v.
esta relación tiene las tres propiedades siguientes:
(1) para cada elemento u de S, tenemos que u <u.(irreflexibilidad)
(2) si u<v, entonces v<u. (asimetría).
(3) Si u<v y u<w. (transitividad)
Tal relación < sobre S se llama relación parcial de S, y S con tal relación se llama conjunto
parcialmente ordenado o conjunto po. Así un grafo S sin ciclos se puede considerar un conjunto
parcialmente ordenado.
Por otro lado suponga que S es un conjunto parcialmente ordenado con la ordenación parcial
denotado por <. Entonces S se puede considerar un grafo cuyos nodos son los elemente de S y
cuyas aristas están definidas como sigue:
( u,v) es una arista en S si u<v.
Un conjunto S parcialmente ordenado, considerado como un grafo, no tiene ciclos.
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.
48
Ordenación topológicas de del grafo S.
(a)
(b)
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.
A D G A F E C
E G B A D F C