Shulou(Shulou.com)06/03 Report--

A deep copy of a map method tutorial, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Preface

Before you do that, you need to figure out some concepts: what is a deep copy or a shallow copy?

Shallow copy: if you are copying a reference type (not a basic type), only one layer will be copied (nested objects will not be copied), and if the original object changes, the copied object will also change.

Deep copy: deep copy will copy multiple layers, and nested objects will be copied out, which is equivalent to opening up a new memory address to store the copied objects.

To put it more colloquially (perhaps not exactly), the shallow copy is like your twin brothers, your parents and relatives are the same, while the deep copy is like another parallel time and space, where there is another everything about you.

Now that we understand the deep and shallow copy and its difference, let's look at the graph, which is generally used to represent the relationship between nodes and nodes, which is often divided into directed graph and undirected graph. Here we take the undirected graph (bidirectional once connected) as the theme.

We generally have the adjacency matrix and the adjacency table to represent the graph. The adjacency matrix is more intuitive to express the connectivity of a graph, and the operation and maintenance is easier. In Java, we generally use a two-dimensional array to represent the adjacency matrix, and the values in the array can represent the weights of the two nodes.

The adjacency matrix represents a graph

Although it is simple to use adjacency matrix, one of the disadvantages is that it wastes more memory space, so in many cases, adjacency tables are used to represent a graph, which is usually a combination of arrays and linked lists. But there are also some special cases where the nodes are independent and do not need arrays.

The adjacency table represents a graph

Analysis of problems

If the graph is represented by an adjacency table and gives you a reference to a node in an undirected connected graph, please return a deep copy (clone) of the graph.

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

Class Node {public int val; public List neighbors;}

The source of the picture is buckle.

A reference to a node, how do you clone the graph?

If there is only one node, it is good to clone the node. If the node has only one layer of neighbors, then clone the list of neighbors (clone the List collection).

But the fact is that this node may have multiple layers of neighbors, and there may be complex relationships between neighbors.

A possible graph

Clone the whole graph, so every node of the graph has to be cloned, we need to use the search algorithm of graph theory to enumerate all nodes, and we need to find a way to clone the relationship between nodes in the process of traversal. The traversal method can be done using dfs or bfs, which is implemented using bfs here.

Whenever we encounter suffering, we can simulate the process of cloning. Through the following diagram, we can roughly understand that in the process of cloning, the biggest problem is to avoid creating duplicate nodes. That is, once a node is created, its reference may be used later.

Simulate the process of cloning

So how can we solve this problem? How can I quickly find a reference to the corresponding node?

The best method here is to use HashMap, where key saves the nodes in the cloned graph, and value is the corresponding node in the cloned graph, so that in the process of cloning a new graph, when we traverse the neighbors of the nodes in the cloned graph, we can use hashing to determine whether the value corresponding to this node exists (that is, whether this node exists in the cloned graph).

If there is, then directly use HashMap to find the corresponding node and put it in the newly created List in the clone diagram.

However, it does not mean that this node encounters for the first time. Clone this node, put it in hashMap corresponding to the cloned node, and then put it in the newly created List in the clone diagram.

The process goes something like this:

The change and function of Map in one of the processes

With the above analysis, you must have ideas and ideas for solving this problem. Here is the code implementation.

/ * / / Definition for a Node. Class Node {public int val; public List neighbors; public Node () {val = 0; neighbors = new ArrayList ();} public Node (int _ val) {val = _ val; neighbors = new ArrayList ();} public Node (int _ val, ArrayList _ neighbors) {val = _ val; neighbors = _ neighbors } * / class Solution {public Node cloneGraph (Node node) {if (node==null) return null; Mapmap=new HashMap (); / / Node mapping cloned node Queueoldqueue=new ArrayDeque (); / / bfs queue oldqueue.add (node); Node value=new Node (node.val); / / first create and map map.put (node, value) to the returned node While (! oldqueue.isEmpty ()) {Node oldnode=oldqueue.poll (); Node newnode=map.get (oldnode); / / find the mapping of this node corresponding to the clone (must exist) Listlist=oldnode.neighbors;// neighbor Listlistnew=new ArrayList () / / Clone neighbor for (Node team:list) {if (map.containsKey (team)) {listnew.add (map.get (team)) / / Point has been encountered before, directly added to the neighbor list} else {/ / this neighbor is encountered for the first time, you need to create a new node to assign the value Node no=new Node (team.val); map.put (team, no); / / Map listnew.add (no) Oldqueue.add (team); / / this point is encountered for the first time. Is it helpful for you to put it in the queue for bfs search}} newnode.neighbors=listnew;// to point the node's neighbors to list} return value;}}? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.