Clone graph

Title Description: give you a reference to a node in an undirected connected graph. Please return a deep copy (clone) of the graph.

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

See LeetCode's official website for an example.

Source: LeetCode
Link: https://leetcode-cn.com/problems/clone-graph/
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

Solution 1: depth first traversal

First, if the current node is empty, you can return it directly without processing.

Otherwise, a Map called visited is used to store the processed graph nodes and corresponding clone nodes. The recursive processing process is as follows:

• Judge whether the current node is in the visited. If it is, it indicates that it has been processed. Directly take out the clone of the current node from the visited and return it.
• Otherwise, clone a new clone node according to the current node, initialize the neighbor node of the new clone node as empty, and then add the current node and the new clone node to visited;
• Then, the neighbor nodes of the current node are processed recursively.

Finally, the clone node of the current node is returned.

Solution 2: breadth first traversal

Similarly, first, if the current node is empty, it does not need to be processed and returns directly.

Otherwise, you also need to initialize a Map, called visited, to store the processed graph nodes and corresponding clone nodes. First, add the current node and the nodes cloned by the current node to visited, then add the current node to a queue, and then process the nodes in the queue. You know that the queue is not empty. The process is as follows:

• Take out the head node of the queue as curNode;
• Traversing the neighbor nodes of the processing curNode node;
• If the current neighbor node is not in the visited, add it and the corresponding clone node to the visited and add it to the queue;
• Then add the clone node of the current neighbor node to the neighbor node list of the clone node of curNode.

Finally, the clone node of the initial node is returned.

Note: we still don't know much about graph related algorithms, so we have to 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
     *
     * @param node Current node
     * @return
     */
    public static GraphNode cloneGraph(GraphNode node) {
        if (node == null) {
            return node;
        }
        // If the node has been accessed, the corresponding clone node is directly retrieved from the hash table and returned
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

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

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

        return cloneNode;
    }

    /**
     * breadth-first search 
     *
     * @param node 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<>();
        // Adds 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<>()));

        // breadth-first search 
        while (!queue.isEmpty()) {
            // Take out the head node of the queue
            GraphNode curNode = queue.remove();
            // Traverse 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 neighbor node to queue
                    queue.add(neighbor);
                }

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

        return visited.get(node);
    }

    public static void main(String[] args) {

    }
}

[daily message] do it yourself and have plenty of food and clothing!