12 - Componentes conexas

Las componentes conexas son grupos de vértices que están unidos por algún camino entre sí. Dividen al grafo en “islas”: dentro de una isla puedes ir de cualquier nodo a otro, pero entre islas no hay ruta. Identificarlas ayuda a saber si el grafo está conectado, cuántas islas tiene y a concentrar cálculos o recorridos solo donde hace falta.

12.1 Definición

Una componente conexa es el grupo más grande posible de vértices donde cualquier pareja se puede alcanzar siguiendo las aristas en algún sentido. Si agregas un vértice de fuera, esa propiedad se rompe. En grafos dirigidos la idea cambia: allí importan los sentidos de las aristas y se definen las componentes fuertemente conexas, que se estudian aparte.

Abrir visualizador de componentes

12.2 Componentes conexas en no dirigidos

En grafos no dirigidos, cada componente es una isla de conectividad: dentro de ella todos se alcanzan, fuera no hay puente. Si empiezas un recorrido (BFS o DFS) en un vértice no visitado, ese mismo proceso pinta todos los nodos de su isla y te deja listos para saltar a la siguiente.

12.3 Detección con BFS

Para hallar todas las componentes con BFS, arrancas desde un vértice no visitado, exploras en anchura y marcas a todos los que alcanzas con el mismo identificador. Cuando la cola queda vacía, esa componente está completa; luego eliges otro vértice sin marcar y repites. Cada ejecución de BFS corresponde a una componente distinta.

12.4 Detección con DFS

El procedimiento es análogo usando DFS; la pila (explícita o recursiva) marca los vértices de la componente actual.

12.5 Implementación en C

#include <stdio.h>
#include <stdlib.h>

typedef struct Arista {
  int destino;
  struct Arista *sig;
} Arista;

typedef struct {
  int n;
  Arista **listas;
} Grafo;

void agregar(Grafo *g, int u, int v) {
  Arista *a = malloc(sizeof(Arista));
  a->destino = v;
  a->sig = g->listas[u];
  g->listas[u] = a;
  Arista *b = malloc(sizeof(Arista));
  b->destino = u;
  b->sig = g->listas[v];
  g->listas[v] = b;
}

void dfsComp(const Grafo *g, int u, int *visitado, int compId, int *componentes) {
  visitado[u] = 1;
  componentes[u] = compId;
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (!visitado[v]) dfsComp(g, v, visitado, compId, componentes);
  }
}

int main(void) {
  int n = 6;
  Grafo g = {0};
  g.n = n;
  g.listas = calloc(n, sizeof(Arista *));

  agregar(&g, 0, 1);
  agregar(&g, 1, 2);
  agregar(&g, 3, 4);

  int *visitado = calloc(n, sizeof(int));
  int *componentes = calloc(n, sizeof(int));
  int compId = 0;

  for (int u = 0; u < n; u++) {
    if (!visitado[u]) {
      dfsComp(&g, u, visitado, compId, componentes);
      compId++;
    }
  }

  printf("Cantidad de componentes: %d\n", compId);
  for (int u = 0; u < n; u++) {
    printf("Vertice %d -> componente %d\n", u, componentes[u]);
  }

  for (int u = 0; u < n; u++) {
    Arista *it = g.listas[u];
    while (it) {
      Arista *tmp = it;
      it = it->sig;
      free(tmp);
    }
  }
  free(g.listas);
  free(visitado);
  free(componentes);
  return 0;
}

12.6 Mostrar componentes encontradas

Al almacenar el arreglo componentes[u] puedes:

  • Imprimir cada componente agrupando vértices con el mismo id.
  • Filtrar consultas: verificar si componentes[u] == componentes[v] implica conectividad.
  • Crear subgrafos por componente para procesarlos de manera independiente.
Retornar