克隆图(经典算法150题),程序员经典面试笔试题目, 码小课

当前位置：面试刷题>> 克隆图(经典算法150题)

题目描述

给定一个无向图，图中的节点由一个唯一的整数ID表示，每个节点都有一个列表，其中包含与该节点直接相连的节点ID。图以字典形式给出，字典的键是节点的ID，字典的值是一个列表，包含与该节点相连的所有节点的ID。

图的表示示例如下（使用Python字典表示）：

graph = {
    '1': ['2', '4'],
    '2': ['1', '3'],
    '3': ['2'],
    '4': ['1']
}

图是无向的，意味着如果节点'1'到节点'2'有一条边，那么节点'2'到节点'1'也有一条边。

现在，你的任务是克隆这个图，即创建一个图的深拷贝，使得原图和克隆图在逻辑上是分离的，即修改克隆图中的任何节点或边都不会影响原图。

解题思路

为了克隆这个图，我们需要遵循以下步骤：

初始化：创建一个空字典来存储克隆图的节点。
遍历原图：对每个节点，如果它还没有被克隆，则创建一个克隆节点，并将其添加到克隆图的字典中。
构建克隆图的边：在克隆节点时，同时构建与克隆节点相连的边。由于图的节点可能包含循环引用，我们需要一个方法来跟踪已经访问过的节点，避免无限递归。

示例代码

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

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

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