Laboratorio Visual: TopoSort (DFS) y Gráfica de Componentes ($G_{cc}$)
Explora el análisis formal de los 3 casos de coloración y la condensación de digrafos en DAGs.
Blanco Gris Negro
Estado del RecorridoPaso 0 / 0
Presiona Paso Siguiente o Reproducir para iniciar la exploración DFS.
Lista Topológica $L$Orden $v_i.f > v_j.f$
(Lista vacía)
Pila de Recursión DFSReloj $t = 0$
Pila inactiva
Teorema Central: Al examinar $(u, v)$ con $u$ gris:
$v$ Gris: Arista atrás $\to$ ciclo ($\bot$).
$v$ Blanco: Subárbol recursivo $\to u.f > v.f$.
$v$ Negro: Ya finalizó $\to u.f > v.f$.
Digrafo Canónico de Tarjan (1972) · 13 vértices
Estructura de ComponentesGrafo $G$
El grafo contiene 4 componentes fuertemente conexas (SCCs). Haz clic en Condensar a $G_{cc}$ para colapsar cada SCC en un supernodo y verificar que el resultado es estrictamente un DAG.
Componentes Fuertes (SCC)
$C_1$: {0, 1, 2, 3, 4, 5} (Ciclos mutuos)
$C_2$: {6, 8} (Ciclo 6 ⇄ 8)
$C_3$: {7} (Nodo aislado de salida)
$C_4$: {9, 10, 11, 12} (Ciclo cuádruple)
Orden Topológico de $G_{cc}$
C₁
⟶
C₂
⟶
C₃
|
C₄
Como $G_{cc}$ es un DAG, las dependencias entre componentes admiten orden lineal.