Wechat search a search: [Bigsai], attention is more wonderful if helpful welcome a key triplet

preface

Earlier, I wrote about depth copying in Java, which is object-based copying, but looking at data structures and algorithms, have you ever considered how to copy a graph? (Undirected graph)

Before you do that, you need to understand some concepts: what is deep copy and shallow copy?

Shallow copy: If you copy a reference type (not a basic type), only one layer is copied (nested objects are not copied). If the original object is changed, the copied object is also changed.

Deep copy: In deep copy, multiple layers are copied and nested objects are also copied out, which is equivalent to creating a new memory location for storing the copied objects.

In layman’s terms (which may not be entirely accurate), a shallow copy is like your twin brother. And the deep copy is like another parallel time, where there is another you of everything.

Now that we know the difference between shallow-depth copying and shallow-depth copying, let’s look at graphs. Graphs are generally used to represent nodes and relationships between nodes, and are often divided into directed graphs and undirected graphs. Here we will focus on undirected graphs (bidirectional once connected).

The representation of graph generally includes adjacency matrix and adjacency list. Adjacency matrix is more intuitive to represent the connectivity of a graph, which is easier to operate and maintain. In Java, 2d array is generally used to represent adjacency matrix, and the values in the array can represent the weights of two nodes.

It’s easy to use an adjacency matrix but there’s one thing that’s bad about itWaste a lot of memory spaceSo in many cases it is still usedAdjacency listAn adjacency list is usually a combination of an array and a linked list. But there are special cases where each node is independent and not connected to an array.

Problem analysis

If the graph is represented by an adjacency list and gives you 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]).

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

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

If there is only one node, clone that node. If the node has only one layer of neighbors, clone the List of neighbors (clone List collection).

But the reality is that this node may have multiple layers of neighbors, and the neighbors may have complex relationships.

Clone the whole graph, so every node of the graph should be cloned, we need to use the graph theory search algorithm to enumerate all nodes, and in the process of traversal we need to find a way to clone the relationship between nodes. The traversal method can be DFS or BFS, and BFS is used here.

Whenever we encounter hardships, we can simulate the process of cloning. Through the following picture, we can roughly understand the process of cloning. The biggest problem is toAvoid creating duplicate nodes. That is, once a node is created its references may be used later.

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

The best method here is to use HashMap

, where key is the Node in the cloned graph and value is the corresponding Node in the cloned graph. In this way, in the process of cloning a new graph, when we traverse the neighbor of the Node in the cloned graph, The hash can be used to determine whether the value corresponding to this node exists (that is, whether this node exists in the clone graph).
,node>

  • Use it directly if it existsHashMapFind the corresponding node and add it to the newly created List in the clone diagram.
  • But if it doesn’t exist, it’s the first time you’ve encountered this node, so clone this node and put it inhashMapAnd then put it into the newly created List in the clone diagram.

The process looks something like this:

With the above analysis, you must have some ideas about how to solve 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;
	    	Map<Node, Node>map=new HashMap<Node, Node>();// The node maps the cloned node
	    	
	    	Queue<Node>oldqueue=new ArrayDeque<Node>();/ / BFS queue
	    	oldqueue.add(node);
	    	Node value=new Node(node.val);// Create and map the returned node
	    	map.put(node, value);
	    	while(! oldqueue.isEmpty()) { Node oldnode=oldqueue.poll(); Node newnode=map.get(oldnode);// Find the clone mapping for this node (it must exist)
				List<Node>list=oldnode.neighbors;/ / neighbor
				List<Node>listnew=new ArrayList<Node>();// Clone the neighbor
				for(Node team:list)
				{
					if(map.containsKey(team))
					{
						listnew.add(map.get(team));
						// The dot was encountered before and added directly to the neighbor list
					}
					else {// Create a new node to assign a value to the neighbor
						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 and will be queued for BFS search
					}
				}
				newnode.neighbors=listnew;// Point the node's neighbor to the list
			}
	    	returnvalue; }}Copy the code

This content is over here, but also hope you can one key triple support! New people for attention, praise support, more exciting welcome to pay attention to the public number: [Bigsai]!