133. 克隆图

题目描述

输入一张无向连通图中某个节点的引用。每个节点含整数值 val 和邻居节点列表 neighbors。返回整张图的深拷贝：新图的每个节点都要新建，结构与原图一致。

测试数据用邻接表描述图。节点值从 1 开始编号，邻接表第 i 个列表（从 0 数）列出值为 i + 1 的节点的邻居。

传入的节点总是值为 1 的节点。你需要返回它对应的新节点。输出同样以邻接表展示；图为空时输出 []。

示例 1

输入：edges = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]

解释：4 个节点连成一个环 1-2-3-4-1，拷贝后邻接表相同。

示例 2

输入：edges = [[]]
输出：[[]]

解释：只有一个值为 1 的节点，没有邻居。

示例 3

输入：edges = []
输出：[]

解释：图中没有节点。

数据范围

节点数在 [0, 100] 之间。
1 <= Node.val <= 100
各节点的值互不相同。
没有重边，也没有连向自己的边。
图是连通的，从给定节点能到达所有节点。

解题思路：哈希表+BFS

用哈希表 clones 记录“原节点 → 新节点”。BFS 遍历原图：弹出 cur，枚举它的每个邻居 nb；如果 nb 还没克隆，就新建并入队；然后把 clones[nb] 接到 clones[cur] 的邻居列表里。哈希表同时起到“已访问”的作用。

为什么正确

一个原节点恰好对应一个克隆节点；一个节点出队处理完后，它的克隆的邻居列表就与原节点一一对应。

复杂度分析

时间 O(V + E)，空间 O(V)。

易错点

必须先把新节点放进哈希表，再处理它的邻居；否则遇到环时会把同一个节点克隆多次。另外，新节点的邻居必须指向克隆节点，不能指回原图。空图要返回 null。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None
        clones = {node: Node(node.val)}
        queue = collections.deque([node])
        while queue:
            cur = queue.popleft()
            for nb in cur.neighbors:
                if nb not in clones:
                    clones[nb] = Node(nb.val)
                    queue.append(nb)
                clones[cur].neighbors.append(clones[nb])
        return clones[node]

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> clones = new HashMap<>();
        clones.put(node, new Node(node.val));
        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node nb : cur.neighbors) {
                if (!clones.containsKey(nb)) {
                    clones.put(nb, new Node(nb.val));
                    queue.offer(nb);
                }
                clones.get(cur).neighbors.add(clones.get(nb));
            }
        }
        return clones.get(node);
    }
}

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return nullptr;
        }
        unordered_map<Node*, Node*> clones;
        clones[node] = new Node(node->val);
        queue<Node*> q;
        q.push(node);
        while (!q.empty()) {
            Node* cur = q.front();
            q.pop();
            for (Node* nb : cur->neighbors) {
                if (!clones.count(nb)) {
                    clones[nb] = new Node(nb->val);
                    q.push(nb);
                }
                clones[cur]->neighbors.push_back(clones[nb]);
            }
        }
        return clones[node];
    }
};

func cloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}
	clones := map[*Node]*Node{node: {Val: node.Val}}
	queue := []*Node{node}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for _, nb := range cur.Neighbors {
			if _, ok := clones[nb]; !ok {
				clones[nb] = &Node{Val: nb.Val}
				queue = append(queue, nb)
			}
			clones[cur].Neighbors = append(clones[cur].Neighbors, clones[nb])
		}
	}
	return clones[node]
}

var cloneGraph = function(node) {
    if (!node) {
        return null;
    }
    const clones = new Map([[node, new _Node(node.val)]]);
    const queue = [node];
    let head = 0;
    while (head < queue.length) {
        const cur = queue[head++];
        for (const nb of cur.neighbors) {
            if (!clones.has(nb)) {
                clones.set(nb, new _Node(nb.val));
                queue.push(nb);
            }
            clones.get(cur).neighbors.push(clones.get(nb));
        }
    }
    return clones.get(node);
};

