c++ - 具有邻接表的有向图的复制构造函数

Question

我正在为有向图编写深度构造函数复制函数:

class Graph {
  class Node {
  private:
    std::vector<Node*> childs;
  public:
    Node* clone() {
      Node* n = new Node(*this);
      for(int i = 0; i < node->childs.size(); i++) {
        n->addChild(childs[i]->clone());
      }
      return n;
    }
  };

  Graph(const Graph& h) {
    root = h.root->clone();
  }

private:
  Node* root;
};

如果我有一棵树，复制构造函数可以工作，但在以下情况下它会失败，因为它创建了 B 的两个单独的克隆。我该如何解决这个问题？我需要移动到邻接表表示吗？

A
|\
|/
B

Answer 1

首先，如果你有一个循环，你的代码将永远运行，因为你从不排除任何东西，而且你没有指定我们正在谈论非循环图。

第二件事，做 Node* node = new Node(*this) 已经复制了节点的 std::vector，所以用 重新添加它们addChild 没有意义。

这个问题可以通过多种方式解决，我想到的第一个是使用支持数据结构来避免克隆相同的节点，类似于:

Graph(const Graph&h) {
  std::unordered_map<Node*,Node*> alreadyCloned;
  root = h.root->clone();
}

Node* clone(std::unordered_map<Node*,Node*>& alreadyCloned)
{
  auto it = alreadyCloned.find(this);

  // if we try to clone a node already cloned just return
  // the clone already created
  if (it != alreadyCloned.end())
    return it->second;

  Node* n = new Node();
  alreadyCloned.insert(this, n); // mark node as clone, so if by recursively visiting we find it, we skip it since we're still cloning

  for(int i = 0; i < this->childs.size(); i++)
    n->childs.push_back(childs[i]->clone(alreadyCloned));

  return n;
}

此代码未经测试，可能存在问题，只是为您提供方法背后的想法。