133. Clone Graph
給定一個連通無向圖中某個節點的引用。
返回該圖的深拷貝（克隆）。
圖中的每個節點包含一個值（int）和一個鄰居列表（List[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
測試用例格式：
為了簡單起見，每個節點的值與節點的索引相同（從 1 開始）。例如，第一個節點的值為 1，第二個節點的值為 2，依此類推。圖在測試用例中用鄰接列表表示。
鄰接列表是一組無序列表，用於表示有限圖。每個列表描述圖中某個節點的鄰居集合。
給定的節點將始終是值為 1 的第一個節點。你必須返回給定節點的克隆作為克隆圖的引用。
範例：
輸入：adjList = [[2,4],[1,3],[2,4],[1,3]] 輸出：[[2,4],[1,3],[2,4],[1,3]] 解釋：圖中有 4 個節點。 第一個節點（值 = 1）的鄰居是第二個節點（值 = 2）和第四個節點（值 = 4）。 第二個節點（值 = 2）的鄰居是第一個節點（值 = 1）和第三個節點（值 = 3）。 第三個節點（值 = 3）的鄰居是第二個節點（值 = 2）和第四個節點（值 = 4）。 第四個節點（值 = 4）的鄰居是第一個節點（值 = 1）和第三個節點（值 = 3）。
Python
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return None
# Dictionary to store the mapping from the original node to the cloned node
clone_map = {}
# Helper function to perform DFS and clone the graph
def dfs(node):
if node in clone_map:
return clone_map[node]
# Create a new node for the clone
clone_node = Node(node.val)
clone_map[node] = clone_node
# Iterate through the neighbors and recursively clone them
for neighbor in node.neighbors:
clone_node.neighbors.append(dfs(neighbor))
return clone_node
# Start the DFS from the given node
return dfs(node)
16.96MB, 40ms
C++
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
// Dictionary to store the mapping from the original node to the cloned node
unordered_map<Node*, Node*> clone_map;
// Helper function to perform DFS and clone the graph
function<Node*(Node*)> dfs = [&](Node* node) -> Node* {
if (clone_map.find(node) != clone_map.end()) {
return clone_map[node];
}
// Create a new node for the clone
Node* clone_node = new Node(node->val);
clone_map[node] = clone_node;
// Iterate through the neighbors and recursively clone them
for (Node* neighbor : node->neighbors) {
clone_node->neighbors.push_back(dfs(neighbor));
}
return clone_node;
};
// Start the DFS from the given node
return dfs(node);
}
};
11.78MB, 4ms
Javascript
/**
* // 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;
const cloneMap = new Map();
// Helper function to perform DFS and clone the graph
const dfs = (node) => {
if (cloneMap.has(node)) {
return cloneMap.get(node);
}
// Create a new node for the clone
const cloneNode = new _Node(node.val);
cloneMap.set(node, cloneNode);
// Iterate through the neighbors and recursively clone them
for (let neighbor of node.neighbors) {
cloneNode.neighbors.push(dfs(neighbor));
}
return cloneNode;
};
// Start the DFS from the given node
return dfs(node);
};
52.44MB, 61ms
