Todo se puede aprender
...si se quiere.
Home » , » Algoritmos de Búsqueda en Anchura (BFS) y Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Anchura (BFS) y Búsqueda en Profundidad (DFS)

29 de abril de 2014 | 21:16

algoritmos
En anteriores publicaciones pudimos aprender algunas cosas elementales acerca de la teoría de grafos. En esta oportunidad aprenderemos a realizar Algoritmos de Búsqueda en Anchura (BFS, por sus siglas en inglés: “Breadth-First Search”) y de Búsqueda en Profundidad (DFS, por sus siglas en ingles: “Depth-First Search”).

Ambas técnicas constituyen métodos sistemáticos para visitar todos los vértices y arcos del grafo, exactamente una vez y en un orden específico predeterminado, por lo cual podríamos decir que estos algoritmos simplemente nos permiten hacer recorridos controlados dentro del grafo con algún propósito.

Siendo la búsqueda una de las operaciones más sencillas y elementales en cualquier estructura de datos, se han estandarizado el uso de estos algoritmos para ello, por lo que se conocen como algoritmos de búsqueda. Sin embargo, es importante resaltar que pueden utilizarse para muchísimas otras operaciones con grafos que no necesariamente incluyan la búsqueda de algún elemento dentro del grafo.

Manejo de grafos

El recorrido que se hace con este tipo de algoritmos es a cíclico por lo que se dice que el recorrido es de árbol, sin embargo la entrada sigue siendo un grafo.

Un árbol es un grafo conexo a cíclico, y para cada par de vértices distintos sólo existirá un único camino. Un árbol está conformado por vértices (nodos) y arcos (aristas), al igual que un grafo. Si existe un camino de longitud 1 entre dos nodos en un árbol uno de ellos será el padre y el otro será el hijo. Los vértices pueden ser de tres tipos:


  • Raíz: Es el único nodo que no tiene padre.
  • Nodo Interno: Es aquel que posee al menos un hijo.
  • Nodo Externo: Es aquel que no tiene hijos, también se le denomina hoja.
grafo

Haremos nuestra implementación en el lenguaje de programación C++, utilizando Visual Studio 10.0. Lo primero que hay que hacer tanto en BFS como en DFS es crear toda la estructura base que nos permitirá manejar el grafo. Utilizaremos listas de adyacencia para representar el grafo, en este caso trabajaremos con un grafo no dirigido y no ponderado. En el tutorial antes mencionado se explica en detalle las consideraciones base para manejar el grafo, puedes consultarlo como referencia para la creación de esta primera parte del código.


En ambos casos el recorrido se inicia desde un nodo raíz, elegido arbitrariamente (En el caso de que el grafo sea un árbol, la raíz ya está determinada). También se debe indicar el elemento que ha de ser buscado.

Es fundamental marcar cada uno de los nodos que han sido visitados, de lo contrario podremos repetir los nodos una y otra vez, con lo cual no podremos salir nunca de nuestro algoritmo. Esta característica es lo que garantiza precisamente que el recorrido sea a cíclico. Para ello usaremos un vector de booleanos, que inicializamos en falso, y la declararemos como una variable global.

vector<bool> mark;
mark = vector<bool>(graph.V, false);

La diferencia entre BFS y DFS es el orden en que ha de recorrerse el grafo, para algunos problemas no tiene ninguna relevancia cual de los dos algoritmos ha de aplicarse, pero en otros casos esta elección es crucial.

Algoritmo de Búsqueda en Anchura (BFS)

La búsqueda en anchura supone que el recorrido se haga por niveles. Para entender más fácilmente de que se trata, hemos indicado en la siguiente imágen un grafo ejemplo en donde cada color representa un nivel, tomando como raíz o nodo inicial el que tiene el número 1. El recorrido se hará en orden numérico de forma consecutiva hasta llegar al nodo número 7.
Algoritmo de Búsqueda en Anchura (BFS)
La estrategia que usaremos para garantizar este recorrido es utilizar una cola que nos permita almacenar temporalmente todos los nodos de un nivel, para ser procesados antes de pasar al siguiente nivel hasta que la cola esté vacía.

queue<State> q;
q.push(State(raiz));
mark[raiz] = true;

Inmediatamente después de declarar nuestra estructura de cola, agregamos el nodo raíz para poder iniciar el proceso de búsqueda. Esto se hace porque necesitamos tener al menos un elemento en nuestra cola, dado que la condición de salida es que la cola esté vacía. Luego marcamos el nodo raíz como visitado.

while(!q.empty())
{
    State st = q.front();
    q.pop();
    if (st.node == nodo){
        printf("'%d'n",nodo);
        return;
    }else printf("%d ",st.node);

    int T = (int)graph.G[st.node].size();
    for(int i = 0; i < T; ++i)
    {
        if (!mark[graph.G[st.node][i].node])
        {
            mark[graph.G[st.node][i].node] = true;
            q.push(State(graph.G[st.node][i].node));
        }
    }
}

Cada vez que visitamos un nodo, lo desencolamos e imprimimos por pantalla el valor del nodo para ir indicando el recorrido. Luego agregamos a la cola todos los nodos del siguiente nivel y los marcamos como visitados antes de comenzar el ciclo de nuevo, en el que procesaremos estos nuevos nodos que hemos agregado a la cola.

