复制树的算法很简单，我们可以进行先序遍历。是否存在一种高效的算法来复制图？
我尝试了类似的方法，并得出结论需要在新图中维护一个节点的哈希映射，否则会重复节点，因为一个节点可能有多个父节点。
克隆图的算法
8
- Amit
6
6修改后的 BFS/DFS，当节点被标记为“已访问”时会复制它们？ - Oren
1严重依赖于数据结构。 - Zeta
图遍历 在维基百科上。这是一篇相对较长的文章，可能会给您带来一些启示。 - keyser
@Zeta 假设图被表示为邻接矩阵。 - Amit
@Keyser 在原始图中使用DFS/BFS和标志将帮助我避免再次访问节点。但在新图中，我确实希望当前节点与已添加到图中的节点之间存在链接。由于已添加的节点具有多个父节点。可以将其视为某些社交网络图，其中您将拥有共同的朋友。 - Amit
如果图被表示为邻接矩阵，也许你可以直接复制这个矩阵？ - wildplasser
4个回答
11
只需进行深度优先搜索并在访问每个节点时复制该节点即可。正如您所说，您需要一种将原始图中的节点映射到相应副本的方法，以便可以正确连接循环和交叉边的副本。
此映射也足以记住在DFS中已经访问过的节点。
因此，在Java中，您可以采用以下代码：
class Node {
// Contents of node...
Data data;
// ... member declarations like array of adjacent nodes
final ArrayList<Node> children = new ArrayList<>();
// Recursive graph walker for copying, not called by others.
private Node deepCloneImpl(Map<Node, Node> copies) {
Node copy = copies.get(this);
if (copy == null) {
copy = new Node(data);
// Map the new node _before_ copying children.
copies.put(this, copy);
for (Node child : children)
copy.children.add(child.deepCloneImpl(copies));
}
return copy;
}
public Node deepClone() {
return deepCloneImpl(new HashMap<Node, Node>());
}
}
请注意，您不希望覆盖Node的equals或hashCode方法。包含副本的映射依赖于由Object定义的引用相等性。
另一种方法是在每个节点中放置一个附加字段，该字段指向副本（如果有）并且否则为空。这仅通过另一种方法实现映射。但它需要两次遍历图形：一次制作副本，另一次清除这些映射字段以供将来重用。
- Gene
3
如果您有一种快速唯一地标识每个节点的方法，那么您的哈希映射方法似乎是可行的。
否则，您最好：
使用数据结构存储图形，使您能够直接在每个节点中存储“是否重复”的唯一标志（例如，对于未重复的节点为
0，对于重复的节点为1到numberOfNodes），遍历节点（通过BFS、DFS）时要注意已经复制的节点并从起始图重新构建所有连接。
您的起始图和完成图都应该在每个节点中具有相应的唯一“是否重复”标志，以便您能够正确地从起始图重构连接。当然，您可以将“是否重复”的标志和“唯一标识符”作为单独的变量使用。
- plesiv
0
为了使克隆更加高效，需要使用两个东西：
- 具有更快的删除和添加末尾操作的数据结构。可以从
list、queue或stack中选择。 - 具有快速搜索功能的数据结构。可以快速搜索
Map，即摊销时间复杂度为O(1)。
算法：
To be processed <--> Queue
/
Not_Cloned_Yet -> Clone it -> Map
`~~~~~~~~checks~~~~~~~~~~^
Root is "Not Cloned yet" and needs to be "To be processed" -- (1)
Clone it -> Put in Map & Queue -- (2)
Continue till "To be processed" is not zero. i.e. Queue is not empty. -- (3)
Traverse and update the list of neighbours -- (4)
Neighbours that are "Not cloned yet" needs "Clone it -> Put in Map & Queue" --(5)
- 步骤2和5基于
待处理 --> 队列 - 步骤3基于
队列 -> 待处理 - 队列元素是已经克隆但未被处理的元素（即其邻居列表未更新）。
- 邻居可能已经克隆，也可能还没有。因此需要在映射中进行检查。
- Saurav Sahu
0
在从源图中复制节点时，将每个节点放置在一个<Node，Integer>映射中（因此对节点进行编号，从1到N）。
在将节点粘贴到目标图中时，将每个节点放置在一个<Integer，Node>映射中（再次从1到N进行编号，但出于很快就会清楚的原因，映射方向相反）。
当您在源图中找到反向链接时，可以使用第一个映射将该反向链接的“源副本”节点映射到整数i。接下来，您使用第二个映射查找整数i并找到需要创建相同反向链接的“目标副本”节点。
- The111
1
我刚意识到这基本上是Gene在上面发布的相同答案，只是将Node<->Node映射拆分为两个映射。 哦，算了。 :-) - The111
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接