Pseudo Code
Lección 4 de 9 del curso Búsqueda en anchura - Algoritmos de grafos de Coddy.
bfs(n, edges, start):
build adjacency (sort each list ascending)
visited = all false
queue = [start]; visited[start] = true
order = []
while queue not empty:
node = queue.dequeue() # tomar del FRENTE
order.add(node)
for nb in adj[node]:
if not visited[nb]:
visited[nb] = true
queue.enqueue(nb)
return order- La única diferencia con DFS es el contenedor: una cola (FIFO) en lugar de una pila (LIFO).
- Una forma sencilla de escribir la cola es un arreglo con un índice head móvil: se desencola leyendo
queue[head]y avanzandohead.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Búsqueda en anchura - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity