Búsqueda en anchura y búsqueda en profundidad para árboles

Búsqueda en anchura y búsqueda en profundidad para árboles

Publicado el 16 septiembre, 2011 por meta

En programación es muy común usar Estructuras de Datos para poder ordenar y almacenar información. Ésta puede ser desde primitivas como números enteros hasta cadenas de texto hasta tipos definidos por el programador como productos, personas o estados de un juego.
Existen diversas Estructuras de Datos entre las cuales están los arrays, las listas, las colas, las pilas, los conjuntos, los árboles, los grafos… En esta entrada vamos a centrarnos en los árboles y en los dos algoritmos de búsqueda más sencillos que podemos usar en ellos: la búsqueda en anchura y la búsqueda en profundidad.
Comencemos entonces.
Un árbol es una estructura de datos compuesta por nodos y ramas. Un nodo es un elemento, el dato que queremos organizar. Una rama es una unión dirigida entre un par de nodos. Un nodo se dice que es padre si existe alguna rama que le una con otro nodo, del mismo modo que un nodo es hijo si existe una rama que una a otro nodo con éste. Decimos que un nodo es hoja si no tiene hijos. Un grafo es una generalización de un árbol. Para entenderlo mejor, consultemos la siguiente figura:

Como toda estructura de datos, los árboles tienen tres operaciones básicas:

• Inserción de nuevos elementos.
• Eliminación de elementos existentes.
• Búsqueda de un elemento en la estructura.

Existen otras operaciones como la ordenación y la mezcla de dos estructuras de datos del mismo tipo, pero no vamos a tratarlas aquí.
Durante el resto de la entrada vamos a utilizar el siguiente árbol:

Comenzamos por tanto, construyendo los tipos de datos necesarios para representar este árbol. En esta ocasion voy a elegir Java como lenguaje de programación por disponer de tipos de datos predefinidos que nos van a ayudar, ya que por ejemplo en C tendríamos que crearnos diversos tipos de datos (los cuales veremos más adelante) que pertenecería a una entrada sobre estructuras de datos y su construcción, y no de algoritmos de búsqueda.
Lo primero será crear nuestra clase NodoArbol, la cual va a representar un nodo de nuestro árbol (duh). En nuestro caso vamos a usar como elemento de cada nodo un carácter, para hacerlo simple. Sin embargo podríamos también usar otras primitivas o nuestros propias clases. Y además vamos a aceptar que cada nodo pueda tener entre 0 y N hijos, de modo que querremos algún tipo de lista dinámica para almacenarlo (ya que no sabemos inicialmente cuántos hijos habrá por nodo). El código de la clase comienza siendo el siguiente:

1	public class NodoArbol {

2

3	private char elemento;

4	private List<NodoArbol> hijos;

5

6	public NodoArbol(char elemento) {

7	this.elemento = elemento;

8	hijos = new ArrayList<NodoArbol>();

9

}

10

11	public char getElemento() {

12	return elemento;

13

}

14

15	public void addHijo(NodoArbol hijo) {

16	hijos.add(hijo);

17

}

18

19	public List<NodoArbol> getHijos() {

20	return hijos;

21

}

22

23	public boolean esNodoHoja() {

24	return hijos.size() > 0;

25

}

26

}

Además de los atributos que hemos mencionado, añadimos funcionalidad para obtener el elemento del nodo actual y los hijos de dicho nodo, además de la opción de insertar hijos al nodo y de consultar si es un nodo hoja.
Ahora crearemos nuestra clase principal, desde la que vamos a ejecutar las pruebas:

