Skip to content

Latest commit

 

History

History
206 lines (157 loc) · 7.17 KB

0133.md

File metadata and controls

206 lines (157 loc) · 7.17 KB
title description keywords
133. 克隆图
LeetCode 133. 克隆图题解，Clone Graph，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
133. 克隆图
克隆图
Clone Graph
解题思路
深度优先搜索
广度优先搜索
图
哈希表

133. 克隆图

🟠 Medium  🔖  深度优先搜索 广度优先搜索 图 哈希表  🔗 力扣 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 哈希表来记录已经访问过的节点，避免重复遍历。

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

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

代码

::: code-tabs

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

@tab DFS 无返回值版

/**
 * @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+ 🟠 🀄️ 🔗