function cloneGraph(node: _Node | null): _Node | null {
    if (!node) {
        return null;
    }
    const clones = new Map<_Node, _Node>([[node, new _Node(node.val)]]);
    const queue: _Node[] = [node];
    let head = 0;
    while (head < queue.length) {
        const cur = queue[head++];
        for (const nb of cur.neighbors) {
            if (!clones.has(nb)) {
                clones.set(nb, new _Node(nb.val));
                queue.push(nb);
            }
            clones.get(cur)!.neighbors.push(clones.get(nb)!);
        }
    }
    return clones.get(node)!;
}

载入编辑器，自己跑一遍 →

其他解法

两种解法都用哈希表防止重复克隆，复杂度相同；DFS 更简洁，BFS 不受递归深度限制。

解法 2：哈希表+DFS 时间 O(V+E)，空间 O(V)

用哈希表记录原节点到克隆节点的映射。递归访问节点时，若已克隆就直接返回克隆节点。否则先创建克隆节点并登记，再递归克隆每个邻居并加入邻居列表。

代码更短，节点和邻居的关系一目了然。递归深度可达节点数，图很大时可能栈溢出。

import sys
from typing import Optional

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        sys.setrecursionlimit(10000)
        clones = {}

        def dfs(cur):
            if cur in clones:
                return clones[cur]
            copy = Node(cur.val)
            clones[cur] = copy
            for nb in cur.neighbors:
                copy.neighbors.append(dfs(nb))
            return copy

        return dfs(node) if node else None

class Solution {
    private Map<Node, Node> clones = new HashMap<>();

    public Node cloneGraph(Node node) {
        clones.clear();
        return node == null ? null : dfs(node);
    }

    private Node dfs(Node cur) {
        if (clones.containsKey(cur)) return clones.get(cur);
        Node copy = new Node(cur.val);
        clones.put(cur, copy);
        for (Node nb : cur.neighbors) {
            copy.neighbors.add(dfs(nb));
        }
        return copy;
    }
}

class Solution {
    unordered_map<Node*, Node*> clones;

    Node* dfs(Node* cur) {
        auto it = clones.find(cur);
        if (it != clones.end()) return it->second;
        Node* copy = new Node(cur->val);
        clones[cur] = copy;
        for (Node* nb : cur->neighbors) {
            copy->neighbors.push_back(dfs(nb));
        }
        return copy;
    }

public:
    Node* cloneGraph(Node* node) {
        clones.clear();
        return node ? dfs(node) : nullptr;
    }
};

func cloneGraph(node *Node) *Node {
	clones := map[*Node]*Node{}
	var dfs func(cur *Node) *Node
	dfs = func(cur *Node) *Node {
		if c, ok := clones[cur]; ok {
			return c
		}
		cp := &Node{Val: cur.Val}
		clones[cur] = cp
		for _, nb := range cur.Neighbors {
			cp.Neighbors = append(cp.Neighbors, dfs(nb))
		}
		return cp
	}
	if node == nil {
		return nil
	}
	return dfs(node)
}

var cloneGraph = function(node) {
    const clones = new Map();
    const dfs = (cur) => {
        if (clones.has(cur)) return clones.get(cur);
        const copy = new _Node(cur.val);
        clones.set(cur, copy);
        for (const nb of cur.neighbors) {
            copy.neighbors.push(dfs(nb));
        }
        return copy;
    };
    return node ? dfs(node) : null;
};

function cloneGraph(node: _Node | null): _Node | null {
    const clones = new Map<_Node, _Node>();
    const dfs = (cur: _Node): _Node => {
        if (clones.has(cur)) return clones.get(cur)!;
        const copy = new _Node(cur.val);
        clones.set(cur, copy);
        for (const nb of cur.neighbors) {
            copy.neighbors.push(dfs(nb));
        }
        return copy;
    };
    return node ? dfs(node) : null;
}

图论专题的其他题目

查看图论全部题目 →