Menú principal
Applet | Recorrido en profundidad (DFS)
Parámetros
Código Python
Visualizador
Parámetros
- En el campo Lista de adyacencias deberás introducir un grafo válido en formato de lista de listas encerradas por [corchetes]. Si imprimes una lista de adyacencias en Python y la pegas aquí ya estará en el formato correcto.
- El deslizador Velocidad controla la velocidad a la que se ejecuta el algoritmo.
- Los botones de colores permiten iniciar la simulación del algoritmo, pausarla, avanzarla paso a paso y reiniciarla.
Sobre este algoritmo
En el recorrido en profundidad, partiendo de un vértice inicial (que, en nuestro caso, será por lo general el nodo con índice cero o uno, excepto cuando el enunciado indique lo contrario) se explora un camino avanzando tan lejos como sea posible hasta alcanzar un punto muerto (un punto sin vértices adyacentes no visitados), en cuyo caso se retrocede para probar otros caminos aún sin explorar. El algoritmo finaliza una vez se han visitado todos los nodos alcanzables desde el vértice inicial. En caso de haber varios componentes no conexos, el algoritmo se ejecuta de nuevo para cada uno de ellos.
Recorrido en profundidad
Recorrido en profundidad