当前位置： 面试刷题>> 克隆图 (经典算法题500道)
### 题目描述
给定一个图，图由节点（vertices）和连接节点的边（edges）组成，每个节点都有一个唯一的标识符（ID）。图可能包含自环（即，节点可以连接到自己）和并行边（即，两个节点之间可以有多个边）。
图通过邻接表（adjacency list）表示，其中`graph`是一个字典（或哈希表），每个键是节点的ID，每个值是该节点的邻居列表（包含邻居节点的ID）。
实现一个函数`cloneGraph`，该函数返回图的深拷贝（深克隆），图中的每个节点都复制一次，并且图中的每条边都连接到新克隆的节点上。
### 示例
假设图由以下邻接表表示：
```
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
```
调用`cloneGraph(graph, 'A')`后，应返回以下图的深拷贝：
```
{
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E'],
'A_clone': ['B_clone', 'C_clone'],
'B_clone': ['A_clone', 'D_clone', 'E_clone'],
'C_clone': ['A_clone', 'F_clone'],
'D_clone': ['B_clone'],
'E_clone': ['B_clone', 'F_clone'],
'F_clone': ['C_clone', 'E_clone']
}
```
注意：返回的克隆图应包含原始图中所有节点的克隆，并且每个克隆节点都应连接到其相应的克隆邻居节点。
### PHP 示例代码
```php
class Node {
public $val;
public $neighbors;
function __construct($val = 0, $neighbors = []) {
$this->val = $val;
$this->neighbors = $neighbors;
}
}
function cloneGraph($node, &$visited = []) {
if ($node === null) return null;
if (isset($visited[$node->val])) {
return $visited[$node->val];
}
$clone = new Node($node->val);
$visited[$node->val] = $clone;
foreach ($node->neighbors as $neighbor) {
$clone->neighbors[] = cloneGraph($neighbor, $visited);
}
return $clone;
}
// 注意：这里的代码示例使用了自定义的 Node 类，而题目描述中是基于字典的。
// 实际应用中，你可能需要根据具体场景调整 Node 类的结构和图的表示方式。
```
### Python 示例代码
```python
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node, visited=None):
if node is None:
return None
if visited is None:
visited = {}
if node.val in visited:
return visited[node.val]
clone = Node(node.val, [])
visited[node.val] = clone
for neighbor in node.neighbors:
clone.neighbors.append(cloneGraph(neighbor, visited))
return clone
# 示例图的构建和克隆需要额外的代码来适配 Node 类
```
### JavaScript 示例代码
```javascript
class Node {
constructor(val = 0, neighbors = []) {
this.val = val;
this.neighbors = neighbors;
}
}
function cloneGraph(node, visited = new Map()) {
if (!node) return null;
if (visited.has(node.val)) {
return visited.get(node.val);
}
const clone = new Node(node.val);
visited.set(node.val, clone);
clone.neighbors = node.neighbors.map(neighbor => cloneGraph(neighbor, visited));
return clone;
}
// 注意：这里的 JavaScript 示例也使用了自定义的 Node 类。
```
**码小课网站中有更多相关内容分享给大家学习**，包括更深入的算法解析、面试技巧、实战案例等，帮助大家提升编程技能。