algorithm - 复制图形的一部分

Question

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

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

类型字段指示(仅在叶子中)节点是否必须复制、不得复制或可以复制。

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

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

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 根是准确的。堆栈有效地构建了一些父指针，但您可能更容易接受。