Si encontramos el elemento buscado, la función BFS retornará al “main” e imprimirá entre comillas simples el valor del elemento buscado.

Podríamos hacer otro tipo de mensaje para indicar que el elemento ha sido encontrado, calcular el número de nodos que fueron visitados o incluso generar un mensaje especial en el caso de que el elemento no haya sido encontrado. Por el momento la función ha quedado lo más sencilla posible para enfocarnos únicamente en cómo hacer el recorrido.

Dejo un link para mas información: Algoritmo de Búsqueda en Anchura (BFS)

Algoritmo de Búsqueda en Profundidad (DFS)

En el caso de la búsqueda en profundidad lo que se quiere es recorrer desde la raíz hasta los nodos extremos u hojas por cada una de las ramas. En este caso los niveles de cada nodo no son importantes. En la siguiente imagen podemos ver el orden en que se hace el recorrido desde el nodo raíz, indicado con el número uno, hasta el nodo número siete.
Algoritmo de Búsqueda en Profundidad (DFS)
La forma más intituiva de hacer este algoritmo es de forma recursiva, de lo contrario tendríamos que usar en lugar de una cola una pila, pero con la recursión nos ahorramos la necesidad de utilizar esta estructura explícitamente y en lugar de ello nos valemos de la pila de recursión.

En este caso pasaremos por parámetro el nodo a buscar y el nodo actual (El nodo que esta siendo visitado en cada ambiente de recursión), que en la primera llamada será el nodo raíz.

void DFS(const int nodo, int nodoAct){
    mark[nodoAct] = true;
    if(mark[nodo]==true) return;
    if (nodoAct == nodo){
            printf("'%d'n",nodo);
            return;
    }else if(mark[nodo]==true) return;
    else{
        printf("%d ",nodoAct);

        int T = (int)graph.G[nodoAct].size();
        for(int i = 0; i < T; ++i)
        {
            if (!mark[graph.G[nodoAct][i].node]) DFS(nodo, graph.G[nodoAct][i].node);
        }
    }
}

En cada llamada recursiva marcaremos el nodo actual como visitado y luego verificamos si es el nodo buscado para salir de la recursión, este será nuestro caso base. De no ser el nodo requerido, se hace la llamada recursiva con todos los nodos hijos del nodo actual, pero en este caso, a diferencia del recorrido BFS, no se visitarán todos los hijos de forma consecutiva, sino que el algoritmo recorrerá en profundidad hasta llegar a un nodo extremo o nodo hoja, antes de retornar al ambiente de recursión en donde se encuentran los otros nodos hijos.

El orden en que se eligen las ramas en un recorrido DFS está determinado por el tipo de recorrido de procesamiento de árbol que se haya elegido, estos pueden ser:
  • Pre-orden: Se procesa primero la raíz, luego la rama izquierda y luego las ramas siguientes hasta llegar a la que se encuentra más a la derecha.
  • Post-orden: Se procesa el árbol desde las ramas izquierdas hasta la que se encuentra más a la derecha. Finalmente se procesa el nodo raíz
  • Simétrico o In-orden: Se procesa la rama de la izquierda, luego el nodo raíz y luego la rama derecha.
En este caso el recorrido es Pre-orden.

Tips:
  1. La búsqueda en anchura se recomienda cuando lo que se necesita es buscar el camino más corto en grafos no ponderados.
  2. La búsqueda en profundidad se puede utilizar para detectar ciclos en un grafo, determinar si un grafo es conexo o no y cuántas componentes conexas tiene, determinar puntos de articulación y biconexión de grafos, entre otras cosas.
  3. Cuando no tiene importancia el orden en que visitemos los nodos y aristas del grafo, se puede usar cualquiera de los dos algoritmos.
Dejo un link para mas información: Algoritmo de Búsqueda en Profundidad (DFS)

Un grafo de ejemplo

Supongamos que tenemos el siguiente grafo leído:
grafo
Queremos ver el orden en que cada algoritmo ha de recorrer el grafo. Llamaremos a la función BFS en el main y posteriormente la función DFS. Tomaremos el nodo ’2′ como nuestro nodo raíz para ambos algoritmos y la salida obtenida será:
resultado cmd

Conclusiones

Los algoritmos de búsqueda BFS y DFS son una de las herramientas básicas a la hora de trabajar con grafos. No sólo podremos usarlos para recorrer grafos o buscar elementos, sino que también podemos adaptarlos y mejorarlos para resolver de manera eficiente cualquier tipo de situaciones que podamos moldear como un grafo o un árbol.

En los próximos tutoriales aprenderemos otras técnicas de programación muy útiles que podrás aplicar a diferentes situaciones.

Estaremos atentos para resolver todas tus dudas. No olvides seguirnos y manifestar cualquier inquietud, queja o sugerencia.

Para mas información, dejo un vídeo explicativo por si tienen mas dudas sobre el tema.


Si necesitan poner en practica este tema, les recomiendo que vean el siguiente post "Implementado Algoritmos de Grafos en C++" donde detallamos ejercicios en C++ implementado estos grafos.
Compartir