133. 克隆图
133. 克隆图
🟠 🔖 深度优先搜索
广度优先搜索
图
哈希表
🔗 力扣
LeetCode
题目
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int
) and a list (List[Node]
) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1
, the second node with val == 2
, 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 val = 1
. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
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)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:
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.
Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints:
- The number of nodes in the graph is in the range
[0, 100]
. 1 <= Node.val <= 100
Node.val
is unique for each node.- There are no repeated edges and no self-loops in the graph.
- The Graph is connected and all nodes can be visited starting from the given node.
题目大意
给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 val(int)
和其邻居的列表(list[Node]
)。
class Node {
public int val;
public List<Node> neighbors;
}
测试用例格式:
简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1
(val = 1
),第二个节点值为 2
(val = 2
),以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点(值为 1
)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
提示:
- 节点数不超过
100
。 - 每个节点值
Node.val
都是唯一的,1 <= Node.val <= 100
。 - 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
- 由于图是无向的,如果节点
p
是节点q
的邻居,那么节点q
也必须是节点p
的邻居。 - 图是连通图,你可以从给定节点访问到所有节点。
解题思路
克隆图的常见解法是使用深度优先搜索(DFS)或广度优先搜索(BFS)。以深度优先搜索为例,可以通过递归实现图的克隆。在递归的过程中,使用 visited
哈希表来记录已经访问过的节点,避免重复遍历。
- 使用一个哈希表
visited
来存储原图节点和克隆图节点的映射关系。键为原图节点,值为克隆图节点。 - 定义一个 DFS 函数,输入为原图节点
node
,在函数中进行如下操作:- 如果
node
为空,直接返回null
。 - 如果
node
在visited
中,说明已经访问过,直接返回对应的克隆图节点。 - 否则,创建一个克隆图节点,并将其放入
visited
中,键为node
,值为cloneNode
。 - 对
node
的邻居进行递归调用 DFS,并将结果添加到visited.get(node)
的邻居列表中。
- 如果
- 最后返回克隆图的起始节点。
当然也有人写 DFS 时不习惯返回值,这样更清晰易懂一些,详见解法二。
代码
/**
* // Definition for a Node.
* function Node(val, neighbors) {
* this.val = val === undefined ? 0 : val;
* this.neighbors = neighbors === undefined ? [] : neighbors;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function (node) {
if (!node) return null;
let visited = new Map();
const dfs = (node) => {
if (!node) return null;
if (visited.has(node)) return visited.get(node);
visited.set(node, new Node(node.val));
for (let i of node.neighbors) {
visited.get(node).neighbors.push(dfs(i));
}
return visited.get(node);
};
return dfs(node);
};
/**
* @param {_Node} node
* @return {_Node}
*/
var cloneGraph = function (node) {
let copy = new Map();
const dfs = (node) => {
if (!node) return;
if (copy.has(node)) return;
copy.set(node, new Node(node.val));
for (let item of node.neighbors) {
dfs(item);
copy.get(node).neighbors.push(copy.get(item));
}
};
dfs(node);
return copy.get(node);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
138 | 随机链表的复制 | [✓] | 哈希表 链表 | |
1485 | 克隆含随机指针的二叉树 🔒 | 树 深度优先搜索 广度优先搜索 2+ | ||
1490 | 克隆 N 叉树 🔒 | 树 深度优先搜索 广度优先搜索 1+ |