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/24 10:27] sebach [DFS] |
algoritmos-oia:grafos:dfs [2017/12/26 19:12] (actual) sebach ↷ Page moved from algoritmos-oia:dfs to algoritmos-oia:grafos:dfs |
||
---|---|---|---|
Línea 41: | 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 52: | 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 63: | 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 72: | 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 87: | 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 117: | Línea 117: | ||
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 | ||
- | visited[vecino]=true; | + | if(!visited[nodoActual]){ |
- | for(int vecino : grafo[nodoActual]){ | + | visited[nodoActual]=true; |
- | if(visited[vecino]==false){ | + | for(int vecino : grafo[nodoActual]){ |
- | st.push(vecino); | + | if(visited[vecino]==false){ |
+ | st.push(vecino); | ||
+ | } | ||
} | } | ||
} | } |