4.3.4. Algoritmos sobre grafos dirigidos.
Componentes fuertemente conexos
Algoritmo para encontrar los componentes fuertemente conexos de un grafo dirigido G.
1. Realizar la búsqueda en profundidad de G, numerando los vértices en el orden de terminación de las llamadas recursivas (al final de bpp).
2. Construir un nuevo grafo dirigido GR invirtiendo las direcciones de los arcos. Para todo <v, w> ? A(G), <w, v> ? A(GR).
3. Realizar una búsqueda en profundidad en GR partiendo del nodo con numeración más alta. Si en el recorrido no se visitan todos los nodos, iniciar la búsqueda en profundidad a partir del nodo no visitado con numeración más alta.
4. Cada árbol del bosque abarcador resultante es un componente fuertemente conexo de G.