1	public class ArbolesBusquedas {

2

3	public static void main(String[] args) {

4	// crear nodos

5	NodoArbol raiz = new NodoArbol('v');

6

7	// primer nivel

8	NodoArbol nivel1hijo0 = new NodoArbol('i');

9	NodoArbol nivel1hijo1 = new NodoArbol('o');

10	NodoArbol nivel1hijo2 = new NodoArbol('r');

11

12	// segundo nivel

13	NodoArbol nivel2hijo0 = new NodoArbol('d');

14	NodoArbol nivel2hijo1 = new NodoArbol('c');

15	NodoArbol nivel2hijo2 = new NodoArbol('n');

16	NodoArbol nivel2hijo3 = new NodoArbol('r');

17	NodoArbol nivel2hijo4 = new NodoArbol('e');

18	NodoArbol nivel2hijo5 = new NodoArbol('e');

19

20	// tercer nivel

21	NodoArbol nivel3hijo0 = new NodoArbol('a');

22	NodoArbol nivel3hijo1 = new NodoArbol('s');

23	NodoArbol nivel3hijo2 = new NodoArbol('c');

24	NodoArbol nivel3hijo3 = new NodoArbol('u');

25	NodoArbol nivel3hijo4 = new NodoArbol('n');

26	NodoArbol nivel3hijo5 = new NodoArbol('t');

27	NodoArbol nivel3hijo6 = new NodoArbol('s');

28

29	// construir el arbol

30	raiz.addHijo(nivel1hijo0);

31	raiz.addHijo(nivel1hijo1);

32	raiz.addHijo(nivel1hijo2);

33

34	// primer nivel

35	nivel1hijo0.addHijo(nivel2hijo0);

36	nivel1hijo0.addHijo(nivel2hijo1);

37	nivel1hijo1.addHijo(nivel2hijo2);

38	nivel1hijo2.addHijo(nivel2hijo3);

39	nivel1hijo2.addHijo(nivel2hijo4);

40	nivel1hijo2.addHijo(nivel2hijo5);

41

42	// segundo nivel

43	nivel2hijo0.addHijo(nivel3hijo0);

44	nivel2hijo0.addHijo(nivel3hijo1);

45	nivel2hijo2.addHijo(nivel3hijo2);

46	nivel2hijo2.addHijo(nivel3hijo3);

47	nivel2hijo4.addHijo(nivel3hijo4);

48	nivel2hijo4.addHijo(nivel3hijo5);

49	nivel2hijo5.addHijo(nivel3hijo6);

50

}

51

}

El código de arriba crea el árbol que hemos visto en la figura superior. Todos estamos de acuerdo en que quizá no es la forma elegante de crear el árbol y probablemente existen formas más cortas y eficientes de hacerlo. Sin embargo prefiero mantener la claridad en la explicación para que no se me pierda nadie.
Lo siguiente que vamos a hacer es crear las búsquedas en anchura y profundidad. Pero antes de crearlas tendremos que saber qué hace cada una, ¿no?

Búsqueda en anchura

La busqueda en anchura (o búsqueda en amplitud), llamada Breadth First Search en inglés, es un algoritmo usado para recorrer o buscar elementos en una estructura de datos como los árboles y los grafos (aunque nosotros nos centremos ahora mismo en los árboles). Pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en ir visitando todos los nodos de un nivel antes de proceder con el siguiente nivel tal y como mostramos en la siguiente figura (los números en naranja indican el orden de exploración de los nodos):

De modo que lo primero que hará será visitar la raíz, luego los hijos de la raíz, luego los hijos de cada uno de estos hijos y así sucesivamente. ¿Cómo hacemos esto para que funcione, pensaréis? La respuesta es sencilla: usar una cola como estructura de datos auxiliar.
Una cola es una estructura FIFO (First In, First Out) en la que sólo disponemos de dos operaciones: insertar al final de la cola y extraer del principio de la cola. Por tanto, el elemento que entra el último será el último en salir. Como hemos elegido Java como lenguaje de programación para esta entrada, disponemos ya de la interfaz Queue<E> y la clase LinkedList<E> que nos van a brindar la funcionalidad de las colas sin programar nada.
Nuestro procedimiento va a ser el siguiente:

• Insertamos la raíz en la cola, como preparación.
• Si la cola no está vacía, sacamos el primer elemento (el primer nodo que haya en la cola) y comprobamos si es el elemento que estamos buscando. Si es igual entonces acabamos, si no es igual obtenemos todos los hijos de dicho nodo y los insertamos en la cola (recordamos que las inserciones son por el final).
• Repetimos hasta que hayamos encontrado el elemento o la cola sea vacía.
• Finalizamos.

Como la búsqueda se realiza desde un NodoArbol (la raíz), cabe pensar que la función de búsqueda debe ser parte de esta clase. Por tanto, agreamos la siguiente función a la clase NodoArbol:

1	public boolean busquedaAnchura(char c) {

2	Queue<NodoArbol> colaAuxiliar = new LinkedList<NodoArbol>();

3	colaAuxiliar.add(this);

4

5	while(colaAuxiliar.size() != 0) {

6	NodoArbol cabeza = colaAuxiliar.poll();

7	System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros

8	if(cabeza.getElemento() == c)

9	return true;

10

else

11	for(NodoArbol hijo : cabeza.getHijos())

12	colaAuxiliar.add(hijo);

13

}

14	return false;

15

}

