题目描述

给定一个图，图由节点（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 示例代码

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 示例代码

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 示例代码

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 类。

码小课网站中有更多相关内容分享给大家学习，包括更深入的算法解析、面试技巧、实战案例等，帮助大家提升编程技能。