BFS
Lección 10 de 14 del curso Grafos - Serie de Estructuras de Datos #9 de Coddy.
Los siguientes desafíos están diseñados para utilizar la clase Graph que acabas de construir.
Cada desafío te entrega un archivo graph bloqueado (el Graph final del capítulo anterior) y un archivo solution nuevo donde escribirás una función que UTILIZA el Graph.
Nuestro primer algoritmo: Breadth-First Search (Búsqueda en anchura). Comenzando desde un vértice, BFS visita todos los vértices alcanzables en oleadas: primero el inicio, luego todo lo que esté a una arista de distancia, después todo lo que esté a dos aristas, y así sucesivamente. La implementación clásica utiliza una queue (cola): encola el inicio, luego desencola repetidamente, registra el vértice como visitado y encola cualquier vecino no visitado.
Debido a que las listas de vecinos no tienen un orden fijo, dos ejecuciones correctas de BFS pueden producir diferentes órdenes de recorrido. Para que la respuesta sea determinista en este desafío, ordena los vecinos de cada vértice de forma ascendente antes de encolarlos.
Desafío
FácilEscribe una función bfs que reciba un array de enteros bidimensional adjacency (donde cada fila es una arista [u, v]) y un entero start, y devuelva el orden de visita BFS desde start como una lista de enteros.
Construye el grafo: para cada [u, v] en adjacency, llama a g.addEdge(u, v). Luego, realiza el BFS desde start utilizando una cola. Al procesar los vecinos de un vértice, ordénalos de forma ascendente para que el resultado sea determinista.
Debes utilizar la clase Graph (proporcionada en graph); no utilices elementos integrados del lenguaje (mapas, conjuntos) para modelar la adyacencia. Los datos auxiliares para el algoritmo (conjuntos de visitados, colas) pueden utilizar tipos de la biblioteca estándar (stdlib).
Pruébalo tú mismo
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}