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:
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.
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.
Análisis de complejidad
Complejidad de tiempo: O (V + E), V es el número de nodos y E es el número de aristas.
Complejidad espacial: O (V), matriz de tamaño V para almacenar el color.
Gracias por leer este tutorial.
Añadir comentario