Grafos III

Componentes fuertemente conexas (SCC)

Componentes fuertemente conexas

Grafos DIRIGIDOS

Una SCC puede ser definida de la siguiente manera: "Si tomamos cualquier par de vertices u y v en la SCC, podemos encontrar una ruta de u a v y vice versa.

Solución 1: Algoritmo de Tarjan

Modificación de DFS

¿Recuerdan el dfs_low y el dfs_num?

                                              
public static void tarjanSCC( int u ){
    dfs_low[u] = dfs_num[u] = dfsCont;
    dfsCont++;
    s.push(u);
    visited[u] = true;
        
    int j, v;
        
    for( j = 0; j < ady[u].size(); j++ ){
        v = ady[u].get( j );
            
        if( dfs_num[v] == -1 ){
            tarjanSCC( v );
        }
            
        if( visited[v] ){
            dfs_low[u] = Math.min( dfs_low[u], dfs_low[v] );
        }
    }
        
    if( dfs_low[u] == dfs_num[u] ){
        cantSCC++;
        System.out.println("COMPONENTE CONEXA #" + cantSCC );
        while( !s.empty() ){
            v = s.peek();
            s.pop();
            visited[v] = false;
            System.out.println(v);
            if( u == v ) break;
        }
    }
        
}
                        
                    

Ejercicios propuestos