clone-graph

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given a reference of a node in a <a href="https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph" target="_blank">connected</a> undirected graph.

Return a <a href="https://en.wikipedia.org/wiki/Object_copying#Deep_copy" target="_blank">deep copy</a> (clone) of the graph.

Each node in the graph contains a value (<code>int</code>) and a list (<code>List[Node]</code>) of its neighbors.

<pre>
class Node {
 public int val;
 public List&lt;Node&gt; neighbors;
}
</pre>

&nbsp;

Test case format:

For simplicity, each node&#39;s value is the same as the node&#39;s index (1-indexed). For example, the first node with <code>val == 1</code>, the second node with <code>val == 2</code>, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with <code>val = 1</code>. You must return the copy of the given node as a reference to the cloned graph.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png" style="width: 454px; height: 500px;" />
<pre>
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)&#39;s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)&#39;s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)&#39;s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)&#39;s neighbors are 1st node (val = 1) and 3rd node (val = 3).
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2020/01/07/graph.png" style="width: 163px; height: 148px;" />
<pre>
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.
</pre>

Example 3:

<pre>
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the graph is in the range <code>[0, 100]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 100</code></li>
	<li><code>Node.val</code> is unique for each node.</li>
	<li>There are no repeated edges and no self-loops in the graph.</li>
	<li>The Graph is connected and all nodes can be visited starting from the given node.</li>
</ul>

cloneGraph

Clone Graph

Copy List with Random Pointer

copy-list-with-random-pointer

随机链表的复制

Clone Binary Tree With Random Pointer

clone-binary-tree-with-random-pointer

克隆含随机指针的二叉树

Clone N-ary Tree

clone-n-ary-tree

克隆 N 叉树

Depth-First Search

Breadth-First Search

Graph

Hash Table

&#32473;&#20320;&#26080;&#21521;&nbsp;<a href="https://baike.baidu.com/item/&#36830;&#36890;&#22270;/6460995?fr=aladdin" target="_blank">&#36830;&#36890;</a>&nbsp;&#22270;&#20013;&#19968;&#20010;&#33410;&#28857;&#30340;&#24341;&#29992;&#65292;&#35831;&#20320;&#36820;&#22238;&#35813;&#22270;&#30340;&nbsp;<a href="https://baike.baidu.com/item/&#28145;&#25335;&#36125;/22785317?fr=aladdin" target="_blank">&#28145;&#25335;&#36125;</a>&#65288;&#20811;&#38534;&#65289;&#12290;

&#22270;&#20013;&#30340;&#27599;&#20010;&#33410;&#28857;&#37117;&#21253;&#21547;&#23427;&#30340;&#20540; <code>val</code>&#65288;<code>int</code>&#65289; &#21644;&#20854;&#37051;&#23621;&#30340;&#21015;&#34920;&#65288;<code>list[Node]</code>&#65289;&#12290;

<pre>
class Node {
 public int val;
 public List&lt;Node&gt; neighbors;
}</pre>

&nbsp;

&#27979;&#35797;&#29992;&#20363;&#26684;&#24335;&#65306;

&#31616;&#21333;&#36215;&#35265;&#65292;&#27599;&#20010;&#33410;&#28857;&#30340;&#20540;&#37117;&#21644;&#23427;&#30340;&#32034;&#24341;&#30456;&#21516;&#12290;&#20363;&#22914;&#65292;&#31532;&#19968;&#20010;&#33410;&#28857;&#20540;&#20026; 1&#65288;<code>val = 1</code>&#65289;&#65292;&#31532;&#20108;&#20010;&#33410;&#28857;&#20540;&#20026; 2&#65288;<code>val = 2</code>&#65289;&#65292;&#20197;&#27492;&#31867;&#25512;&#12290;&#35813;&#22270;&#22312;&#27979;&#35797;&#29992;&#20363;&#20013;&#20351;&#29992;&#37051;&#25509;&#21015;&#34920;&#34920;&#31034;&#12290;

&#37051;&#25509;&#21015;&#34920; &#26159;&#29992;&#20110;&#34920;&#31034;&#26377;&#38480;&#22270;&#30340;&#26080;&#24207;&#21015;&#34920;&#30340;&#38598;&#21512;&#12290;&#27599;&#20010;&#21015;&#34920;&#37117;&#25551;&#36848;&#20102;&#22270;&#20013;&#33410;&#28857;&#30340;&#37051;&#23621;&#38598;&#12290;

