OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Componentes conexas ======

==== Definición y propiedades ====
Recordamos la definición de componente conexa. Dado un grafo $G$ **no dirigido**, una //componente conexa// es un conjunto de nodos **maximal** de $G$ tal para cada par de nodos de la componente hay un camino que los une. Con maximal queremos decir que no se le puede agregar ningun nodo más a la componente.

Decir que para cualquier par de nodos hay un camino que los une, es equivalente a que de un nodo $v_0$ en particular se pueda llegar a cualquier otro por medio de caminos. Es claro que la primera implica la segunda. Para ver que la segunda implica la primera, tomamos $u$ y $w$ nodos cualquiera de la componente, queremos ver que hay un camino que une $u$ con $w$. Pero hay un camino que une $u$ con $v_0$ y uno que une $v_0$ con $w$, luego, uniendo estos dos caminos conseguimos uno de $u$ a $w$.

Esto nos dice que la componente conexa de un nodo $v$ son los nodos desde los que se puede llegar a partir de $v$. Por lo que cada nodo pertenece a una sola componente conexa. Es decir, las componentes conexas parten a los nodos de $G$ en conjuntos sin elementos en común.

==== Algoritmo para hallarlas ====
La última observación nos dice cómo podemos hallar las componentes conexas de un grafo $G$. Simplemente para cada nodo $v$ buscamos todos los nodos a los que se puede llegar a partir de $v$. Esto se puede hacer lanzando un DFS a partir de $v$. Los nodos a los que alcance el DFS serán la componente conexa de $v$. Para no repetir componentes, podemos guardar para qué nodos ya encontramos su componente y para ellos no lanzar el DFS.

Este es un posible algoritmo, lo que hacemos es numerar las componentes en el orden que las encontramos y devoler un vector que nos dice para cada nodo a qué componente pertenece:

<code cpp>

void dfs(int nodo, vector<vector<int>>& grafo, vector<int>& componente, int componenteActual) {
    // agregamos el nodo a la componente
    componente[nodo] = componenteActual;
    for(int: vecino in grafo[nodo]) {
        if(componente[vecino] != componenteActual) {
            dfs(vecino, grafo, componente, componenteActual);
        }
    }
}

vector<vector<int>> hallarComponentesConexas(vector<vector<int>>& grafo) {
    int n = grafo.size();
    // vector que guarda a qué componente pertenece cada nodo
    vector<int> componente(n, -1);
    int cantidadComponentes = 0;
    
    for(int i = 0; i < n; i++) {
        // si no encontramos ya la componente del nodo i
        if(componente[i] == -1) {
            // marcamos a todos los nodos de la componente de i con el número cantidadComponentes
            dfs(i, grafo, componente, cantidadComponentes);
            cantidadComponentes++;
        }
    }
    
    // Se puede devolver directamente el vector componente si nos es más cómodo para el problema
    vector<vector<int>> componentes(cantidadComponentes);
    for(int i = 0; i < n; i++) {
        componentes[componente[i]].push_back(i);
    }
    return componentes;
}

</code>

==== Análisis de complejidad ====

Es claro que todo salvo el primer for es $O(n)$ donde $n$ es la cantidad de nodos de $G$.
Para el for que hace los DFs. El DFS lanzado desde $i$ recorre todos los nodos de la componente de $i$ y todas sus aristas y nada más que eso. Luego es $O(n_i + m_i)$ donde $n_i$ y $m_i$ son la cantidad de nodos y aristas respectivamente de la componente de $i$. Luego el costo total del for es $O(n)$ más la suma de $O(n_i + m_i)$ por cada DFS que lanzamos. Pero lanzamos un DFS por componente, luego la suma de los $n_i$ es la suma de las cantidades de nodos de todas las componentes, que es $n$. Y, análogamente la suma de los $m_i$ es la suma de la cantidades de aristas de todas las componentes, que es $m$. Luego el for tiene complejidad $O(n+m)$ y como es lo más costoso del algoritmo, el algoritmo queda $O(n+m)$.

==== Grafos conexos ====
Un grafo $G$ es conexo si de cualquier nodo se puede llegar a cualquier otro. Esto es equivalente a decir que hay una sola componente conexa. Luego, podemos chequear si un grafo es conexo usando el algoritmo anterior y chequeando que quede una sola componente. Se puede hace algo mas simple para este caso que es simplemente lanzar un sólo DFS desde cualquier nodo $v$, por ejemplo el nodo $0$, y verificar que visite a todos los nodos del grafo.
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
