9 - Recorridos en grafos

Un recorrido sirve para visitar todos los vértices que se pueden alcanzar desde un punto. Aquí se explica qué son, cómo se diferencian BFS y DFS y cómo usar el arreglo visitado[] en C para no repetir nodos.

9.1 ¿Qué es un recorrido?

Es un proceso sistemático que visita vértices a partir de uno o más nodos iniciales, siguiendo las aristas del grafo y marcando los ya procesados para evitar repeticiones. Igual que en árboles binarios, donde existen tres recorridos clásicos (preorden, inorden y postorden), en grafos hay dos formas principales de explorar: por anchura (BFS) y por profundidad (DFS).

9.2 Importancia y usos de los recorridos

  • Detectar conectividad y componentes.
  • Encontrar rutas y calcular distancias (BFS en grafos no ponderados).
  • Detectar ciclos u ordenar tareas (DFS para topológico en digrafos acíclicos).
  • Preparar estructuras previas a algoritmos de caminos mínimos o flujos.

9.3 Diferencias BFS/DFS

  • BFS: (breadth-first search - búsqueda en anchura) usa una cola, visita por capas y encuentra distancias mínimas en aristas sin peso.
    Abrir visualizador BFS interactivo
  • DFS: (depth-first search - búsqueda en profundidad) usa pila (implícita con recursión o explícita), profundiza antes de retroceder y es útil para detectar ciclos y tiempos de entrada/salida.
    Abrir visualizador DFS interactivo

9.4 Requisitos y estructuras auxiliares

Se necesita una estructura de grafo (matriz o lista), una cola o pila según el recorrido, y un arreglo visitado para marcar vértices ya explorados.

9.5 Preparación del arreglo visitado[]

Se inicializa en 0 para todos los vértices. Al visitar uno, se marca en 1. En grafos no dirigidos evita bucles infinitos; en dirigidos permite seguir las aristas con dirección correcta sin repetir nodos.

9.6 Recorridos en grafos dirigidos y no dirigidos

En grafos no dirigidos, las aristas se recorren en ambos sentidos; el marcado con visitado evita volver por el mismo borde. En digrafos, solo se siguen aristas en su sentido; BFS y DFS se aplican igual, pero el resultado respeta la orientación.

/* BFS sobre lista de adyacencia */
#include <stdio.h>
#include <stdlib.h>

typedef struct Arista {
  int destino;
  struct Arista *sig;
} Arista;

typedef struct {
  int n;
  Arista **listas;
} Grafo;

void bfs(const Grafo *g, int origen) {
  if (!g || origen < 0 || origen >= g->n) return;
  int *visitado = calloc(g->n, sizeof(int));
  int *cola = malloc(g->n * sizeof(int));
  int ini = 0, fin = 0;

  visitado[origen] = 1;
  cola[fin++] = origen;

  while (ini < fin) {
    int u = cola[ini++];
    printf("%d ", u);
    for (Arista *it = g->listas[u]; it; it = it->sig) {
      int v = it->destino;
      if (!visitado[v]) {
        visitado[v] = 1;
        cola[fin++] = v;
      }
    }
  }
  free(visitado);
  free(cola);
}
/* DFS recursivo sobre lista de adyacencia */
void dfsRec(const Grafo *g, int u, int *visitado) {
  visitado[u] = 1;
  printf("%d ", u);
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (!visitado[v]) {
      dfsRec(g, v, visitado);
    }
  }
}

void dfs(const Grafo *g, int origen) {
  if (!g || origen < 0 || origen >= g->n) return;
  int *visitado = calloc(g->n, sizeof(int));
  dfsRec(g, origen, visitado);
  free(visitado);
}

Para grafos con varios componentes, inicia BFS/DFS desde cada vértice no visitado hasta cubrirlos todos. Así garantizas que el marcado visitado abarque el grafo completo.

Retornar