Java: compruebe si un grafo no dirigido es bipartito o no

Muy buenas, me llamo Miguel y hoy les traigo otro nuevo tutorial.

Planteamiento del problema

Dado un grafo no dirigido, devuelve verdadero si y solo si es bipartito.

Un grafo es bipartito si podemos dividir su conjunto de nodos en dos subconjuntos independientes A y B de modo que cada borde en el grafo tenga un nodo en A y otro nodo en B.

Ejemplo:

Gráfico bipartito

En los ejemplos anteriores, graph[i] es una lista de índices j para el cual el borde entre nodos i y j existe. Cada nodo es un número entero entre 0 y graph.length - 1.

Código:

class BipartiteGraph {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        //initially all graph are uncolored, so all entries are -1.
        Arrays.fill(color,-1);

        for(int start = 0; start < n; start++){
            Stack<Integer> stack = new Stack<>();
            stack.push(start);
            color[start] = 0; // 0 represents some color
            while (!stack.isEmpty()){
                Integer node = stack.pop();
                if (color[node] == -1){
                    for (int adj : graph[node]){ // loop through all the adjacent nodes of current node
                        if (color[adj] == -1){
                            stack.push(adj);
                            color[adj] = color[node] ^ 1; // color all the adjacent nodes with different color
                        }else if (color[adj] == color[node]){ // if adj nodes color is same, return false.
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

Explicación

El enfoque anterior es la coloración del grafo utilizando DFS.

Cree una matriz de tamaño igual al número de nodos e inicialice todos los valores con -1, que muestra inicialmente que todos los nodos están sin colorear.

Para realizar DFS, utilice una pila. Mantenga inicialmente el nodo de inicio en la pila y coloréelo. Utilice 0, 1, etc. para colorear los nodos. Luego, recorra todos los nodos adyacentes del nodo actual, si no están coloreados, coloree con un color diferente y repita el proceso para todos los nodos.

Si el color del nodo actual es el mismo que el del nodo adyacente a él, significa que no es posible colorear y el grafo no es un grafo bipartito.