当前位置： 面试刷题>> 克隆图(经典算法150题)
### 题目描述
给定一个无向图，图中的节点由一个唯一的整数ID表示，每个节点都有一个列表，其中包含与该节点直接相连的节点ID。图以字典形式给出，字典的键是节点的ID，字典的值是一个列表，包含与该节点相连的所有节点的ID。
图的表示示例如下（使用Python字典表示）：
```python
graph = {
'1': ['2', '4'],
'2': ['1', '3'],
'3': ['2'],
'4': ['1']
}
```
图是无向的，意味着如果节点'1'到节点'2'有一条边，那么节点'2'到节点'1'也有一条边。
现在，你的任务是克隆这个图，即创建一个图的深拷贝，使得原图和克隆图在逻辑上是分离的，即修改克隆图中的任何节点或边都不会影响原图。
### 解题思路
为了克隆这个图，我们需要遵循以下步骤：
1. **初始化**：创建一个空字典来存储克隆图的节点。
2. **遍历原图**：对每个节点，如果它还没有被克隆，则创建一个克隆节点，并将其添加到克隆图的字典中。
3. **构建克隆图的边**：在克隆节点时，同时构建与克隆节点相连的边。由于图的节点可能包含循环引用，我们需要一个方法来跟踪已经访问过的节点，避免无限递归。
### 示例代码
#### PHP 示例
```php
class GraphNode {
public $val;
public $neighbors;
function __construct($val = 0, $neighbors = []) {
$this->val = $val;
$this->neighbors = $neighbors;
}
}
function cloneGraph($node) {
if ($node == null) return null;
$visited = [];
function cloneNode($node) use (&$visited) {
if ($node == null) return null;
if (isset($visited[$node->val])) {
return $visited[$node->val];
}
$clone = new GraphNode($node->val);
$visited[$node->val] = $clone;
foreach ($node->neighbors as $neighbor) {
$clone->neighbors[] = cloneNode($neighbor);
}
return $clone;
}
return cloneNode($node);
}
```
#### Python 示例
```python
class GraphNode:
def __init__(self, val = 0, neighbors = []):
self.val = val
self.neighbors = neighbors
def cloneGraph(node):
if not node:
return None
visited = {}
def clone_node(node):
if node in visited:
return visited[node]
clone = GraphNode(node.val, [])
visited[node] = clone
for neighbor in node.neighbors:
clone.neighbors.append(clone_node(neighbor))
return clone
return clone_node(node)
```
#### JavaScript 示例
```javascript
class GraphNode {
constructor(val = 0, neighbors = []) {
this.val = val;
this.neighbors = neighbors;
}
}
function cloneGraph(node) {
if (!node) return null;
const visited = new Map();
function cloneNode(node) {
if (visited.has(node)) {
return visited.get(node);
}
const clone = new GraphNode(node.val);
visited.set(node, clone);
node.neighbors.forEach(neighbor => {
clone.neighbors.push(cloneNode(neighbor));
});
return clone;
}
return cloneNode(node);
}
```
在以上代码中，我们使用了递归和哈希表（在PHP中是关联数组，Python中是字典，JavaScript中是Map）来跟踪已经访问过的节点，从而避免重复克隆和循环引用问题。