Clone Graph Blind75 LeetCode Problema

Descripción de la tarea:

Dada una referencia de un nodo en un grafo no dirigido conexo .

Devuelve una copia profunda (clon) del gráfico.

Cada nodo del gráfico contiene un valor ( int ) y una lista ( List[Node] ) de sus vecinos.

 class Node { public int val; public List<Node> neighbors; }

Formato de caso de prueba:

Para simplificar, el valor de cada nodo es el mismo que el índice del nodo (1-indexado). Por ejemplo, el primer nodo con val == 1 , el segundo nodo con val == 2 , y así sucesivamente. El gráfico se representa en el caso de prueba mediante una lista de adyacencia.

Una lista de adyacencia es una colección de listas desordenadas que se utilizan para representar un gráfico finito. Cada lista describe el conjunto de vecinos de un nodo en el gráfico.

El nodo dado siempre será el primer nodo con val = 1 . Debe devolver la copia del nodo dado como referencia al gráfico clonado.

Ejemplo 1:

 Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Ejemplo 2:

 Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Ejemplo 3:

 Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.

Restricciones:

• El número de nodos en el gráfico está en el rango [0, 100] .
• 1 <= Node.val <= 100
• Node.val es único para cada nodo.
• No hay bordes repetidos ni bucles automáticos en el gráfico.
• El gráfico está conectado y todos los nodos se pueden visitar a partir del nodo dado.

Razonamiento:

Como siempre, observamos los problemas y puede parecer bastante desafiante. Como siempre sugiero, si te sientes atascado o no sabes cómo abordar el problema, comienza hablando contigo mismo. Así que tenemos un gráfico y necesitamos clonarlo, un pensamiento debe aparecer inmediatamente en tu cabeza. No hay forma de hacer una copia completa de algo sin recorrerlo o explorarlo por completo. Bien. ¿Qué enfoques conocemos para recorrer un gráfico/árbol? BFS correcto (búsqueda primero pan) o DFS (búsqueda primero en profundidad). ¿Importa cuál elegimos? No me parece. Acabamos de dar el primer paso en nuestro camino hacia la solución. Veamos un DFS simple.

 class Node { public int val; public List<Node> neighbors; public Node() { val = 0; neighbors = new ArrayList<Node>(); } public Node(int _val) { val = _val; neighbors = new ArrayList<Node>(); } public Node(int _val, ArrayList<Node> _neighbors) { val = _val; neighbors = _neighbors; } } public void traverseGraph(Node node) { LinkedList<Node> queue = new LinkedList<>(); Set<Node> visitedNodes = new HashSet<>(); queue.addLast(node); while (!queue.isEmpty()) { Node current = queue.removeFirst(); // we already visited this node, we should ship exploring this path if (!visitedNodes.add(current)) { continue; } // just because every node contains a list of it's neighbors we can add all of them to our queue queue.addAll(current.neighbors); } }

Entonces ahora tenemos el código para explorar el gráfico dado, pero no solo necesitamos visitarlos sino también crear una copia para cada nodo en un gráfico. Intencionalmente no les digo nada sobre la creación de enlaces entre los nodos que vamos a copiar, lo tocaré más adelante, por ahora concentrémonos en nuestro esfuerzo para crear copias. Necesitamos alguna estructura de datos para almacenar la relación entre el nodo original y su copia. Al mismo tiempo, debe admitir 2 funciones, una para agregar un enlace y la segunda para obtener la copia. Debería funcionar lo más rápido posible. Algunos de ustedes ya lo habrán adivinado: HashMap en Java o HashTable en otros lenguajes de programación. Necesitamos agregar solo unas pocas líneas de código en nuestra función.

 public void traverseGraphAndCreateCopyOfNodes(Node node, Map<Node, Node> originalToCopyMap) { LinkedList<Node> queue = new LinkedList<>(); Set<Node> visitedNodes = new HashSet<>(); queue.addLast(node); while (!queue.isEmpty()) { Node current = queue.removeFirst(); // we already visited this node, we should ship exploring this path if (!visitedNodes.add(current)) { continue; } Node copy = new Node(current.val); originalToCopyMap.put(current, copy); // just because every node contains a list of it's neighbors we can add all of them to our queue queue.addAll(current.neighbors); } }

Echemos un vistazo a lo que hemos hecho hasta ahora. Imaginemos que nos dan este gráfico

Entonces en nuestro originalToCopyMap tenemos algo como esto

Lo único que queda. Necesitamos conectar de alguna manera los nodos clonados para que tengan exactamente las mismas conexiones entre ellos que tiene el gráfico original. ¿Cómo hacemos eso? ¿Podemos utilizar originalToCopyMap? La respuesta debemos usarla. Vamos a hacer la segunda poligonal después de hacer la primera, usando datos de ese mapa podemos copiar/establecer conexiones entre nodos clonados para que repitan el original.

 public void traverseGraphAndCreateLinksBetweenNodes(Node node, Map<Node, Node> originalToCopyMap) { LinkedList<Node> queue = new LinkedList<>(); Set<Node> visitedNodes = new HashSet<>(); queue.addLast(node); while (!queue.isEmpty()) { Node current = queue.removeFirst(); // we already visited this node, we should ship exploring this path if (!visitedNodes.add(current)) { continue; } Node clonedCurrent = originalToCopyMap.get(current); for (Node neighborOfCurrentNode: current.neighbors) { clonedCurrent.neighbors.add(originalToCopyMap.get(neighborOfCurrentNode)); } // just because every node contains a list of it's neighbors we can add all of them to our queue queue.addAll(current.neighbors); } }

Después de ejecutar el método traverseGraphAndCreateLinksBetweenNodes, deberíamos obtener este gráfico copiado

Solución:

Usando 3 simples pasos resolvimos el problema dado. Aquí está el código fuente completo

Solución

 class Node { public int val; public List<Node> neighbors; public Node() { val = 0; neighbors = new ArrayList<Node>(); } public Node(int _val) { val = _val; neighbors = new ArrayList<Node>(); } public Node(int _val, ArrayList<Node> _neighbors) { val = _val; neighbors = _neighbors; } } public Node cloneGraph(Node node) { if (node == null) { return null; } Map<Node, Node> originalToCopyMap = new HashMap<>(); traverseGraphAndCreateCopyOfNodes(node, originalToCopyMap); traverseGraphAndCreateLinksBetweenNodes(node, originalToCopyMap); return originalToCopyMap.get(node); } public void traverseGraphAndCreateCopyOfNodes(Node node, Map<Node, Node> originalToCopyMap) { LinkedList<Node> queue = new LinkedList<>(); Set<Node> visitedNodes = new HashSet<>(); queue.addLast(node); while (!queue.isEmpty()) { Node current = queue.removeFirst(); // we already visited this node, we should ship exploring this path if (!visitedNodes.add(current)) { continue; } Node copy = new Node(current.val); originalToCopyMap.put(current, copy); // just because every node contains a list of it's neighbors we can add all of them to our queue queue.addAll(current.neighbors); } } public void traverseGraphAndCreateLinksBetweenNodes(Node node, Map<Node, Node> originalToCopyMap) { LinkedList<Node> queue = new LinkedList<>(); Set<Node> visitedNodes = new HashSet<>(); queue.addLast(node); while (!queue.isEmpty()) { Node current = queue.removeFirst(); // we already visited this node, we should ship exploring this path if (!visitedNodes.add(current)) { continue; } Node clonedCurrent = originalToCopyMap.get(current); for (Node neighborOfCurrentNode: current.neighbors) { clonedCurrent.neighbors.add(originalToCopyMap.get(neighborOfCurrentNode)); } // just because every node contains a list of it's neighbors we can add all of them to our queue queue.addAll(current.neighbors); } }

Podemos detenernos aquí y alegrarnos por otro problema resuelto. PERO algunos de ustedes habrán notado que tenemos algunos duplicados en nuestro código que podemos eliminar y usemos la recursión para hacer que nuestro código sea más limpio y más corto.

 public Node cloneGraph(Node node) { Map<Node, Node> map = new HashMap<>(); return cloneGraph(node, map); } private Node cloneGraph(Node node, Map<Node, Node> map) { if (node == null) { return null; } if (map.containsKey(node)) { return map.get(node); } Node copy = new Node(node.val); map.put(node, copy); for (Node neighbor : node.neighbors) { copy.neighbors.add(cloneGraph(neighbor, map)); } return copy; }

Enfoque recursivo

Espero que este artículo lo ayude a comprender la lógica detrás de este problema y lo use para resolver otras tareas.

¡Te veo pronto!

También publicado aquí

Foto de Thomas Couillard en Unsplash