Adfshkg

askdfjhgasldkhasñldkgjgk´sdfñj ásñdljgñasdlkfgjñalsdfgjñasldfkj asñldkasñldfghañslgdhañsljs Una componente fuertemente conexa de un grafo G=(V,E) es el máximo conjunto de vértices U subconjunto de Vtal que para cada par de vértices u, v en U, existan caminos desde u a v y viceversa.
El algoritmo descubre todas las componentes fuertemente conexas. Para ello define el grafo traspuesto de G, GT=(V,ET), donde ET={(u,v) tal que (v,u) pertenece a E}. En otras palabras, invierte el sentido de todas los arcos.
Algoritmo:
Strongly_Connected_Components(G)1.- Llamar a DFS(G) para obtener eltiempo de término f[u], para cada vértice u;2.- Calcular GT;3.- Llamar a DFS(GT), pero en el loop principal de DFS, considerar los vértices en orden decreciente de f [u].4.- La salida son los vérticesde cada árbol de la foresta del paso 3. Cada árbol es una componente fuertemente conexa separada.
No haremos una demostración rigurosa, pero si daremos algunos elementos que ayudan a su entendimiento.Cuando se recorre un grado en DFS se tiene: si v es un descendiente de u entonces f[v]
Como en BFS, inicialmente el algoritmo colorea los vértices con blanco. Luego éstos pasan a plomo y luegonegro. Aquí el color plomo es usado para definir nodos cuyos descendientes están siendo visitados.
int tiempo; /* global */int d[N], f[N], p[N], color[N]; /* Arreglos de tiempo de entrada, tiempo desalida, padres, y color */
DFS(G) { /* pseudo-código */ for ( cada vértice u  V[G]) { color [u] =Blanco; p[u] = NULL; } tiempo = 0; for (cada vértice u  V[G]) if (color[u] == Blanco)DFS_visit(u);}
DFS_visit (u) /* pseudo-código */ color [u]= Plomo; /* Vértice Blanco u es visitado, ingresamos a su sub-árbol */ d[u] = ++tiempo; /* el tiempo se incrementa cada vez que“entramos y salimos” de un nodo*/ for ( cada v  Adj [u] ) { /* explora arcos (u,v) */ if (color [v] == Blanco) { p [v] = u; DFS_visit(v); } } color [u] = Negro; /* ennegrezca u, salimos...