克隆图 LeetCode 133

Question

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
    public int val;
    public List<Node> neighbors;
}
Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

我已经为此苦苦挣扎了很长时间。我的解决方案：

 /**
 * // 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) {
  if (!node) {
    return node;
  }
  const nodeCopy = new Node(node.val);
  let stack = [node];
  let nodeMap = {};
  nodeMap[node.val] = nodeCopy;
  while (stack.length > 0) {
    const currentNode = stack.shift();
    const currentNodeCopy = nodeMap[currentNode.val];
    let nodeNeighbors = currentNode.neighbors;
    while (nodeNeighbors.length > 0) {
      const currentNeighbor = nodeNeighbors.shift();
      let existingNeighborCopy = nodeMap[currentNeighbor.val];
      // console.log(existingNeighborCopy);
      if (!existingNeighborCopy) {
        stack.push(currentNeighbor);
        nodeMap[currentNeighbor.val] = new Node(currentNeighbor.val);
      }
      // console.log('Existing Neighbor');
      // Already Visited;
      currentNodeCopy.neighbors.push(nodeMap[currentNeighbor.val]);
    }
  }
  console.log(nodeCopy);
  console.log(nodeCopy.neighbors[0]);
  return nodeMap[node.val];
};

它迭代地进行 DFS。但是对于给定的基本测试用例：

[[2,4],[1,3],[2,4],[1,3]]

它抛出输出：

Node with value 2 doesn't exist in the original graph.

这似乎完全错误，因为有一个节点的值为 2。上面的代码可能是什么问题？

Answer 1

发生这种情况是因为您改变输入图：

nodeNeighbors.shift();

显然，LeetCode 测试代码不维护自己的输入图副本，因此当它运行您的代码并尝试将输入图与返回图进行比较时，它发现在输入图中节点 1 有没有邻居，因此它说没有节点 2.

所以不要改变输入图，更改以下两行：

    while (nodeNeighbors.length > 0) {
      const currentNeighbor = nodeNeighbors.shift();

...至：

    for (const currentNeighbor of nodeNeighbors) {

另一个实现

您可以考虑使用递归而不是使用显式堆栈。

var cloneGraph = function(node) {
    if (!node) return null;
    const nodeMap = [0];

    const dfs = ({ val, neighbors }) =>
        Object.assign(nodeMap[val] = new Node(val), {
            neighbors: neighbors.map(neighbor =>
                nodeMap[neighbor.val] ?? dfs(neighbor)
            )
        });

    return dfs(node);
};

Answer 2

在 java 中添加一个具有更好 T、S 复杂度的解决方案。


class Solution {
    // O(N)time
    // O(N)space
    HashMap<Integer, Node> graphDataMap = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null)
            return node;
        depthFirstSearch(node);
        return graphDataMap.get(node.val);
    }

    void depthFirstSearch(Node node) {
        if (graphDataMap.containsKey(node.val)) {
            return;
        }
        Node cloneNode = new Node(node.val);
        graphDataMap.put(node.val, cloneNode);
        for (Node n : node.neighbors) {
            depthFirstSearch(n);
            cloneNode.neighbors.add(graphDataMap.get(n.val));
        }
    }
}
```

克隆图 LeetCode 133

Clone Graph LeetCode 133

javascript

algorithm

graph-algorithm

Test case format:

另一个实现