Buscador de Puntos de Articulación

Pseudocódigo

Un solo DFS y dos números por vértice. El tiempo de descubrimiento dice cuándo se vio el vértice por primera vez; el low-link dice cuál es el vértice más temprano al que puede llegar su subárbol a través de una arista de retroceso.

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

    para cada vecino v de u:
        si v == padre: continuar
        si v ya visitado:
            low[u] = min(low[u], desc[v])   // retroceso
        si no:
            hijos++
            dfs(v, u)
            low[u] = min(low[u], low[v])
            si padre != NINGUNO y low[v] >= desc[u]:
                marcar u como punto de articulación

    si padre == NINGUNO y hijos > 1:
        marcar u como punto de articulación   // regla raíz

La condición low[v] >= desc[u] dice que el subárbol con raíz en el hijo v no tiene ninguna arista de retroceso que trepe por encima de u. Así que toda ruta de salida de ese subárbol pasa por u, y borrar u lo deja aislado. La raíz es un caso aparte porque no tiene padre del que quedar desconectada: la raíz es punto de articulación exactamente cuando tiene dos o más hijos en el DFS, ya que esos subárboles solo pueden alcanzarse entre sí a través de ella.

Ejemplo resuelto, paso a paso

Ejecuta el DFS desde A sobre un grafo formado por un triángulo con una cola de dos vértices, tomando los vecinos por orden alfabético.

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 colgando de él.

1. Descender hasta E. Los tiempos de descubrimiento y los low-link se asignan al bajar: A recibe 1, B recibe 2, C recibe 3, D recibe 4 y E recibe 5. E es una hoja cuyo único vecino es su padre D, así que low[E] se queda en 5.
2. Volver a D. low[D] = min(4, low[E] = 5) = 4. Comprueba el hijo: low[E] = 5 >= desc[D] = 4, así que nada por debajo de E trepa por encima de D. D es punto de articulación, y en efecto quitar D aísla a E.
3. Volver a C. C tiene además la arista de retroceso C-A, que fija low[C] = min(3, desc[A] = 1) = 1. Incorporando al hijo queda low[C] = min(1, low[D] = 4) = 1. Comprueba el hijo D: low[D] = 4 >= desc[C] = 3, así que C es punto de articulación. Quitar C separa la cola D-E del triángulo.
4. Volver a B. low[B] = min(2, low[C] = 1) = 1. Comprueba el hijo C: low[C] = 1 >= desc[B] = 2 es falso, porque C puede llegar de vuelta hasta A sin pasar por B. Así que B no es punto de articulación, lo cual es correcto: el triángulo mantiene conectados A y C sin él.
5. Terminar en la raíz. A es la raíz del DFS. Tiene exactamente un hijo en el DFS, B, ya que a C se llegó a través de B y no directamente. Un solo hijo significa que la regla de la raíz no se dispara, así que A no es punto de articulación.

Los puntos de articulación son C y D. El triángulo A-B-C no aporta ninguno entre A y B porque todo vértice de un ciclo tiene una ruta alternativa, mientras que en la cola C-D-E todo vértice interno es crítico. Ese contraste es la intuición clave: los puntos de articulación viven en las cadenas, no dentro de los ciclos.

Complejidad y de dónde sale

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

Esto es una única búsqueda en profundidad con trabajo extra constante por arista, así que cuesta lo mismo que el propio recorrido. Cada vértice se visita una vez y cada arista se examina dos veces, una desde cada extremo. El estado adicional son dos enteros por vértice, el tiempo de descubrimiento y el low-link, más la pila de recursión, todo O(V). La alternativa ingenua, quitar cada vértice por turno y comprobar la conectividad, cuesta O(V por (V + E)), así que el método del low-link convierte una comprobación cuadrática en una lineal en una sola pasada. En un grafo con 10.000 vértices y 30.000 aristas la diferencia es de unos cuatro órdenes de magnitud.

Cuándo usar Puntos de Articulación y cuándo no

Puntos de articulación, puentes y componentes biconexas salen todos del mismo DFS. Cuál necesitas depende de si lo frágil es un vértice o una arista.

Errores frecuentes

• Aplicar la regla de no raíz a la raíz. La raíz no tiene padre, así que la prueba low[v] >= desc[u] carece de sentido allí y normalmente la marcará mal. La raíz necesita su propia regla: es punto de articulación exactamente cuando tiene dos o más hijos en el DFS.
• Usar low[v] en lugar de desc[v] en una arista de retroceso. Cuando encuentras un vértice ya visitado v, actualiza con desc[v], no con low[v]. Usar low[v] puede propagar un valor procedente de otro subárbol y producir low-links demasiado pequeños, ocultando puntos de articulación auténticos.
• Confundir la prueba del hijo con la de puentes. Los puntos de articulación usan low[v] >= desc[u]; los puentes usan low[v] > desc[u], estrictamente mayor. La diferencia de un solo carácter es la diferencia entre "todo debe pasar por este vértice" y "todo debe pasar por esta arista".
• Saltar al padre por identidad y no por arista. Comparar solo el identificador del padre falla en multigrafos. Si dos aristas paralelas unen u y v, la segunda es una ruta alternativa genuina y no debe saltarse. Registra la arista por la que llegaste, no solo el vértice.
• Olvidar las componentes desconectadas. Un solo DFS cubre una sola componente. Recorre todos los vértices y arranca un DFS nuevo desde cada uno no visitado, reiniciando la regla de la raíz para cada raíz nueva.

Preguntas frecuentes

¿Qué es un punto de articulación en un grafo?

Un punto de articulación, también llamado vértice de corte, es un vértice cuya eliminación aumenta el número de componentes conexas. En términos prácticos es un punto único de fallo: toda ruta entre algún par de vértices pasa por él, así que borrarlo parte el grafo.

¿Cómo se encuentran los puntos de articulación?

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. Un vértice u que no sea raíz es punto de articulación si algún hijo v del DFS cumple low[v] >= desc[u]. La raíz lo es si tiene dos o más hijos en el DFS. Todo el proceso es O(V + E).

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

Un punto de articulación es un vértice cuya eliminación desconecta el grafo; un puente es una arista cuya eliminación lo hace. Salen del mismo DFS y se diferencian en una comparación: low[v] >= desc[u] para puntos de articulación y el estricto low[v] > desc[u] para puentes. Un grafo puede tener puentes sin puntos de articulación y viceversa.

¿Por qué la raíz del DFS es un caso especial?

Porque la prueba general pregunta si un subárbol hijo puede alcanzar algo por encima del vértice actual, y por encima de la raíz no hay nada. La raíz solo es crítica cuando une dos o más subárboles que de otro modo estarían separados, que es exactamente la condición de tener dos o más hijos en el DFS.

¿Para qué sirven los puntos de articulación?

Identifican routers críticos en redes de comunicación, cruces clave en sistemas viarios, servidores cuyo fallo particionaría una infraestructura distribuida e intermediarios influyentes en redes sociales. La ingeniería de fiabilidad los usa para decidir dónde compensa invertir en redundancia.