Como hemos dicho previamente, lo primero es insertar la raíz en la cola para que tengamos algo por donde empezar. A partir de entonces, si existe algo en la cola cogemos la cabecera (la función poll() devuelve la cabeza y la elimina de la cola). Ahora comprobamos si el elemento interno de este nodo es el que estamos buscando (recordemos que se debe usar la función .equals() para comparar objetos no primitivos). Si el elemento es el que buscamos entonces retornamos de la función positivamente, si no lo es entonces cogemos todos los hijos de dicho nodo y los insertamos en la cola para hacer una iteración más.
Llega el momento de probar que lo que hemos hecho funciona como esperamos. Los siguientes códigos se deben insertar al final del main de la clase ArbolesBusquedas y lo que obtendríamos al ejecutar está marcado como output. Comenzamos probando que encontramos la raíz:

1	System.out.println(raiz.busquedaAnchura('v'));

2

3

/* output

4

v

5

true

6

*/

Comprobamos que encontramos la letra ‘u’:

1	System.out.println(raiz.busquedaAnchura('u'));

2

3

/* output

4

v

5

i

6

o

7

r

8

d

9

c

10

n

11

r

12

e

13

e

14

a

15

s

16

c

17

u

18

true

19

*/

Comprobamos que no encontramos la letra ‘z’:

1	System.out.println(raiz.busquedaAnchura('z'));

2

3

/* output

4

v

5

i

6

o

7

r

8

d

9

c

10

n

11

r

12

e

13

e

14

a

15

s

16

c

17

u

18

n

19

t

20

s

21

false

22

*/

¿Qué pasa si buscamos la letra ‘c’? Existen varias letras ‘c’, ¿cuál encontrará? Probemos:

1	System.out.println(raiz.busquedaAnchura('c'));

2

3

/* output

4

v

5

i

6

o

7

r

8

d

9

c

10

true

11

*/

Entonces, la búsqueda en anchura va a encontrar el elemento de menor profundidad del árbol, si es que existe.
Ventajas de la búsqueda en anchura:

• Es completo: siempre encuentra la solución si existe.
• Es óptimo si el coste de cada rama es constante: en Inteligencia Artificial puede que cada nodo sea un estado de un problema, y que unas ramas tengan un coste diferente a las demás.

Inconvenientes de la búsqueda en anchura:

• Complejidad exponencial en espacio y tiempo (incluso peor la del espacio que la del tiempo).

Búsqueda en profundidad

La busqueda en profundidad, llamada Depth First Search en inglés, es un algoritmo usado para recorrer o buscar elementos en un árbol o un grafo y pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en visitar todos los nodos de forma ordenada pero no uniforme en un camino concreto, dejando caminos sin visitar en su proceso. Una vez llega al final del camino vuelve atrás hasta que encuentra una bifurcación que no ha explorado, y repite el proceso hasta acabar el árbol (esto se conoce como backtracking). En la siguiente figura mostramos el orden de visita, siendo los números en naranja dicho orden:

Para poder programar dicho comportamiento vamos a apoyarnos en una estructura de datos llamada pila. Una pila es una estructura de datos LIFO (Last In, First Out) en la que sólo disponemos de dos operaciones: apilar y desapilar. Apilar añade el elemento en la cabeza y desapilar lo extrae y elimina. Por tanto, el primer elemento que entre se quedará en el fondo y será el último en visitarse. Igual que con las colas, Java nos brinda la clase Stack<T> que nos va a servir el comportamiento deseado.
Nuestro procedimiento, por tanto, será:

• Insertamos la raíz en la pila, para preparación.
• Mientras haya algo en la pila, desapilamos la cabeza. Comprobamos si es el elemento que buscamos y si lo es acabamos. Si no lo es, cogemos todos los hijos de dicho nodo y los apilamos todos.
• Repetimos hasta que encontremos el elemento buscado o la pila esté vacía.
• Finalizamos.

Por tanto, añadimos la siguiente función a la clase NodoArbol:

1	public boolean busquedaProfundidad(char c) {

2	Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();

3	pilaAuxiliar.push(this);

4

5	while(pilaAuxiliar.size() != 0) {

6	NodoArbol cabeza = pilaAuxiliar.pop();

7	System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros

8	if(cabeza.getElemento() == c)

9	return true;

10

else

11	for(int i = cabeza.getHijos().size() - 1; i >= 0; i--)

12	pilaAuxiliar.push(cabeza.getHijos().get(i));

13

}

14	return false;

15

}

Pregunta: ¿por qué no hemos hecho el bucle for igual que en la búsqueda en anchura? Recordemos que una pila es una estructura en la que lo último que entra es lo primero que sale. Nosotros queremos ir explorando el árbol por el camino de más a la izquieda, tal y como mostrábamos en la figura superior. Si usáramos el mismo bucle for que en la búsqueda en anchura, estaríamos haciendo la búsqueda por la derecha, puesto que el elemento de la cabeza de la pila siempre sería el hijo de más a la derecha del nodo consultado.
Comprobemos entonces que funciona. Igual que antes, pondremos los siguientes códigos al final de la creación del árbol en el main y al ejecutar veremos lo que está marcado como output:
Comprobamos que encuentra la raíz:

