Buscador de Puentes

Pseudocódigo

Maquinaria idéntica a la de los puntos de articulación, con una sola comparación cambiada de mayor o igual a estrictamente mayor.

dfs(u, padre):
    desc[u] = low[u] = ++tiempo

    para cada vecino v de u:
        si v == padre: continuar   // saltar la arista de llegada
        si v ya visitado:
            low[u] = min(low[u], desc[v])    // retroceso
        si no:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            si low[v] > desc[u]:
                informar de la arista (u, v) como puente

La desigualdad estricta es toda la diferencia con los puntos de articulación. low[v] > desc[u] dice que nada en el subárbol por debajo de v puede alcanzar u ni nada por encima, así que la arista (u, v) es la única ruta y quitarla desconecta el grafo. Los puntos de articulación usan low[v] >= desc[u], donde la igualdad significa que el subárbol puede alcanzar el propio u pero no más allá, lo que aísla el subárbol si borras el vértice u pero no si borras solo la arista.

Ejemplo resuelto, paso a paso

Ejecuta el DFS desde A sobre un triángulo con una cola de dos aristas, el mismo grafo usado para los puntos de articulación, de modo que las dos pruebas puedan compararse sobre datos idénticos.

Grafo de ejemplo: Aristas no dirigidas A-B, B-C y C-A que forman un triángulo, más C-D y D-E.

1. Asignar tiempos de descubrimiento. Bajando por A, B, C, D y E se obtienen los tiempos de descubrimiento 1, 2, 3, 4 y 5 respectivamente.
2. E es un callejón sin salida. E solo tiene a su padre D como vecino, así que low[E] se queda en 5.
3. D-E es un puente. Al volver a D, low[D] = min(4, low[E] = 5) = 4. Comprueba la arista: low[E] = 5 > desc[D] = 4, así que D-E es un puente. Quitarla aísla a E, lo cual es claramente correcto.
4. C-D también es un puente. En C, la arista de retroceso C-A da low[C] = min(3, desc[A] = 1) = 1, e incorporando al hijo queda min(1, low[D] = 4) = 1. Comprueba la arista hacia D: low[D] = 4 > desc[C] = 3, así que C-D también es un puente.
5. Las aristas del triángulo no lo son. En B, low[B] = min(2, low[C] = 1) = 1. Comprueba la arista B-C: low[C] = 1 > desc[B] = 2 es falso, así que B-C no es puente. C puede alcanzar A sin usar B-C, de modo que la arista tiene una ruta alternativa. El mismo razonamiento descarta A-B y C-A.

Los puentes son C-D y D-E. Fíjate en el contraste con los puntos de articulación sobre este mismo grafo, donde la respuesta eran los vértices C y D. Toda arista del triángulo está en un ciclo y por tanto tiene un desvío, mientras que toda arista de la cola es la única conexión hacia lo que hay más allá. La regla general se deduce directamente: una arista es puente exactamente cuando no pertenece a ningún ciclo.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V)

Una única búsqueda en profundidad con trabajo extra constante por arista, así que el coste es el del recorrido. Cada vértice se visita una vez y cada arista se examina dos veces, una desde cada extremo. El estado son dos enteros por vértice más la pila de recursión, todo O(V). El enfoque ingenuo de quitar cada arista y comprobar la conectividad cuesta O(E por (V + E)), de modo que en un grafo con 10.000 aristas el método del low-link es del orden de cuatro magnitudes más rápido.

Cuándo usar Búsqueda de Puentes y cuándo no

El mismo DFS responde a varias preguntas relacionadas. Elige según si lo frágil es una arista, un vértice o toda una región.

Errores frecuentes

• Usar >= en lugar de >. La prueba de punto de articulación es low[v] >= desc[u]; la de puente es estrictamente low[v] > desc[u]. Usar >= informa de toda arista de árbol hacia un vértice que no puede trepar por encima de su padre, lo que sobreinforma gravemente. Un solo carácter separa los dos algoritmos.
• Saltar al padre por vértice en lugar de por arista. Con aristas paralelas entre u y v, la segunda arista es una ruta alternativa genuina y ninguna de las dos es puente. Saltar por identidad de vértice lo oculta e informa de un puente inexistente. Registra la arista concreta por la que llegaste.
• Usar low[v] en lugar de desc[v] para las aristas de retroceso. Cuando encuentres un vecino ya visitado, incorpora su tiempo de descubrimiento, no su low-link. Usar low[v] puede importar un valor de un subárbol no relacionado y suprimir en silencio puentes auténticos.
• Aplicarlo a grafos dirigidos. Los puentes están definidos para grafos no dirigidos. La pregunta dirigida, qué aristas al eliminarse aumentan el número de componentes fuertemente conexas, es otro problema y requiere otra maquinaria.
• Olvidar las componentes desconectadas. Un DFS cubre una sola componente. Itera sobre todos los vértices y arranca una búsqueda nueva desde cada uno no visitado, o los puentes de otras componentes quedarán sin informar.

Preguntas frecuentes

¿Qué es un puente en un grafo?

Un puente, también llamado arista de corte, es una arista cuya eliminación aumenta el número de componentes conexas. Equivalentemente es una arista que no pertenece a ningún ciclo: si hubiera un ciclo a través de ella, el resto de ese ciclo ofrecería una ruta alternativa y quitarla no desconectaría nada.

¿Cómo se encuentran los puentes de un grafo?

Ejecuta un único DFS registrando para cada vértice su tiempo de descubrimiento y su low-link, el menor tiempo de descubrimiento alcanzable desde su subárbol mediante a lo sumo una arista de retroceso. Una arista de árbol de u a su hijo v es puente exactamente cuando low[v] > desc[u], es decir cuando nada por debajo de v puede alcanzar u ni nada por encima. Todo el algoritmo es O(V + E).

¿Cuál es la diferencia entre un puente y un punto de articulación?

Un puente es una arista cuya eliminación desconecta el grafo; un punto de articulación es un vértice cuya eliminación lo hace. Salen del mismo DFS y se diferencian en una comparación: estrictamente mayor para puentes, mayor o igual para puntos de articulación. Un grafo puede tener uno sin el otro.

¿Puede un puente formar parte de un ciclo?

No, y esta es la forma más limpia de pensarlo. Si una arista pertenece a un ciclo, el resto de ese ciclo es una ruta alternativa entre sus extremos, así que quitarla deja el grafo conectado. Los puentes son exactamente las aristas que no pertenecen a ningún ciclo.

¿Para qué sirven los puentes?

Para hallar enlaces críticos en redes troncales de telecomunicaciones y de fibra, carreteras y tramos ferroviarios esenciales cuyo cierre partiría una región, conexiones frágiles en redes eléctricas y análisis de riesgo de dependencias en software. En LeetCode el mismo problema aparece como Critical Connections in a Network.