跳至主要內容

133. 克隆图


133. 克隆图open in new window

🟠   🔖  深度优先搜索 广度优先搜索 哈希表  🔗 力扣open in new window LeetCodeopen in new window

题目

Given a reference of a node in a connectedopen in new window undirected graph.

Return a deep copyopen in new window (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;
}

测试用例格式:

简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1val = 1),第二个节点值为 2val = 2),以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

提示:

  • 节点数不超过 100
  • 每个节点值 Node.val 都是唯一的,1 <= Node.val <= 100
  • 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
  • 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
  • 图是连通图,你可以从给定节点访问到所有节点。

解题思路

克隆图的常见解法是使用深度优先搜索(DFS)或广度优先搜索(BFS)。以深度优先搜索为例,可以通过递归实现图的克隆。在递归的过程中,使用 visited 哈希表来记录已经访问过的节点,避免重复遍历。

  1. 使用一个哈希表 visited 来存储原图节点和克隆图节点的映射关系。键为原图节点,值为克隆图节点。
  2. 定义一个 DFS 函数,输入为原图节点 node,在函数中进行如下操作:
    • 如果 node 为空,直接返回 null
    • 如果 nodevisited 中,说明已经访问过,直接返回对应的克隆图节点。
    • 否则,创建一个克隆图节点,并将其放入 visited 中,键为 node,值为 cloneNode
    • node 的邻居进行递归调用 DFS,并将结果添加到 visited.get(node) 的邻居列表中。
  3. 最后返回克隆图的起始节点。

当然也有人写 DFS 时不习惯返回值,这样更清晰易懂一些,详见解法二。

代码

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);
};

相关题目

题号标题题解标签难度
138随机链表的复制open in new window[✓]哈希表 链表
1485克隆含随机指针的二叉树 🔒open in new window 深度优先搜索 广度优先搜索 2+
1490克隆 N 叉树 🔒open in new window 深度优先搜索 广度优先搜索 1+