1	System.out.println(raiz.busquedaProfundidad('v'));

2

3

/* output

4

v

5

true

6

*/

Comprobamos que encuentra la letra ‘u’:

1	System.out.println(raiz.busquedaProfundidad('u'));

2

3

/* output

4

v

5

i

6

d

7

a

8

s

9

c

10

o

11

n

12

c

13

u

14

true

15

*/

Comprobamos que no encuentra la letra ‘z’:

1	System.out.println(raiz.busquedaProfundidad('z'));

2

3

/* output

4

v

5

i

6

d

7

a

8

s

9

c

10

o

11

n

12

c

13

u

14

r

15

r

16

e

17

n

18

t

19

e

20

s

21

false

22

*/

¿Qué pasa si buscamos la letra ‘c’?

1	System.out.println(raiz.busquedaProfundidad('c'));

2

3

/* output

4

v

5

i

6

d

7

a

8

s

9

c

10

true

11

*/

Como vemos, la búsqueda en profundidad busca el elemento por el camino de máxima profundidad y cuando éste se acaba, vuelve al último nodo que había visitado con caminos posibles (caminos abiertos).
Ventajas de la búsqueda en profundidad:

• Es completa si no existen ciclos repetidos.
• Tiene menor complejidad en espacio que la búsqueda en anchura, porque solo mantenemos en memoria un camino simultáneamente.

Inconvenientes de la búsqueda en profundidad:

• No es óptima.
• Puede no encontrar la solución aunque exista si hay caminos infinitos. Luego no es completa.

Quizá el ejemplo anterior no sea demasiado ilustrativo para el caso de la letra ‘c’. Veamos el siguiente árbol, que está simplificado pero nos ayudará a entenderlo mejor:

Ahora veamos qué pasa si buscamos con ambos algoritmos el elemento cuyo carácter es una ‘c’.
Comenzamos con la búsqueda en anchura:

Ahora la búsqueda en profundidad:

¿Qué vemos aquí? La búsqueda en anchura ha visitado sólo 3 nodos hasta encontrar la solución mientras que la búsqueda en profundidad ha visitado 11 nodos para encontrar la suya. ¿Significa esto que la búsqueda en anchura es mejor que la búsqueda en profundidad? Miremos un último ejemplo:

Buscamos el elemento cuyo carácter es ‘c’ y los dos recorridos serán los que se ven en la siguiente figura (click para agrandar):

¿Y ahora? ¿Cuál es mejor? Parece que la búsqueda en profundidad.
Concluiremos con que en realidad no hay una búsqueda no informada mejor o peor, porque dependen mucho de la posición de nuestra solución dentro del árbol (entendemos solución por lo que estamos buscando). ¿Cómo solucionamos esto, entonces? La respuesta es usar búsquedas informadas (usando heurísticas). Sin embargo es un campo muy amplio y en esta entrada no vamos a tratarlo.
Por tanto, podemos generalizar el algoritmo que usaremos en dichas búsquedas como lo siguiente:

1	listaAbierta <- raiz

2

REPETIR

3	SI esVacia(listaAbierta) ENTONCES

4	DEVOLVER(negativo)

5

6	nodo <- primero(listaAbierta)

7	SI esNodoMeta(nodo) ENTONCES

8	DEVOLVER(positivo)

9

10	listaSucesores <- expandir(nodo)

11	PARA CADA n : sucesores HACER

12	insertar(n, listaAbierta, ordenInsercion)

13

FIN

Donde la lista abierta podemos generalizarla como una lista enlazada simple y el orden de inserción es al inicio, al final u otro lugar dependiendo de la búsqueda que estemos haciendo. De esta forma tendríamos una forma general de realizarlas. Si esto fuera Ingeligencia Artificial y no una simple búsqueda de un elemento, cabria añadir una instrucción más por cada sucesor y además devolver el nodo una vez encontrado, y no un valor booleano.

Algunos usos de las búsquedas

