4.3.4. Algoritmos sobre grafos dirigidos.
Componentes fuertemente conexos
Un componente conexo de un grafo G es un subgrafo conexo (y maximal) de G. Es decir, contiene un conjunto de vértices para los cuales existen caminos entre cualquier par de nodos (v, w) y (w,v).
Si el grafo es dirigido, entonces hablamos de componentes fuertemente conexos.
Ejemplo. Grafo G no dirigido.
Cálculo de componentes conexos en grafos no dirigidos: Realizar un recorrido en profundidad. Cada árbol generado es un componente conexo.
En grafos dirigidos no es suficiente con realizar una búsqueda primero en profundidad.
Ejemplo. Grafo G dirigido.