Implementation (Part 2)
Lección 6 de 9 del curso Búsqueda en anchura - Algoritmos de grafos de Coddy.
Ahora recorremos el grafo por capas con una cola.
Desafío
IntermedioAhora construye el recorrido completo.
Escribe una función llamada bfs que reciba n, el arreglo plano edges (no dirigido) y un vértice start, y devuelva el orden en el que BFS visita los vértices desde start.
Construye la lista de adyacencia (vecinos ordenados de forma ascendente), luego usa una cola: marca y encola el inicio, y desencola repetidamente un vértice, regístralo y encola sus vecinos no visitados. Solo se visitan los vértices alcanzables desde start.
Pruébalo tú mismo
#include <stdlib.h>
int* bfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Escribe el código aquí
*returnSize = 0;
return edges;
}
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