Antes de acabar voy a hablar muy brevemente sobre las aplicaciones de estas búsquedas.
La aplicación básica es la de encontrar un elemento en concreto dentro de nuestra estructura de datos, como hemos visto.
Por su parte, la Inteligencia Artificial trata de, dado un problema, hayar su solución. Supongamos un laberinto. Nuestro agente inteligente debe encontrar la salida. Si esta búsqueda de la salida la realiza con búsquedas no informadas (sin heurísticas) puede acabar en ciclos infinitos (en caso de la búsqueda en profundidad) o tardar muchísimo tiempo (en la búsqueda en anchura siempre encontramos la solución más corta si existe, pero esto puede ser en la parte inferior derecha del árbol, que es lo último en visitar). También existen modificaciones de dichos algoritmos como la búsqueda en profundidad limitada (para evitar ciclos infinitos).
Para solventar estos problemas surgieron las búsquedas informadas que usan heurísticas. Éstas, antes de explorar un nuevo nodo evaluan cuál de los hijos le ofrece mayor recompensa. Esta forma de decidir qué nodo es mejor depende de la heurística usada, que pueden ser muy variadas e incluso ineficientes.
Por ejemplo la heurística lo que más me acerque a la meta puede parecer una gran idea. Pero puede traer un inconveniente: ¿y si hay una pared desde donde estoy hasta la meta? Sí, me queda una casilla para llegar, ¡pero no puedo atravesar el muro!
Esto es solamente un ejemplo y haría falta mucha explicación para cubrir los casos y sobre todo hacer una comparativa en complejidad espacial y temporal de cada una de las búsquedas. Sin embargo como idea inicial de posibles usos de las búsquedas vistas durante la entrada es suficiente.
¡Espero que haya sido de utilidad para los lectores!

inShare1

Esta entrada fue publicada en Programación y etiquetada como algoritmo, amplitud, anchura, arbol, arbol de busqueda, bfs, breadth first search, busqueda, cola, depth first search, dfs, estructuras de datos, grafos, java, pila, profundidad.

Post navigation

← Rogue AP con karmetasploit

Obteniendo información de dispositivos Android con Metasploit →

11 Respuestas a Búsqueda en anchura y búsqueda en profundidad para árboles

1. Luismi dijo:

   16 septiembre, 2011 at 10:30

   Muy bien explicado la verdad, creo que se entiende fácilmente.
   Por cierto, creo que tienes un error en la numeración del ejemplo de búsqueda en profundidad (letras n, r, t)
   Saludos!
   

   Responder
   • meta dijo:

     16 septiembre, 2011 at 13:44

     Tienes razón, había una errata en la numeración de la búsqueda en profundidad. ¡Ya está solucionado!
     ¡Muchas gracias!
     

     Responder
2. hdfc bank netbanking dijo:

   30 marzo, 2012 at 2:51

   Keep the religion, my Online companion. You are a first-class author and deserve for being listened to.
   

   Responder
3. kx27 dijo:

   29 julio, 2012 at 22:37

   muchas gracias, esta muy bien explicado, creo que hasta mejor que mi profe
   

   Responder
4. Luis Alfredo S. dijo:

   12 septiembre, 2013 at 20:04

   Hola me podrias explicar esta linea de código en tu función para recorrido en anchura?
   Queue colaAuxiliar = new LinkedList();
   Lo que pasa es que lo estoy migrando a c# y no me permite crear la Queue con el constructor de la lista enlazada.
   y también esta porfavor, l
   for(NodoArbol hijo : cabeza.getHijos())
   

   Responder
5. andres dijo:

   2 octubre, 2013 at 6:05

   muchas gracias x fin logre entender mejor los grafos
   

   Responder
6. eduardo dijo:

   11 octubre, 2013 at 5:35

   oye de casualidad podrias mandar el codigo en orden …
   

   Responder
7. javier dijo:

   15 octubre, 2013 at 15:13

   Puedes enviarme el codigo completo y en que lenguaje esta programado.. GRACIAS..
   Es para revisarlo y entenderlo mejor. GRACIAS.
   

   Responder
8. José Carlos Ramírez Moreno dijo:

   16 octubre, 2013 at 7:15

   Muy bien explicado, lo probé y funciono. Pero aún no entiendo algo, en los métodos donde se hace la búsqueda: como es que para de imprimir. ¿Cómo rompe el ciclo while al encontrar el valor que buscamos?
   Espero me puedas ayudar. Gracias.
   

   Responder
9. Carlos Medina dijo:

   5 diciembre, 2013 at 7:19

   Muy bien explicado, me podrias mandar el código completo porfa, te lo voy agradecer mucho
   salu2
   

   Responder
10. pablo dijo:

    11 diciembre, 2013 at 12:35

    hola!! a mi me marca una Exception un NullPointer Exception para ser exactos, no entiendo el por que me marca, me muestra el addHijo espero me puedan ayudar
    

    Responder

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

Nombre *

Correo electrónico *

Web

Comentario

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>