&#32473;&#23450;&#33410;&#28857;&#23558;&#22987;&#32456;&#26159;&#22270;&#20013;&#30340;&#31532;&#19968;&#20010;&#33410;&#28857;&#65288;&#20540;&#20026; 1&#65289;&#12290;&#20320;&#24517;&#39035;&#23558;&nbsp;&#32473;&#23450;&#33410;&#28857;&#30340;&#25335;&#36125;&nbsp;&#20316;&#20026;&#23545;&#20811;&#38534;&#22270;&#30340;&#24341;&#29992;&#36820;&#22238;&#12290;

&nbsp;

&#31034;&#20363; 1&#65306;

<img alt="" src="https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/02/01/133_clone_graph_question.png" style="height: 500px; width: 500px;" />

<pre>
&#36755;&#20837;&#65306;adjList = [[2,4],[1,3],[2,4],[1,3]]
&#36755;&#20986;&#65306;[[2,4],[1,3],[2,4],[1,3]]
&#35299;&#37322;&#65306;
&#22270;&#20013;&#26377; 4 &#20010;&#33410;&#28857;&#12290;
&#33410;&#28857; 1 &#30340;&#20540;&#26159; 1&#65292;&#23427;&#26377;&#20004;&#20010;&#37051;&#23621;&#65306;&#33410;&#28857; 2 &#21644; 4 &#12290;
&#33410;&#28857; 2 &#30340;&#20540;&#26159; 2&#65292;&#23427;&#26377;&#20004;&#20010;&#37051;&#23621;&#65306;&#33410;&#28857; 1 &#21644; 3 &#12290;
&#33410;&#28857; 3 &#30340;&#20540;&#26159; 3&#65292;&#23427;&#26377;&#20004;&#20010;&#37051;&#23621;&#65306;&#33410;&#28857; 2 &#21644; 4 &#12290;
&#33410;&#28857; 4 &#30340;&#20540;&#26159; 4&#65292;&#23427;&#26377;&#20004;&#20010;&#37051;&#23621;&#65306;&#33410;&#28857; 1 &#21644; 3 &#12290;
</pre>

&#31034;&#20363; 2&#65306;

<img alt="" src="https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/02/01/graph.png" style="height: 148px; width: 163px;" />

<pre>
&#36755;&#20837;&#65306;adjList = [[]]
&#36755;&#20986;&#65306;[[]]
&#35299;&#37322;&#65306;&#36755;&#20837;&#21253;&#21547;&#19968;&#20010;&#31354;&#21015;&#34920;&#12290;&#35813;&#22270;&#20165;&#20165;&#21482;&#26377;&#19968;&#20010;&#20540;&#20026; 1 &#30340;&#33410;&#28857;&#65292;&#23427;&#27809;&#26377;&#20219;&#20309;&#37051;&#23621;&#12290;
</pre>

&#31034;&#20363; 3&#65306;

<pre>
&#36755;&#20837;&#65306;adjList = []
&#36755;&#20986;&#65306;[]
&#35299;&#37322;&#65306;&#36825;&#20010;&#22270;&#26159;&#31354;&#30340;&#65292;&#23427;&#19981;&#21547;&#20219;&#20309;&#33410;&#28857;&#12290;
</pre>

&nbsp;

&#25552;&#31034;&#65306;

<ul>
	<li>&#36825;&#24352;&#22270;&#20013;&#30340;&#33410;&#28857;&#25968;&#22312; <code>[0, 100]</code>&nbsp;&#20043;&#38388;&#12290;</li>
	<li><code>1 &lt;= Node.val &lt;= 100</code></li>
	<li>&#27599;&#20010;&#33410;&#28857;&#20540;&nbsp;<code>Node.val</code> &#37117;&#26159;&#21807;&#19968;&#30340;&#65292;</li>
	<li>&#22270;&#20013;&#27809;&#26377;&#37325;&#22797;&#30340;&#36793;&#65292;&#20063;&#27809;&#26377;&#33258;&#29615;&#12290;</li>
	<li>&#22270;&#26159;&#36830;&#36890;&#22270;&#65292;&#20320;&#21487;&#20197;&#20174;&#32473;&#23450;&#33410;&#28857;&#35775;&#38382;&#21040;&#25152;&#26377;&#33410;&#28857;&#12290;</li>
</ul>

Sunbelt Computer Software

PL/B Language Development and Support