Algoritmos y Estructura de Datos

Componentes Fuertemente conexos

En teoría de grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus subgrafos maximales fuertemente conexos. Estos subgrafos forman una partición del grafo.

Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo.

El cálculo de los componentes fuertemente conexos de un grafo es uno de los problemas fundamentales de la Teoría de los grafos. El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan​ en 1970 a base de una búsqueda en profundidad (depth-first search). Otros algoritmos aparecen en los principales textos sobre algorítmica.

Algoritmo de Kosaraju

Para hallar las SCC (Componentes Fuertemente conexos) de un grafo dirigido G :

1. Realiza un DFS sobre G y enumera los vértices en orden de terminación de las llamadas recursivas.

                void dfs(int v){
                    visited[v] = true;
                    start[v] = count;
                    ++count;
                    
                    for(int i=G[v].size()-1;i>=0;--i){
                        if(!visited[G[v][i]]) dfs(G[v][i]);
                    }
                    
                    finish[v] = count;
                    ++count;
                }
            

2. Construye un nuevo grafo G_T invirtiendo la dirección de todo arco en G.

3. Realiza un DFS sobre G_T empezando por el vértice que fue enumerado con el mayor valor de acuerdo a la numeración asignada en el paso (1). Si el DFS no alcanza todos los vértices, empieza el siguiente DFS desde el vértice restante enumerado con el mayor valor.

4. Cada árbol obtenido luego del DFS es una componente fuertemente conexa.

Implementacion en C++

                #include < stack>
                    #include < queue>
                    #include < vector>
                    #include < cstring>
                    
                    using namespace std;
                    
                    #define MAX_V 500
                    
                    int V, num_scc, scc[MAX_V];
                    vector< vector< int> > G;
                    vector< vector< int> > GT;
                    bool visited[MAX_V];
                    stack< int> S;
                    queue< int> Q;
                    
                    void dfs(int v){
                        visited[v] = true;
                        
                        for(int i=G[v].size()-1;i>=0;--i)
                            if(!visited[G[v][i]])
                                dfs(G[v][i]);
                        
                        S.push(v);
                    }
                    
                    void bfs(int v){
                        Q.push(v);
                        visited[v] = true;
                        
                        int aux;
                        
                        while(!Q.empty()){
                            aux = Q.front();
                            scc[aux] = num_scc;
                            Q.pop();
                            
                            for(int i=GT[aux].size()-1;i>=0;i--){
                                if(!visited[GT[aux][i]]){
                                    Q.push(GT[aux][i]);
                                    visited[GT[aux][i]] = true;
                                }
                            }
                        }
                    }
                    void SCC(){
                        memset(visited,false,sizeof(visited));
                        
                        for(int i=0;i< V;++i) if(!visited[i]) dfs(i);
                        
                        num_scc = 0;
                        int aux;
                        
                        memset(visited,false,sizeof(visited));
                        
                        while(!S.empty()){
                            aux = S.top();
                            S.pop();
                            
                            if(!visited[aux]){
                                bfs(aux);
                                ++num_scc;
                            }
                        }
                    }
            

Link de apoyo

Kosaraju's algorithm

Componentes fuertemente conectados

Componente fuertemente conexo