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.
Enlace de Github a la solución: https://github.com/shivanidwivedi/JavaProgramming/commit/c03774df67f540304058cda1f0a70f713e57b437.
Gracias por leer.
Añadir comentario