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.
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.
d/low
| Vértice | d | low | Marca |
|---|
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?