Recorrido de grafos

Esta simulación muestra cómo una computadora explora un grafo. Los estudiantes eligen la búsqueda en anchura (BFS) o en profundidad (DFS), escogen el nodo de inicio y fijan la velocidad, y luego observan cómo los nodos cambian de color según estén en espera, en proceso o visitados. Las lecturas muestran el número de visitados, el tamaño de la cola o la pila y el orden de visitas, y un botón genera un grafo aleatorio nuevo. Ejecutar ambos métodos desde el mismo inicio muestra que BFS se extiende en anillos mientras DFS se adentra en profundidad. Apoya las lecciones de computación sobre estructuras de datos y algoritmos.

• Ejecuta BFS desde el nodo 1 y lee la lectura Orden de visita.
• Cambia el Método a DFS con el mismo Nodo de inicio y compara el orden.
• Observa cómo la lectura Tamaño de la cola / pila crece y decrece en cada método.
• Cambia el Nodo de inicio y observa cómo cambia todo el recorrido.
• Pulsa Generar grafo de nuevo y predice el orden antes de ejecutarlo.

1. 1Describe cómo la búsqueda en anchura y la búsqueda en profundidad exploran un grafo.
2. 2Distingue una cola de una pila y relaciona cada una con un método de búsqueda.
3. 3Predice el orden de visita de un grafo pequeño.
4. 4Explica por qué BFS encuentra rutas con el menor número de saltos.

Preguntas frecuentes de los docentes