Herramientas de usuario
algoritmos-oia:grafos:dfs
Diferencias
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:18] sebach [Implementación] |
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 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 116: | 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); | ||
| + | } | ||
| } | } | ||
| } | } | ||
algoritmos-oia/grafos/dfs.1514110719.txt.gz · Última modificación: 2017/12/24 10:18 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
