有向无环图的并行DFS
根据, 是DFS遍历的并行算法的C ++实现。 该算法下的思想克服了基于DFS的标准标记方法的并行实现问题。 这是因为DFS在边缘访问和某些全局变量的使用方面要求严格的顺序,这在需要并行处理时代表了很大的局限性。
该算法为有向无环图(DAG)的DFS遍历提供了不超过3次BFS访问的有效解决方案,从而可以找到DAG节点之间的前序,后序和父级关系。
BFS的首次访问旨在将DAG转换为DT(图B);
下次访问是在DT上完成的,它的作用是为每个节点找到子树的大小,子树的大小定义为可从其到达的节点数加上自身(图C);
进行第三次访问时,可以获取根据DFS访问顺序先前应访问的节点,查看当前节点的先前同级和父级先前同级的子树大小(图D)。 从先前计算出的值开始,我们获得后顺序和前顺序(在此实现中未计算后顺序,但是只需对代码进行很小的更改即可轻松完成)(图E)。
请注意
1