复制图形的一部分

Question

我有一个图形数据结构，我需要复制它的一部分。每个节点最多有两个子节点，为了问题的缘故，可以假设这样表示：

struct node {
    int type;
    struct node *child1, *child2;
};

类型字段指示（仅在叶子中）节点是必须复制、不得复制还是可以复制。

我有一个根节点，需要 return 从该节点可到达的子图的副本。某些叶子节点必须被复制，某些叶子节点必须与原始图共享。由于不能损坏原始图，因此如果必须复制非叶节点，则必须复制它的任何子节点。显然，我宁愿只复制那些我必须复制以满足要求的节点，尽管复制所有非叶节点可以满足要求。

仅复制最小集对于树来说是微不足道的，但此图可能包含循环。是否有一种有效的算法可以只复制所需的节点？特别是，不需要计算所有父指针或迭代直到找到不动点的方法？

Answer 1

您可以稍微修改 Tarjan's SCC algorithm 以检测每个强连接组件是否需要一个副本。伪代码执行行

strongconnect(w)
v.lowlink := min(v.lowlink, w.lowlink)

对于深度优先搜索的每个树边vw，您可以向其中添加

v.needscopy := v.needscopy or w.needscopy

当需要将组件从堆栈中弹出时，needscopy 字段对于 SCC 根是准确的。堆栈有效地构造了一些父指针，但也许你会更容易接受。