← Volver a los ejercicios

Puntos de articulación y puentes en una sola pasada

La búsqueda en profundidad lleva dos números por vértice, el momento en que se descubre, d, y el más bajo que alcanza su subárbol, low. Con ellos, una comparación al volver de cada hijo decide si el vértice es punto de articulación y otra si la arista es puente. Aquí se ejecutan las dos formas del recorrido, la recursiva y la de pila explícita, y cada vértice muestra d/low mientras corre.

1. El grafo y la predicción

Entrada: un grafo no dirigido, sin aristas repetidas.  Salida: los puntos de articulación y los puentes. La búsqueda arranca en el 0 y recorre los vecinos de menor a mayor.

Grafo:
━ arista del árbol ┅ retroceso que baja un low ━ puente ● punto de articulación sobre cada vértice: d/low
¿Cuántos puntos de articulación tiene?

2. Ejecute, con la versión que quiera

Recorrido:
Pila de llamadas: vacía
Puntos de articulación: ninguno todavía
Puentes: ninguno todavía
Devuelve: (aún no)
Paso 0 de 0

3. Los números, vértice por vértice

VérticedlowMarca

4. La raíz es distinta

Compare el primer grafo con el segundo. ¿Qué decide que la raíz sea punto de articulación?

5. Para llevarse

Sin solución aquí. En el tercer grafo, el vértice 2 es punto de articulación y ninguna de sus aristas es puente. Ejecute la versión recursiva y encuentre la línea y el hijo por los que queda marcado. Después cambie el orden de las listas de adyacencia, de mayor a menor, y vuelva a trazar a mano: ¿cambian los puntos de articulación? ¿Y los valores de d?