OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== DFS ======

DFS (abreviación de Depth-First Search, "búsqueda en profundidad") es una técnica de recorrido de grafos. 

Consiste en recorrer el grafo, guardando una lista de "nodos que tenemos que mirar". Esta lista tiene la particularidad de que el último nodo que agregamos a la lista es el primero que vamos a mirar (por eso "en profundidad"). Es decir, vamos a ir agotando los caminos del grafo.

El algoritmo consiste en primero, meter en la lista un nodo inicial. A partir de ahí, agarrar el último nodo que agregamos a la lista, y agregar todos sus vecinos.
Vamos a ir marcando los nodos una vez que hayamos procesado a todos sus hijos, no al agregarlo a la lista, como en BFS. Esto es porque supongamos que empezamos desde $A$, y agregamos sus vecinos $C$ y $B$. Ahora vamos a sacar de la lista $B$, y agotar todos los caminos desde éste. Y quizás hay un camino de $B$ a $C$, y en ese caso queremos recorrer este camino, lo que sería imposible si al agregar a $C$ antes lo hubiésemos marcado como visto.

==== Ejemplo ====

Supongamos que tenemos el siguiente grafo:

{{:algoritmos-oia:grafo-dfs.png?400|}}
Grafo creado [[http://mxwell.github.io/draw-graph/?q=graph{1--2;2--4;2--5;1--3;3--6;6--7;6--8}#|acá]]

Y que lo vamos a empezar a recorrer desde el nodo $1$.

Tenemos **false** en la variable visitado de cada nodo, y la lista de nodos para mirar está vacía:
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
F & F & F & F & F & F & F & F\\
\end{array}$$
$$\begin{array}{|c|}
\hline
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{array}$$

Agregamos al nodo $1$:
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
T & F & F & F & F & F & F & F\\
\end{array}$$
$$\begin{array}{|c|}
\hline
1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{array}$$

Sacamos al nodo $1$, y agregamos a sus vecinos que no fueron visitados (en el orden en el que recorramos los vecinos, podría ser cualquier orden):

$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
T & F & F & F & F & F & F & F\\
\end{array}$$
$$\begin{array}{|c|}
\hline
2, 3\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{array}$$

Sacamos primero al nodo $3$, y miramos sus vecinos:

$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
T & F & T & F & F & F & F & F\\
\end{array}$$
$$\begin{array}{|c|}
\hline
2, 6\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{array}$$

Sacamos al nodo $6$ y miramos sus vecinos no visitados:

$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
T & F & T & F & F & T & F & F \\
\end{array}$$
$$\begin{array}{|c|}
\hline
2, 7, 8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{array}$$

Notar que el $2$ quedó, pero primero vamos a agotar los caminos hacia abajo del nodo $3$.

Sacamos al nodo $8$ y como no tiene vecinos sin visitar, no hacemos nada (más que marcarlo como visitado al sacarlo, como a todos). Lo mismo luego con el nodo $7$:

$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
T & F & T & F & F & T & T & T\\
\end{array}$$
$$\begin{array}{|c|}
\hline
2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{array}$$

Sacamos al nodo $2$ y miramos sus vecinos no visitados:

$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
T & T & T & F & F & T & T & T\\
\end{array}$$
$$\begin{array}{|c|}
\hline
4, 5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{array}$$

Sacamos al nodo $5$ que no tiene nodos por visitar, y lo mismo con el $4$, y terminamos.

==== Implementación ====


Hay dos maneras básicas de implementar este algoritmo. Una es "de una", ir metiendo y sacando nodos hasta terminar, manteniendo una stack para la lista de "nodos a mirar". Esta estructura es de tipo "LIFO" (Last In, First Out, o "el último que entró es el primero en salir"). Stack significa pila, y es como una pila de platos. El último que agregás a la pila tiene que ser el primero que saques, excepto que no te importe romper algunos. Para leer sobre stack se puede consultar la [[http://www.cplusplus.com/reference/stack/stack/|cpp reference]].

Otra manera de implementación muy usada es la manera recursiva (con una función que se llame a sí misma, por cualquier duda con el término está disponible la explicación de [[:algoritmos-oia:recursion|recursión]]).


Manera "directa":

<code cpp>

// Tenemos un vector< vector<int> > grafo que en la posición i guarda los vecinos del nodo i
// Tenemos un nodo n inicial a partir del cual nos empezamos a esparcir
int V = grafo.size();
vector visited(V, false);
stack<int> st;
st.push(n);
while(!st.empty()){
    int nodoActual = st.top(); // Así miramos al primero de la pila
    st.pop(); // Cuando ya lo guardamos, borramos de la pila al primero
    if(!visited[nodoActual]){
        visited[nodoActual]=true;
        for(int vecino : grafo[nodoActual]){
            if(visited[vecino]==false){
                st.push(vecino);
            }
        }
    }
}

</code>


Manera recursiva:

<code cpp>

//variables globales "vector<bool> visited" y "vector< vector<int> > grafo". O se pueden pasar por parámetro a la función, con el cuidado de pasar referencias y que la función no cree otra varibale igual, por temas de tiempo, pero eso es para ver en otro post.
void dfs(int nodoActual){
    for(int vecino : grafo[nodoActual]){
        if(visited[vecino]==false){
            visited[vecino]=true;
            dfs(vecino);
        }
    }
}

// Para llamar a la función empezando a recorrer el grado desde el nodo n, se hace:
int main(){
    // Inicializo el grafo
    int V=grafo.size();
    for(int i=0; i<V; i++){
        visited.push_back(false);
    }
    int n = 1; //por ejemplo, para recorrer desde el 1.
    visited[n]=true;
    dfs(n);
}

</code>

Como se ve en el código, no hay una lista de "vecinos a mirar" en esta segunda manera de implementación. Esto es porque al llamar a la función con un vecino, sabemos que la función va a hacer todo el procedimiento para ese vecino, y ya podremos olvidarnos de ese vecino. Entonces no hace falta guardarlo en ningún lado.


==== Complejidad ====

Se ve que cada vértice se lo mira a lo sumo una vez, y en una visita al nodo se lo agrega/saca de la pila, y se hacen operaciones de tiempo constante, por lo que tenemos $\large O(V)$ tiempo para los vértices. Además, cada arista se ve también a lo sumo una vez, tomando $\large O(E)$ tiempo.
En total, la complejidad temporal es $\large O(V+E)$, que en términos de grafos es óptimo.

La complejidad espacial es sencilla de ver. Tenemos el grafo que guarda una entrada por arista (en realidad dos, para la arista $(u,v)$ guarda $v$ en el vector de $u$ y $u$ en el vector de $v$). Luego, el arreglo de visitados tiene una variable por nodo, y en la pila (en el primer caso) a lo sumo están todos a la vez, una sola vez (si el nodo inicial es vecino de todos).
Entonces la complejidad espacial también se ve que es $\large O(V+E)$.

==== Aplicación interesante ====

Al igual que en BFS, podemos usar esta técnica de recorrido de grafo para ver si podemos pintar los nodos con dos colores, de manera que no haya dos vecinos adyacentes con el mismo color. Si eso se puede el grafo se llama bipartito y pueden leer en la wiki sobre este tipo de grafos.
Lo que haríamos sería, arrancar pintando un nodo cualquiera de un color (le ponemos 0), y a partir de ahí, a todos sus vecinos le ponemos 1, luego cuando miramos un nodo, vamos a todos sus vecinos y le ponemos el color del que este nodo no está pintado, y así. Si en algún momento queremos pintar un nodo que está pintado del otro color al que lo íbamos a pintar, entonces no se puede. Si el algoritmo termina y pinta todos los nodos, se puede.

Una diferencia principal es que a BFS no se lo puede utilizar recursivamente, pero en general todo se puede hacer con cualquiera de los métodos. En algunos algoritmos bfs va a ser mucho más sencillo de aplicar, y en otros, dfs.


== Links pseudo-externos ==

Charla de Melanie Sclar durante el nacional de OIA 2015, hablando sobre muchas cosas de grafos y entre ellas BFS:

[[https://www.youtube.com/watch?v=Q_FcD_z5AuQ|Video]]

[[http://www.oia.unsam.edu.ar/wp-content/uploads/2013/10/Grafos.pdf|PDF]]
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
