Búsqueda de componentes conexas en un grafo

Se da un grafo no dirigido $G$ con $n$ nodos y $m$ aristas. Hay que encontrar en él todas las componentes conexas, es decir, varios grupos de vértices tales que dentro de un grupo cada vértice es alcanzable desde cualquier otro y no existe camino entre grupos distintos.

Un algoritmo para resolver el problema

• Para resolver el problema, podemos usar Búsqueda en Profundidad o Búsqueda en Anchura.

• De hecho, haremos una serie de rondas de DFS: la primera ronda empezará desde el primer nodo y se recorrerán (encontrarán) todos los nodos de la primera componente conexa. Luego encontramos el primer nodo no visitado de los que quedan y ejecutamos Búsqueda en Profundidad sobre él, encontrando así una segunda componente conexa. Y así sucesivamente, hasta que todos los nodos estén visitados.

• El tiempo de ejecución asintótico total de este algoritmo es $O(n + m)$: de hecho, este algoritmo no se ejecutará dos veces sobre el mismo vértice, lo que significa que cada arista se verá exactamente dos veces (en un extremo y en el otro).

Implementación

int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;
 
void dfs(int v) {
    used[v] = true;
    comp.push_back(v);
    for (int u : adj[v]) {
        if (!used[u])
            dfs(u);
    }
}
 
void find_comps() {
    used.assign(n, false);
    for (int v = 0; v < n; ++v) {
        if (!used[v]) {
            comp.clear();
            dfs(v);
            cout << "Component:" ;
            for (int u : comp)
                cout << ' ' << u;
            cout << endl ;
        }
    }
}

• La función más importante que se usa es find_comps(), que encuentra y muestra las componentes conexas del grafo.

• El grafo se almacena en representación de lista de adyacencia, es decir, adj[v] contiene una lista de vértices que tienen aristas desde el vértice v.

• El vector comp contiene una lista de nodos de la componente conexa actual.

Implementación iterativa del código

Las funciones con recursión profunda son, en general, problemáticas. Cada llamada recursiva requiere un poco de memoria en la pila, y por defecto los programas solo tienen una cantidad limitada de espacio de pila. Así, si se hace un DFS recursivo sobre un grafo conexo con millones de nodos, se puede caer en desbordamientos de pila.

Siempre es posible convertir un programa recursivo en un programa iterativo, manteniendo manualmente una estructura de datos de pila. Como esta estructura de datos se asigna en el heap, no ocurrirá un desbordamiento de pila.

int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;
 
void dfs(int v) {
    stack<int> st;
    st.push(v);
    
    while (!st.empty()) {
        int curr = st.top();
        st.pop();
        if (!used[curr]) {
            used[curr] = true;
            comp.push_back(curr);
            for (int i = adj[curr].size() - 1; i >= 0; i--) {
                st.push(adj[curr][i]);
            }
        }
    }
}
 
void find_comps() {
    used.assign(n, false);
    for (int v = 0; v < n ; ++v) {
        if (!used[v]) {
            comp.clear();
            dfs(v);
            cout << "Component:" ;
            for (int u : comp)
                cout << ' ' << u;
            cout << endl ;
        }
    }
}

Problemas de práctica

• SPOJ: CT23E 
• CODECHEF: GERALD07 
• CSES : Building Roads