LeetCode – 133 – clone figure

“This is the 29th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Cloning figure

Given a reference to a node in an undirected connected graph, return a deep copy (clone) of the graph.

Each Node in the diagram contains its value val (int) and a list of its neighbors (list[Node]).

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/cl… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: depth first traversal

First, if the current node is empty, no processing is required and return directly.

Otherwise, a Map (visited) is used to store the processed graph nodes and corresponding cloned nodes, and the recursive processing process is as follows:

• Judge whether the current node is in visited. If it is, it indicates that it has been processed. Then, directly extract the clone of the current node from Visited and return.
• Otherwise, a new clone node is cloned according to the current node, and the neighbor node of the newly cloned node is initialized as empty. Then, the current node and the new clone node are added to visited.
• The current node’s neighbors are then recursively processed.

Finally, the clone of the current node is returned.

Solution two: breadth-first traversal

Similarly, first of all, if the current node is empty, no processing, just return.

Otherwise, it is also necessary to initialize a Map, namely visited, to store the processed graph nodes and corresponding cloned nodes. First, add the current node and the node cloned by the current node to Visited, then add the current node to a queue, and process the nodes in the queue, knowing that the queue is not empty. The processing process is as follows:

• The header of the fetch queue is curNode.
• Iterate over the neighbor nodes that process the curNode node.
• If the current neighbor node is not visited, it and its corresponding clone node are added to Visited and added to the queue.
• Then add the clone of the current neighbor node to the list of neighbor nodes of the clone node of the curNode.

Finally, the clone of the original node is returned.

Note: graph related algorithms or understand not much, learn more.

import com.kaesar.leetcode.GraphNode;

import java.util.*;

public class LeetCode_133 {
    private static Map<GraphNode, GraphNode> visited = new HashMap<>();

    /** * depth-first traversal **@paramNode Current node *@return* /
    public static GraphNode cloneGraph(GraphNode node) {
        if (node == null) {
            return node;
        }
        // If the node has already been accessed, the corresponding clone is returned directly from the hash table
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Clone the current node
        GraphNode cloneNode = new GraphNode(node.val, new ArrayList<>());
        // Hash table storage
        visited.put(node, cloneNode);

        // Recursively process the neighbors of the current node
        for (GraphNode neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }

    /** * width first traverses **@paramNode Current node *@return* /
    public static GraphNode cloneGraph2(GraphNode node) {
        if (node == null) {
            return node;
        }

        HashMap<GraphNode, GraphNode> visited = new HashMap<>();

        Queue<GraphNode> queue = new LinkedList<>();
        // Add the current node to the queue
        queue.add(node);
        // Clone the first node and store it in the hash table
        visited.put(node, new GraphNode(node.val, new ArrayList<>()));

        // width first traversal
        while(! queue.isEmpty()) {// Fetch the head node of the queue
            GraphNode curNode = queue.remove();
            // Traverses the neighbor nodes of the current node
            for (GraphNode neighbor : curNode.neighbors) {
                if(! visited.containsKey(neighbor)) { visited.put(neighbor,new GraphNode(neighbor.val, new ArrayList<>()));
                    // Add the neighbor node to the queue
                    queue.add(neighbor);
                }

                // Update the neighbor node list of the current nodevisited.get(curNode).neighbors.add(visited.get(neighbor)); }}return visited.get(node);
    }

    public static void main(String[] args) {}}Copy the code

【 Daily Message 】 Do it yourself, have food and clothing!