Menú principal
Applet | Recorrido en anchura (BFS)
Parámetros
Código Python
Visualizador
Nodo actual:
Cola:
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 anchura, 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 exploran primero todos los vértices adyacentes no visitados al nodo actual. Posteriormente, se continúa con los nodos descubiertos siguiendo el mismo criterio, avanzando nivel por nivel en el grafo. Para gestionar el orden de exploración normalmente se utiliza una cola. 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 proceso se repite para cada uno de ellos.
Recorrido en anchura
Recorrido en anchura