BFS (breadth-first search) recorre el grafo en rondas: arranca en un vértice, usa una cola y visita primero sus vecinos, luego los vecinos de ellos, y así hasta cubrir todo. En grafos sin pesos garantiza llegar en la menor cantidad de aristas y registra quién descubrió a cada nodo para armar el camino.
Partimos de un origen, lo marcamos como visitado y lo encolamos. Luego, repetimos: desencolar un vértice, procesar sus vecinos no visitados, marcarlos y encolarlos. Se avanza capa por capa.
Usamos un arreglo circular simple para mantener O(1) por operación.
typedef struct {
int *datos;
int capacidad;
int ini;
int fin;
} Cola;
Cola *crearCola(int capacidad) {
Cola *c = malloc(sizeof(Cola));
if (!c) return NULL;
c->datos = malloc(capacidad * sizeof(int));
if (!c->datos) { free(c); return NULL; }
c->capacidad = capacidad;
c->ini = 0;
c->fin = 0;
return c;
}
int colaVacia(const Cola *c) { return c->ini == c->fin; }
void encolar(Cola *c, int v) {
c->datos[c->fin++] = v;
}
int desencolar(Cola *c) {
return c->datos[c->ini++];
}visitado[] en 0.u, visitar vecinos v no marcados, marcarlos y encolarlos.v si se necesita reconstruir caminos./* BFS con matriz de adyacencia */
void bfsMatriz(int **m, int n, int origen) {
int *visitado = calloc(n, sizeof(int));
Cola *c = crearCola(n);
visitado[origen] = 1;
encolar(c, origen);
while (!colaVacia(c)) {
int u = desencolar(c);
printf("%d ", u);
for (int v = 0; v < n; v++) {
if (m[u][v] != 0 && !visitado[v]) {
visitado[v] = 1;
encolar(c, v);
}
}
}
free(visitado);
free(c->datos);
free(c);
}/* BFS con lista de adyacencia */
typedef struct Arista {
int destino;
struct Arista *sig;
} Arista;
typedef struct {
int n;
Arista **listas;
} Grafo;
void bfsLista(const Grafo *g, int origen) {
int *visitado = calloc(g->n, sizeof(int));
Cola *c = crearCola(g->n);
visitado[origen] = 1;
encolar(c, origen);
while (!colaVacia(c)) {
int u = desencolar(c);
printf("%d ", u);
for (Arista *it = g->listas[u]; it; it = it->sig) {
int v = it->destino;
if (!visitado[v]) {
visitado[v] = 1;
encolar(c, v);
}
}
}
free(visitado);
free(c->datos);
free(c);
}Para reconstruir caminos mínimos, guarda un arreglo padre[] y asigna padre[v] = u cuando se encola v desde u. Al finalizar, padre define el árbol de BFS.
/* Fragmento para registrar padres en BFS con lista */
void bfsConPadres(const Grafo *g, int origen, int *padre) {
int *visitado = calloc(g->n, sizeof(int));
Cola *c = crearCola(g->n);
for (int i = 0; i < g->n; i++) padre[i] = -1;
visitado[origen] = 1;
encolar(c, origen);
while (!colaVacia(c)) {
int u = desencolar(c);
for (Arista *it = g->listas[u]; it; it = it->sig) {
int v = it->destino;
if (!visitado[v]) {
visitado[v] = 1;
padre[v] = u;
encolar(c, v);
}
}
}
free(visitado);
free(c->datos);
free(c);
}Con padre[] poblado, reconstruye un camino desde cualquier destino siguiendo padres hasta llegar al origen. El siguiente fragmento arma el camino en orden origen → destino:
/* Reconstruir camino desde 'destino' hasta 'origen' usando padre[] */
void reconstruirCamino(const int *padre, int origen, int destino, int n) {
int *camino = malloc(n * sizeof(int));
int len = 0;
int actual = destino;
while (actual != -1) {
camino[len++] = actual;
if (actual == origen) break;
actual = padre[actual];
}
if (camino[len - 1] != origen) {
printf("No hay camino de %d a %d\n", origen, destino);
} else {
printf("Camino %d -> %d: ", origen, destino);
for (int i = len - 1; i >= 0; i--) {
printf("%d", camino[i]);
if (i) printf(" -> ");
}
printf("\n");
}
free(camino);
}Programa autocontenido que construye un grafo, ejecuta BFS y muestra el árbol de padres.
#include <stdio.h>
#include <stdlib.h>
typedef struct Arista {
int destino;
struct Arista *sig;
} Arista;
typedef struct {
int n;
Arista **listas;
} Grafo;
typedef struct {
int *datos;
int ini, fin;
} Cola;
/* Reconstruir camino desde 'destino' hasta 'origen' usando padre[] */
void reconstruirCamino(const int *padre, int origen, int destino, int n) {
int *camino = malloc(n * sizeof(int));
int len = 0;
int actual = destino;
while (actual != -1) {
camino[len++] = actual;
if (actual == origen) break;
actual = padre[actual];
}
if (camino[len - 1] != origen) {
printf("No hay camino de %d a %d\n", origen, destino);
} else {
printf("Camino %d -> %d: ", origen, destino);
for (int i = len - 1; i >= 0; i--) {
printf("%d", camino[i]);
if (i) printf(" -> ");
}
printf("\n");
}
free(camino);
}
Grafo *crearGrafo(int n) {
Grafo *g = malloc(sizeof(Grafo));
if (!g) return NULL;
g->n = n;
g->listas = calloc(n, sizeof(Arista *));
return g;
}
void agregarArista(Grafo *g, int u, int v) {
Arista *n = malloc(sizeof(Arista));
n->destino = v;
n->sig = g->listas[u];
g->listas[u] = n;
}
Cola *crearCola(int n) {
Cola *c = malloc(sizeof(Cola));
c->datos = malloc(n * sizeof(int));
c->ini = c->fin = 0;
return c;
}
int colaVacia(const Cola *c) { return c->ini == c->fin; }
void encolar(Cola *c, int v) { c->datos[c->fin++] = v; }
int desencolar(Cola *c) { return c->datos[c->ini++]; }
void bfsConPadres(const Grafo *g, int origen, int *padre) {
int *visitado = calloc(g->n, sizeof(int));
Cola *c = crearCola(g->n);
for (int i = 0; i < g->n; i++) padre[i] = -1;
visitado[origen] = 1;
encolar(c, origen);
while (!colaVacia(c)) {
int u = desencolar(c);
for (Arista *it = g->listas[u]; it; it = it->sig) {
int v = it->destino;
if (!visitado[v]) {
visitado[v] = 1;
padre[v] = u;
encolar(c, v);
}
}
}
free(visitado);
free(c->datos);
free(c);
}
int main(void) {
Grafo *g = crearGrafo(5);
agregarArista(g, 0, 1);
agregarArista(g, 0, 2);
agregarArista(g, 1, 3);
agregarArista(g, 2, 3);
agregarArista(g, 3, 4);
int padre[5];
bfsConPadres(g, 0, padre);
printf("Padres en el arbol BFS desde 0:\n");
for (int i = 0; i < g->n; i++) {
printf("%d -> %d\n", i, padre[i]);
}
reconstruirCamino(padre, 0, 4, g->n);
/* liberar */
for (int u = 0; u < g->n; u++) {
Arista *it = g->listas[u];
while (it) {
Arista *tmp = it;
it = it->sig;
free(tmp);
}
}
free(g->listas);
free(g);
return 0;
}Ejecuta el programa para ver cómo se forma el árbol de BFS y modifica las aristas para probar distintas topologías. Con la configuración incluida, la salida esperada es:
Padres en el arbol BFS desde 0:
0 -> -1
1 -> 0
2 -> 0
3 -> 1
4 -> 3
Camino 0 -> 4: 0 -> 1 -> 3 -> 4