Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
algoritmos-oia:grafos:dfs [2017/12/06 11:00] sebach Agrego todo DFS, falta poder agregar una imagen que no estoy pudiendo |
algoritmos-oia:grafos:dfs [2017/12/26 19:12] (actual) sebach ↷ Page moved from algoritmos-oia:dfs to algoritmos-oia:grafos:dfs |
||
---|---|---|---|
Línea 5: | Línea 5: | ||
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. | 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 que no fueron agregados antes (es importante mirar que no hayan sido agregados antes porque si no vamos a entrar en un loop mirando los nodos infinitas veces). | + | 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 ==== | ==== Ejemplo ==== | ||
Línea 11: | Línea 12: | ||
Supongamos que tenemos el siguiente grafo: | Supongamos que tenemos el siguiente grafo: | ||
- | FIXME Agregar imagen | + | {{:algoritmos-oia:grafo-dfs.png?400|}} |
- | [[http://mxwell.github.io/draw-graph/?q=graph{1--2;2--4;2--5;1--3;3--6;6--7;6--8}#|Grafo]] | + | 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$. | Y que lo vamos a empezar a recorrer desde el nodo $1$. | ||
Línea 40: | Línea 41: | ||
$$\begin{array}{|c|c|c|c|c|c|c|c|} | $$\begin{array}{|c|c|c|c|c|c|c|c|} | ||
\hline | \hline | ||
- | T & T & T & F & F & F & F & F\\ | + | T & F & F & F & F & F & F & F\\ |
\end{array}$$ | \end{array}$$ | ||
$$\begin{array}{|c|} | $$\begin{array}{|c|} | ||
Línea 51: | Línea 52: | ||
$$\begin{array}{|c|c|c|c|c|c|c|c|} | $$\begin{array}{|c|c|c|c|c|c|c|c|} | ||
\hline | \hline | ||
- | T & T & T & F & F & T & F & F\\ | + | T & F & T & F & F & F & F & F\\ |
\end{array}$$ | \end{array}$$ | ||
$$\begin{array}{|c|} | $$\begin{array}{|c|} | ||
Línea 62: | Línea 63: | ||
$$\begin{array}{|c|c|c|c|c|c|c|c|} | $$\begin{array}{|c|c|c|c|c|c|c|c|} | ||
\hline | \hline | ||
- | T & T & T & F & F & T & T & T \\ | + | T & F & T & F & F & T & F & F \\ |
\end{array}$$ | \end{array}$$ | ||
$$\begin{array}{|c|} | $$\begin{array}{|c|} | ||
Línea 71: | Línea 72: | ||
Notar que el $2$ quedó, pero primero vamos a agotar los caminos hacia abajo del nodo $3$. | 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. Lo mismo luego con el nodo $7$: | + | 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|} | $$\begin{array}{|c|c|c|c|c|c|c|c|} | ||
\hline | \hline | ||
- | T & T & T & F & F & T & T & T\\ | + | T & F & T & F & F & T & T & T\\ |
\end{array}$$ | \end{array}$$ | ||
$$\begin{array}{|c|} | $$\begin{array}{|c|} | ||
Línea 86: | Línea 87: | ||
$$\begin{array}{|c|c|c|c|c|c|c|c|} | $$\begin{array}{|c|c|c|c|c|c|c|c|} | ||
\hline | \hline | ||
- | T & T & T & T & T & T & T & T\\ | + | T & T & T & F & F & T & T & T\\ |
\end{array}$$ | \end{array}$$ | ||
$$\begin{array}{|c|} | $$\begin{array}{|c|} | ||
Línea 110: | Línea 111: | ||
// Tenemos un nodo n inicial a partir del cual nos empezamos a esparcir | // Tenemos un nodo n inicial a partir del cual nos empezamos a esparcir | ||
int V = grafo.size(); | int V = grafo.size(); | ||
- | int visited[V]; | + | vector visited(V, false); |
- | for(int i=0; i<V; i++){ | + | |
- | visited[i]=false; | + | |
- | } | + | |
stack<int> st; | stack<int> st; | ||
st.push(n); | st.push(n); | ||
- | visited[n]=true; | ||
while(!st.empty()){ | while(!st.empty()){ | ||
int nodoActual = st.top(); // Así miramos al primero de la pila | int nodoActual = st.top(); // Así miramos al primero de la pila | ||
st.pop(); // Cuando ya lo guardamos, borramos de la pila al primero | st.pop(); // Cuando ya lo guardamos, borramos de la pila al primero | ||
- | for(int i=0; i<grafo[nodoActual].size(); i++){ | + | if(!visited[nodoActual]){ |
- | int vecino = grafo[nodoActual][i]; | + | visited[nodoActual]=true; |
- | if(visited[vecino]==false){ | + | for(int vecino : grafo[nodoActual]){ |
- | st.push(vecino); | + | if(visited[vecino]==false){ |
- | visited[vecino]=true; | + | st.push(vecino); |
+ | } | ||
} | } | ||
} | } | ||
Línea 136: | Línea 134: | ||
<code cpp> | <code cpp> | ||
- | //variables globales "vector<int> visited" y "vector< vector<int> > grafo". O se pueden pasar por parámetro a la función, con el cuidado de pasar el puntero y que la función no cree otra varibale igual, por temas de tiempo. | + | //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){ | void dfs(int nodoActual){ | ||
- | for(int i=0; i<grafo[nodoActual].size(); i++){ | + | for(int vecino : grafo[nodoActual]){ |
- | int vecino = grafo[nodoActual][i]; | + | |
if(visited[vecino]==false){ | if(visited[vecino]==false){ | ||
+ | visited[vecino]=true; | ||
dfs(vecino); | dfs(vecino); | ||
} | } | ||
Línea 147: | Línea 145: | ||
// Para llamar a la función empezando a recorrer el grado desde el nodo n, se hace: | // Para llamar a la función empezando a recorrer el grado desde el nodo n, se hace: | ||
- | int V=grafo.size(); | + | int main(){ |
- | for(int i=0; i<V; i++){ | + | // Inicializo el grafo |
- | visited.push_back(false); | + | 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); | ||
} | } | ||
- | int n = 1; //por ejemplo, para recorrer desde el 1. | ||
- | visited[n]=true; | ||
- | dfs(n); | ||
</code> | </code> |