Download Capitulo VI Árboles y Grafos

Capitulo VI
Árboles y Grafos
Tu vida no cambia cuando cambia tu jefe,
Cuando tus amigos cambian,
Cuando tus padres cambian,
Cuando tu pareja cambia.
Tu vida cambia, cuando tu cambias,
Eres el único responsable por ella.
"examínate.. Y no te dejes vencer"
6.1. Definición
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o
varios nodos.
6.2. Conceptos Básicos
a. Nodo hijo: cualquiera
de los nodos apuntados
por uno de los nodos
del árbol. En el ejemplo,
'L' y 'M' son hijos de 'F'.
b. Nodo padre: nodo que
contiene un puntero al
nodo actual. En el
ejemplo, el nodo 'A' es
padre de 'B', 'C' y 'D'.
Programación II
Ingenieria de Sistemas
79
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
Los árboles con los que trabajaremos tienen otra característica importante: cada nodo
sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto
hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la
apariencia de árboles.
En cuanto a la posición dentro del árbol:
c. Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos
al árbol. En el ejemplo, ese nodo es el 'A'.
d. Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'G', 'H', 'I', 'K', 'L',
'M', 'N' y 'O'.
e. Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que
no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C',
'D', 'E', 'F' y 'J'.
Otra característica que normalmente tendrán nuestros árboles es que todos los nodos
contengan el mismo número de punteros, es decir, usaremos la misma estructura para
todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto
también los programas para trabajar con ellos.
Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir,
que pueden usarse todos, algunos o ninguno de los punteros de cada nodo. Un árbol en
el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.
En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un
nodo cualquiera de la estructura, podemos considerarlo como una estructura
independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un
árbol completo.
Existen otros conceptos que definen las características del árbol, con relación a su
tamaño:
f.
Orden: es el numero potencial de hijos que puede tener cada elemento de árbol.
De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros
dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
g. Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En
el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y
no existen elementos con más de tres hijos.
Programación II
Ingenieria de Sistemas
80
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
h. Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida
en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En
i.
el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como
cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol,
también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la
rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios
capítulos. Estos árboles se conocen también como árboles binarios. Frecuentemente,
aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del
árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo
podremos avanzar en dirección a la raíz, y no sólo hacia las
hojas.
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se
desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol. El nodo
típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque
sólo en el número de nodos.
6.3. Árboles Binarios.
Un arbol binario es un conjunto finito de nodos que puede estar vacío o está compuesto
por un nodo raíz y dos subárboles binarios disjuntos llamados subárbol izquierdo y
subárbol derecho.. Un subárbol izquierdo o derecho puede esta vacío. Es decir en un
árbol binario cada nodo puede tener 0, 1 o 2 nodos hijos.
•
Un Árbol Binario es Completo si es Pleno y todas sus hojas tienen exactamente
la misma profundidad.
•
Un Árbol Binario es Casi-Completo si todos sus niveles están completos,
excepto posiblemente el más profundo, en cuyo caso las hojas ocupan las
posiciones de más a la izquierda.
•
Propiedades de un AB Completo:
o
El número de nodos en el nivel k-ésimo es 2k.
Programación II
Ingenieria de Sistemas
81
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
o
o
•
El número total de nodos desde la raíz hasta el nivel k-ésimo es 2k+1-1,
El número total de nodos internos desde la raíz hasta el nivel k-ésimo es
2k-1.
Notación
o izq(v): Hijo (o subárbol) izquierdo de v
o der(v): Hijo (o subárbol) derecho de v.
6.4. Representación De Árboles Binarios
Estructura estática representada mediante un vector T
Al igual que las listas, los árboles también están constituidos por un conjunto de nodos del
siguiente modo:
La definición en C del nodo es muy parecida a la de listas doblemente encadenadas:
struct nodo
{
int info;
nodo *izq;
nodo *der;
};
typedef nodo *ARBOL;
El movimiento a través de árboles, salvo que implementemos punteros al nodo padre,
será siempre partiendo del nodo raíz hacia un nodo hoja. Cada vez que lleguemos a un
nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al
siguiente nodo.
En general, intentaremos que exista algún significado asociado a cada uno de los
punteros dentro de cada nodo, los árboles que estamos viendo son abstractos, pero las
aplicaciones no tienen por qué serlo.
Ejemplo
a. Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un
sistema operativo. Aunque en este caso se trata de árboles con nodos de dos
tipos, nodos directorio y nodos fichero, podríamos considerar que los nodos hoja
son ficheros y los nodos rama son directorios.
Programación II
Ingenieria de Sistemas
82
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
b. Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo de este
mismo curso, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el
libro sea algo lineal, como una lista, en el que cada capítulo sigue al anterior,
también es posible acceder a cualquier punto de él a través de la tabla de
contenido.
c. También se suelen organizar en forma de árbol los organigramas de mando en
empresas o en el ejército, y los árboles genealógicos.
6.5. Recorridos
El modo evidente de moverse a través de las ramas de un árbol es siguiendo los
punteros, del mismo modo en que nos movíamos a través de las listas. Esos recorridos
dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que
usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante
recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas
una por una, estos recorridos son:
PreOrden u “Orden Previo''
IinOrden u “Orden Interno o Simétrico'"
PostOrden u “Orden Posterior'"
Los cuales se ejemplifican a continuación
Ejemplo:
Ejemplo:
Preorden: <A, B, C>
Inorden: <B, A, C>
Postorden: <B, C, A>
Un recorrido de un árbol (binario) A es una secuencia o lista de nodos que visita todos los
n nodos de A de alguna forma sistemática.
Supongamos que tenemos un árbol binario y queremos recorrerlo por completo.
Partiremos del nodo raíz:
RecorrerArbol(raiz);
Programación II
Ingenieria de Sistemas
83
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo
a la función RecorrerArbol para cada una de las ramas:
void RecorrerArbol(ARBOL raiz)
{
if(a == NULL) return;
RecorrerArbol(raiz->izq);
RecorrerArbol(raiz->der);
}
Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo,
sino el momento que elegimos para procesar el valor de cada nodo con relación a los
recorridos de cada una de las ramas.
La implementación de los tres tipos es la siguiente:
In-orden:
En este tipo de recorrido, el valor del nodo void InOrden(ARBOL raiz)
(raiz == NULL) return;
se procesa después de recorrer la primera { ifInOrden
(raiz->izq);
rama y antes de recorrer la última. Esto
cout<<raiz->info;
tiene más sentido en el caso de árboles
InOrden (raiz->der);
}
binarios,
El siguiente árbol sería recorrido así: 5,15,17,9,3,1,2,19,25,23
1
15
5
2
9
17
19
3
23
25
Si el árbol no esta vació se realizan los siguientes pasos:
1º.- Recorrer en INORDEN el subarbol izquierdo.
2º.- Procesar la Raiz.
3º.- Recorrer en INORDEN el subarbol derecho.
Programación II
Ingenieria de Sistemas
84
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
Pre-orden:
En este tipo de recorrido, el valor del nodo
se procesa antes de recorrer las ramas:
void PreOrden( ARBOL raiz)
{ if ( raiz == NULL) return;
cout<<raiz->info;
PreOrden (raiz->izq);
PreOrden (raiz->der );
}
El árbol sería recorrido así: 1,15,5,9,17,3,2,19,23,25
Si el árbol no esta vacio se realizan los siguientes pasos:
1º.- Procesar Raiz.
2º.- Recorrer en PREORDEN el izquierdo.
3º.- Recorrer en PREORDEN el derecho.
Post-orden:
En este tipo de recorrido, el valor del nodo void PostOrden(ARBOL raiz)
(raiz == NULL) return;
se muestra después de recorrer todas las { ifPostOrden
(raiz->izq);
ramas:
PostOrden (raiz->der);
cout<<raiz->info;
}
El árbol sería recorrido así: 5,17,3,9,15,25,23,19,2,1
Si el árbol no esta vacio se realizan los siguientes pasos:
1º.- Recorrer en POSTORDEN el izquierdo.
2º.- Recorrer en POSTORDEN el derecho.
3º.- Procesar raiz.
Programación II
Ingenieria de Sistemas
85
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
6.6. Árboles Binarios De Busqueda (Abb)
Árbol binario en el cual todos sus nodos cumplen que los nodos de su subárbol
izquierdo tienen un valor inferior a él, y los nodos de su subárbol derecho tienen un
valor superior a él. No existen valores repetidos.
25
12
1
37
30
9
63
29
11
48
40
6.7. Operaciones Sobre Árboles Binarios De Busqueda
De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con
las listas:
•
•
•
•
Creación de un nuevo nodo
Inserción de nuevos nodos
Búsqueda
Eliminación
Programación II
Ingenieria de Sistemas
86
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
Creación De Un Nuevo Nodo
ARBOL getnodo()
{
ARBOL p;
p=(ARBOL)malloc(sizeof(struct tiponodo));
return p;
}
ARBOL creaArbol(int dato)
{
ARBOL p;
p=getnodo();
p->info=dato;
p->der=NULL;
p->izq=NULL;
p->padre=NULL;
return p;
}
void inserta(PN raiz, int dato)
{int sw=0;
PN q;
q=getnodo();
q->info=dato;
q->izq=NULL;
q->der=NULL;
q->padre=raiz;
while(sw==0)
{ if(q->info<raiz->info)
{ if(raiz->izq==NULL)
{raiz->izq=q;
sw=1;
}
else raiz=raiz->izq;
}
if(raiz->izq==NULL)
{raiz->der=q;
sw=1;
}
else raiz=raiz->der;
}
}
Inserción De Un Elemento.
Hacer un procedimiento que reciba como parámetro el puntero a la raíz de un ABB y
el elemento ELEM y lo inserte en su sitio correspondiente.
Programación II
Ingenieria de Sistemas
87
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
void insertar (ARBOL raiz, int elem)
{
if(raiz==NULL)
{
raiz=new tiponodo();
raiz->info=elem;
raiz->izq= NULL;
raiz->der= NULL;
}
else
if( raiz->info==elem )
cout<<”repetido”;
else
if(elem < raiz->info)
insertar (raiz->izq, elem);
else
insertar (raiz->der, elem);
}
Busqueda De Un Elemento.
Hacer un procedimiento que se llama BUSCAR que reciba como parámetro el
puntero raiz de un ABB, un elemento a buscar en la variable ELEM del mismo tipo
que los que forman el arbol y una variable POS en la que devolverá la dirección de
memoria del nodo que contiene el elemento ELEM, en caso de no encontrarse ese
elemento devolverá NULL
void buscar (ARBOL raiz, int elem, int *pos)
{int auxpos;
if (raiz==NULL)
*pos=NULL;
else
if(raiz->info==elem)
*pos =raiz;
else
if(elem < raiz->info)
buscar ( raiz->izq, elem, &auxpos);
else
buscar (raiz->der, elem, &auxpos);
}
Buscar y Eliminar Un Elemento
Para eliminar un determinado elemento de un árbol, primero se debe encontrar dicho
elemento y luego se debe considerar uno de los siguientes casos:
•
Si el nodo buscado es una hoja
•
Si el nodo buscado tiene un hijo
Si el nodo buscado tiene dos hijos
•
Programación II
Ingenieria de Sistemas
88
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
Con 2 hijos: se sustituye el elemento a borrar por su anterior en un recorrido en
INORDEN, y una vez hecho hay que deshacerse de este último. Dentro del
subarbol izquierdo del elemento a suprimir, el que esté más a la derecha es el
que ocupa su posición, ya que es su anterior en un recorrido en INORDEN.
void encontar(ARBOL raiz, int elem)
{
ARBOL p, ant;
ant = NULL ;
p = raiz ;
while (( p-> info != elem ) && ( p<> NULL ) )
{ ant = p ;
if( elem<p-> info) p= p-> izq ;
else p = p-> der ;
}
if(p != NULL )
{
if(p == raiz) suprimir ( raiz ) ;
else
if(p=ant->izq ) suprimir(ant->izq);
else
suprimir ( ant -> der ) ;
}
}
void suprimir ( var p : arbol ) ;
{
ARBOL
temp , ant;
if(p->izq == NULL) p = p->der;
else
if(p -> der == NULL) p = p->izq;
else
{
ant = p;
temp = p->izq;
while ( temp -> der != NULL )
{
ant = temp;
temp = temp->der;
}
p -> info = temp->info ;
if(ant==p) ant->izq = temp->izq;
else ant->der = temp->izq;
}
}
Programación II
Ingenieria de Sistemas
89
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
6.8. Árboles ordenados
Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia
ordenada sigui}o uno de los recorridos posibles del árbol: inorden, preorden o postorden.
En estos árboles es importante que la secuencia se mantenga ordenada aunque se
añadan o se eliminen nodos.
Existen varios tipos de árboles ordenados, que veremos a continuación:
•
Árboles binarios de búsqueda (ABB): son árboles de orden 2 que mantienen una
•
secuencia ordenada si se recorren en inorden.
Árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles
•
de cada rama para cualquier nodo no difieren en más de 1.
Árboles perfectamente equilibrados: son árboles binarios de búsqueda en los que
el número de nodos de cada rama para cualquier nodo no defieren en más de 1.
Son por lo tanto árboles AVL también.
•
•
Árboles 2-3: son árboles de orden 3, que contienen dos claves en cada nodo y que
están también equilibrados. También generan secuencias ordenadas al recorrerlos
en inorden.
Árboles-B: caso general de árboles 2-3, que para un orden M, contienen M-1
claves.
Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las
inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama.
Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de
árboles.
•Añadir o insertar elementos.
•Buscar o localizar elementos.
•Borrar elementos.
•Moverse a través del árbol.
•Recorrer el árbol completo.
Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que
estemos implementando, de modo que por ahora los pasaremos por alto y nos
centraremos más en el modo de recorrer árboles.
Programación II
Ingenieria de Sistemas
90
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
6.9. Grafos
6.9.1. Definiciones Básicas
Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un
subconjunto de VxV (conjunto de aristas).
Gráficamente representaremos los vértices por puntos y las aristas por líneas que los
unen.
Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices.
Llamaremos orden de un grafo a su número de vértices, |V|.
Si |V| es finito se dice que el grafo es finito. En este curso estudiaremos los grafos finitos,
centrándonos sobre todo en grafos no dirigidos. También supondremos, a no ser que se
diga lo contrario, que entre dos vértices hay, como mucho, una arista y que toda arista
une dos vértices distintos.
Aristas
Si la arista carece de dirección se denota indistintamente {a,b} o {b,a}, si}o a y b los
vértices que une.
Si {a,b} es una arista, a los vértices a y b se les llama sus extremos.
Vértices
Dos vértices v, w se dice que son adyacentes’ si {v,w}∈A (o sea, si existe una arista entre
ellos)
llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que
un vértice es ‘par’ o ‘impar’ según lo sea su grado.
Programación II
Ingenieria de Sistemas
91
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
Caminos
Sean x, y ∈ V, se dice que hay un camino en G de x a y si existe una sucesión finita no
vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso
ƒ
ƒ
x e y se llaman los extremos del camino
El número de aristas del camino se llama la longitud del camino.
ƒ
Si los vértices no se repiten el camino se dice propio o simple.
ƒ
Si hay un camino no simple entre 2 vértices, también habrá un camino simple
ƒ
entre ellos.
Cu&&o los dos extremos de un camino son iguales, el camino se llama circuito o
-
camino cerrado.
Llamaremos ciclo a un circuito simple
-
Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos.
Todo vértice es accesible respecto a si mismo
Ejemplos De Grafos
1.- Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo
llamaremos k-regular.
Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el
tercero no es regular
2.- Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos
de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
Programación II
Ingenieria de Sistemas
92
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
3.- Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo
con n vértices se denota Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6
Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar conectado
con todos los otros vértices.
Un grafo regular no tiene por qué ser completo.
4.- Un grafo bipartido regular se denota Km,n donde m, n es el grado de cada conjunto
disjunto de vértices.
Programación II
Ingenieria de Sistemas
93
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
Representacion De Grafos
Programación II
Ingenieria de Sistemas
94
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
EJERCICIOS
1. Hacer un seguimiento del siguiente algoritmo con el árbol que se da.
void ejercicio(ARBOL raiz)
{
if( raiz!=NULL)
{
if( raiz->info % 2 == 0)
cout<<raiz->info;
ejercicio(raiz->izq);
ejercicio(raiz->der);
if(raiz->info>0)
cout<<raiz->info;
}
}
1
2
9
3
8
10
15
11
4
16
5
12
6
13
7
14
¿Obtendriamos: 2, 4, 4, 6, 7, 6, 5, 3, 8, 8, 2, 10, 12, 14, 14, 13, 12, 11, 10, 16, 16, 15,
9,1?
Programación II
Ingenieria de Sistemas
95
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia
2.
Dada la siguiente secuencia de números: 25, 12, 1, 9, 37, 30, 63, 48, 29, 11,
4
construir el ABB que genera dicha secuencia si el orden en el que entran en el
árbol es el que se establece.
25
12
1
37
30
9
63
29
11
48
40
3. Dado un árbol binario de busqueda , que contiene el nombre, el apellido y la
edad de un grupo de personas , ordenados por edades .
Se pide :
Hacer un algoritmo que visualice los datos de las personas de mayor a menor
edad .
4. Dado un ABB que contiene números enteros .
Se pide :
- Hacer un procedimiento que reciba como parámetros: el puntero a raiz del
arbol , y un número entero . El procedimiento debe buscar el elemento NUM y
una vez encontrado visualizar todos sus antecesores (los anteriores).
Programación II
Ingenieria de Sistemas
96
Lic. Katya Pérez Martínez
Lic. Gladys Chuquimia