15 - Detección de puentes (Bridges)

Un puente (o bridge) es una arista que, al eliminarla, incrementa la cantidad de componentes conexas de un grafo no dirigido. Identificarlos permite conocer puntos críticos de conectividad.

15.1 Concepto

• Solo aplica a grafos no dirigidos; en digrafos se requiere otra definición.
• Una arista u -- v es puente si no existe ningún camino alternativo entre u y v sin usar esa arista.
• En un árbol, todas las aristas son puentes; en un ciclo simple ninguna lo es.

15.2 Algoritmo de Tarjan

El algoritmo de Tarjan usa DFS con tiempos de descubrimiento tin[] y valores low[] que representan el tiempo mínimo alcanzable por back-edges.

• Inicializamos timer = 0; al entrar a un nodo u, asignamos tin[u] = low[u] = timer++.
• Para cada vecino v: si es el padre en el árbol, se ignora; si no está visitado, se desciende y se actualiza low[u] = min(low[u], low[v]).
• Después de procesar un hijo v, la arista u -- v es puente si low[v] > tin[u].
• Si v ya estaba visitado (back-edge), actualizamos low[u] = min(low[u], tin[v]).

Simulador de detección de puentes

15.3 Aplicaciones

La detección de puentes es esencial en:

• Redes de comunicación: enlaces cuya caída rompe la red (routers, switches, cables submarinos, enlaces WiFi críticos).
• Ingeniería de software: en análisis de dependencias, módulos enlazados de forma crítica que aislan al sistema si fallan.
• Análisis de caminos alternativos: en mapas y rutas, puentes reales, túneles o calles sin alternativa.
• Detener propagación de fallas: en sistemas distribuidos, identificar enlaces vulnerables y mejorar la tolerancia a fallos.
• Grafos sociales: detectar vínculos débiles que conectan comunidades y puntos de separación entre grupos.

15.4 Aplicación completa para probar en CLion

Implementación de Tarjan sobre lista de adyacencia. Imprime todas las aristas puente encontradas.

#include <stdio.h>
#include <stdlib.h>

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

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

Grafo crearGrafo(int n) {
  Grafo g;
  g.n = n;
  g.listas = calloc(n, sizeof(Arista *));
  return g;
}

void agregarAristaNoDirigida(Grafo *g, int u, int v) {
  Arista *a = malloc(sizeof(Arista));
  a->destino = v;
  a->sig = g->listas[u];
  g->listas[u] = a;

  Arista *b = malloc(sizeof(Arista));
  b->destino = u;
  b->sig = g->listas[v];
  g->listas[v] = b;
}

void dfsPuentes(const Grafo *g, int u, int padre, int *visitado, int *tin, int *low, int *timer) {
  visitado[u] = 1;
  tin[u] = low[u] = (*timer)++;

  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (v == padre) continue;
    if (!visitado[v]) {
      dfsPuentes(g, v, u, visitado, tin, low, timer);
      if (low[v] > tin[u]) {
        printf("Puente: %d -- %d\n", u, v);
      }
      if (low[v] < low[u]) low[u] = low[v];
    } else {
      if (tin[v] < low[u]) low[u] = tin[v];
    }
  }
}

void encontrarPuentes(const Grafo *g) {
  int *visitado = calloc(g->n, sizeof(int));
  int *tin = malloc(g->n * sizeof(int));
  int *low = malloc(g->n * sizeof(int));
  int timer = 0;

  for (int u = 0; u < g->n; u++) {
    if (!visitado[u]) {
      dfsPuentes(g, u, -1, visitado, tin, low, &timer);
    }
  }

  free(visitado);
  free(tin);
  free(low);
}

int main(void) {
  Grafo g = crearGrafo(7);
  agregarAristaNoDirigida(&g, 0, 1);
  agregarAristaNoDirigida(&g, 1, 2);
  agregarAristaNoDirigida(&g, 2, 0);
  agregarAristaNoDirigida(&g, 1, 3); /* puente */
  agregarAristaNoDirigida(&g, 3, 4);
  agregarAristaNoDirigida(&g, 4, 5);
  agregarAristaNoDirigida(&g, 5, 3); /* ciclo 3-4-5 */
  agregarAristaNoDirigida(&g, 4, 6); /* puente */

  printf("Puentes del grafo:\n");
  encontrarPuentes(&g);
  return 0;
}