Componente fuertemente conexo
Estos subgrafos forman una partición del grafo.
Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo.
El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan[1] en 1970 a base de una búsqueda en profundidad (depth-first search).
Para encontrar los componentes fuertemente conexos se puede utilizar el algoritmo de Kosaraju el cual funciona de la siguiente forma: Sea
un grafo dirigido: Las dos búsquedas en profundidad y la construcción del grafo reverso consumen tiempo lineal, de manera que el tiempo total es también lineal.
