Descripción de la tarea:  Dada una referencia de un nodo en un grafo no dirigido   . conexo  Devuelve una   (clon) del gráfico. copia profunda  Cada nodo del gráfico contiene un valor (   ) y una lista (   ) de sus vecinos. int List[Node]   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   , el segundo nodo con   , y así sucesivamente. El gráfico se representa en el caso de prueba mediante una lista de adyacencia. val == 1 val == 2    es una colección de   desordenadas que se utilizan para representar un gráfico finito. Cada lista describe el conjunto de vecinos de un nodo en el gráfico. Una lista de adyacencia listas  El nodo dado siempre será el primer nodo con   . Debe devolver la   como referencia al gráfico clonado. val = 1 copia del nodo dado     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    es único para cada nodo. Node.val  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

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

The Graph

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Este audio es producido en el idioma original de la historia!

Clone Graph Blind75 LeetCode Problema

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Toque para ganar: Telegram puede incorporar a los próximos 10 mil millones de usuarios de criptomonedas antes de Solana

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Toque para ganar: Telegram puede incorporar a los próximos 10 mil millones de usuarios de criptomonedas antes de Solana

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps