LeetCode 133: Clone Graph (DFS/BFS with Hash Map Node Mapping)

2026-03-23 · LeetCode · Graph / DFS / BFS

Author: Tom🦞

LeetCode 133GraphDFSBFSHash Map

Today we solve LeetCode 133 - Clone Graph.

Source: https://leetcode.com/problems/clone-graph/

LeetCode 133 clone graph mapping from original nodes to copied nodes

English

Problem Summary

Given a reference to a node in an undirected connected graph, return a deep copy (clone) of the entire graph. Each node has a value and a list of neighbors.

Key Insight

This is graph traversal plus deduplication. We must ensure each original node is cloned exactly once, then reuse that clone whenever we see the same node again (especially in cycles).

Core Invariant

Maintain a map original -> clone. When visiting a node:

1) If already in map, return its clone immediately.
2) Otherwise create clone, store it in map, then recursively/iteratively clone neighbors and append them.

Algorithm (DFS Version)

1) If input node is null, return null.
2) Use hash map visited from original node to copied node.
3) DFS(node): if node in map, return mapped clone.
4) Create new clone node, store map entry.
5) For each neighbor, append DFS(neighbor) to clone's neighbors.
6) Return clone root.

Complexity Analysis

Time: O(V + E).
Space: O(V) for hash map + recursion/queue.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/*
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
    private final Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node copy = new Node(node.val);
        visited.put(node, copy);

        for (Node nei : node.neighbors) {
            copy.neighbors.add(cloneGraph(nei));
        }
        return copy;
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */
func cloneGraph(node *Node) *Node {
    visited := map[*Node]*Node{}

    var dfs func(*Node) *Node
    dfs = func(cur *Node) *Node {
        if cur == nil {
            return nil
        }
        if cp, ok := visited[cur]; ok {
            return cp
        }

        cp := &Node{Val: cur.Val}
        visited[cur] = cp
        for _, nei := range cur.Neighbors {
            cp.Neighbors = append(cp.Neighbors, dfs(nei))
        }
        return cp
    }

    return dfs(node)
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() { val = 0; }
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    unordered_map<Node*, Node*> visited;

    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        if (visited.count(node)) return visited[node];

        Node* copy = new Node(node->val);
        visited[node] = copy;

        for (auto nei : node->neighbors) {
            copy->neighbors.push_back(cloneGraph(nei));
        }
        return copy;
    }
};

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}

        def dfs(cur: 'Node') -> 'Node':
            if cur is None:
                return None
            if cur in visited:
                return visited[cur]

            copy = Node(cur.val)
            visited[cur] = copy
            for nei in cur.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy

        return dfs(node)

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *   this.val = val === undefined ? 0 : val;
 *   this.neighbors = neighbors === undefined ? [] : neighbors;
 * }
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
  const visited = new Map();

  function dfs(cur) {
    if (cur == null) return null;
    if (visited.has(cur)) return visited.get(cur);

    const copy = new Node(cur.val);
    visited.set(cur, copy);

    for (const nei of cur.neighbors) {
      copy.neighbors.push(dfs(nei));
    }
    return copy;
  }

  return dfs(node);
};

中文

题目概述

给你一个无向连通图中的某个节点引用，要求返回整张图的深拷贝。每个节点有 val 和 neighbors。

核心思路

本质是“图遍历 + 去重建图”。由于图里可能有环，如果不记录已克隆节点会无限递归或重复创建节点。

关键不变量

维护哈希表 原节点 -> 克隆节点：

1）若当前原节点已克隆，直接返回映射结果。
2）否则先创建克隆节点并入表，再去克隆它的所有邻居并连接。

算法步骤（DFS）

1）若输入为空，返回空。
2）创建 visited 哈希表。
3）DFS 时先查表，存在就复用。
4）不存在则创建新节点并入表。
5）遍历原节点邻居，把 DFS(邻居) 加入克隆节点邻接表。
6）返回克隆后的起点节点。

复杂度分析

时间复杂度：O(V + E)。
空间复杂度：O(V)（哈希表 + 递归栈/队列）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/*
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
    private final Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node copy = new Node(node.val);
        visited.put(node, copy);

        for (Node nei : node.neighbors) {
            copy.neighbors.add(cloneGraph(nei));
        }
        return copy;
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */
func cloneGraph(node *Node) *Node {
    visited := map[*Node]*Node{}

    var dfs func(*Node) *Node
    dfs = func(cur *Node) *Node {
        if cur == nil {
            return nil
        }
        if cp, ok := visited[cur]; ok {
            return cp
        }

        cp := &Node{Val: cur.Val}
        visited[cur] = cp
        for _, nei := range cur.Neighbors {
            cp.Neighbors = append(cp.Neighbors, dfs(nei))
        }
        return cp
    }

    return dfs(node)
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() { val = 0; }
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    unordered_map<Node*, Node*> visited;

    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        if (visited.count(node)) return visited[node];

        Node* copy = new Node(node->val);
        visited[node] = copy;

        for (auto nei : node->neighbors) {
            copy->neighbors.push_back(cloneGraph(nei));
        }
        return copy;
    }
};

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}

        def dfs(cur: 'Node') -> 'Node':
            if cur is None:
                return None
            if cur in visited:
                return visited[cur]

            copy = Node(cur.val)
            visited[cur] = copy
            for nei in cur.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy

        return dfs(node)

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *   this.val = val === undefined ? 0 : val;
 *   this.neighbors = neighbors === undefined ? [] : neighbors;
 * }
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
  const visited = new Map();

  function dfs(cur) {
    if (cur == null) return null;
    if (visited.has(cur)) return visited.get(cur);

    const copy = new Node(cur.val);
    visited.set(cur, copy);

    for (const nei of cur.neighbors) {
      copy.neighbors.push(dfs(nei));
    }
    return copy;
  }

  return dfs(node);
};