He estado leyendo sobre algoritmos para encontrar los componentes fuertemente conectados en un gráfico dirigido . Se considera buscar dos DFS y la segunda etapa se transpone el gráfico original .
El algoritmo es el siguiente:
- Ejecute DFS en (comenzando en un vértice de inicio arbitrario), manteniendo un registro de los tiempos de finalización de todos los vértices.
- Calcule la transposición,
- Ejecute DFS en , comenzando en el vértice con el último tiempo de finalización, formando un árbol enraizado en ese vértice. Una vez que se ha completado un árbol, pasar al vértice no visitado con el siguiente última de acabado el tiempo y formar otro árbol usando DFS y repetir hasta que todos los vértices en son visitados.
- Emite los vértices en cada árbol formado por el segundo DFS como un componente separado fuertemente conectado.
Mi pregunta es :
- ¿Cuál es la intuición detrás de este paso intermedio de calcular una transposición?