Componentes conexas y bicoloración de grafos

Ya conocemos el BFS y DFS. Vamos a ver un par de aplicaciones de estos algoritmos.

Componentes conexas

Dado un grafo no dirigido G nos puede interesar saber cuántas componentes conexas hay y, si dados dos vertices, comparten componente conexa. Qué es una componente conexa? Un conjunto de vertices tal que empezando en uno de ellos cualquiera podemos acceder al resto moviéndonos por las aristas del grafo.

Por ejemplo, si nuestro grafo representa paradas de metro y conexiones entre ellas, que dos vertices compartan componente conexa indica que podemos llegar de una parada a otra transportándonos por el metro.

Vamos a ver cómo utilizar un BFS o DFS indistintamente para descubrir todas las componentes conexas de un grafo. La idea es empezar por un vértice cualquiera del grafo y mediante un BFS o DFS descubrir el resto de nodos que son accesibles y marcarlos adecuadamente como integrantes de la misma componente conexa. Seguidamente recorreremos el resto de vertices del grafo y, si hay alguno que no haya estado marcado como integrante de una componente conexa anterior, lo usaremos para descubrir y marcar su componente conexa.

vector <int> visited (n, -1); 
// visited[v] vale -1 si no hemos visitado v y en caso contrario indica a que componente conexa pertenece
vector <vector <int> > G; //grafo G[v] es un vector con los vecinos de v

// dado un nodo v visita a todos los nodos conectados a v
void dfs (int v, int componente_conexa) {
    if (visited[v] != -1) return;
    visited[v] = componente_conexa;

    for (int i = 0; i < G[v].size(); ++i){ //iteramos por todos los vecinos
        int u = G[v][i];
        dfs(u, componente_conexa); //lo visitamos
    }
}

// la funcion devuelve el numero de componentes conexas de G y ademas guarda en visited a que 
// componente conexa pertenece cada nodo
int descubre_componentes_conexas() {
   int numero_componentes_conexas = 0;
   for (int i = 0; i < n; ++i) {
        if(visited[i] != -1) continue;
        // marcara todos los vecinos de i como miembros de la misma componente conexa
        dfs(i, numero_componentes_conexas); 
        numero_componentes_conexas++;
   }
}

La implementación con un BFS seria similar.

 

2-coloración

Otra pregunta clásica sobre grafos es si podemos colorearlo con dos colores. Colorear un grafo quiere decir asignar un color a cada vértice tal que ningún par de vertices conectados por una arista tengan el mismo color.

Si esto se puede hacer con solo dos colores decimos que el grafo es bipartito. Esto se debe a que tenemos una partición en dos conjuntos de vértices: los pintados de color azul y los pintados de color rojo. Ningún azul es vecino de otro azul y de la misma manera para los rojos.

Podemos resolver este problema de manera muy similar al anterior. Ahora en vez de apuntarnos a que componente conexa pertenece el vértice nos apuntaremos de qué color lo hemos pintado. Cuando estemos en un vértice obligaremos a pintar a sus vecinos del color contrario. Si uno de sus vecinos ya lo hemos pintado antes de su mismo color sabemos que no será posible 2-colorear en grafo. Si acabamos sin haber tenido este problema quiere decir que el grafo es 2-coloreable.

vector <int> colores (n, -1); 
// visited[v] vale -1 si no hemos visitado v y en caso contrario indica de que color esta pintado (0 o 1)
vector <vector <int> > G; //grafo G[v] es un vector con los vecinos de v

// devuelve false si ha encontrado que el grafo no es 2-coloreable
bool dfs (int v, int color) {
    if (colores[v] != -1) return true;
    colores[v] = color;

    for (int i = 0; i < G[v].size(); ++i){ //iteramos por todos los vecinos
        int u = G[v][i];
        // si un nodo y su vecino tienen el mismo color sabemos que el grafo no es 2-coloreable
        if (colores[i] == colores[u]) return false;
        // con !colores hacemos que sus vecinos tengan que ser pintados de 1 si el esta pintado de 0 o viceversa.
        if (not dfs(u, !color)) {
           // si encontramos un problema visitando sus vecinos sabemos que el grafo no es 2-coloreable
            return false; 
        }
    }
   return true;
}

// devuelve true sii el grafo es 2-coloreable
bool es_2_coloreable() {
   for (int i = 0; i < n; ++i) {
        if (colores[i] != -1) continue; 
       // si encontramos algun problema el grafo no es 2-coloreable
        if (not dfs(i, 0))
            return false;
   } 
   // si hemos visitado todos los nodos sin problemas el grafo es 2-coloreable
   return true;
}

Igual que antes se puede implementar el algoritmo mediante un BFS, aunque suele ser algo más farragoso.