控制流图遍历 - BFS，但要确保前辈被访问

Question

我有一种情况，在访问节点之前必须先访问节点的前驱。所以，这里是代码：

nodeQ.Enqueue(rootNode);

while(!nodeQ.Empty())
{
    node = nodeQ.Dequeue();
    ForEach(var predecessor in node.Predecessors)
    {
        if(predecessor is not visited)
        {
            //put the node back into the queue
            nodeQ.Enqueue(node);
            skip = true;
            break;
        }
    }
    if(skip)continue;

    Visit(node)

    foreach(var successor in node.Successors)
    {
        if(successor is not already visited)
        {
            nodeQ.Enqueue(successor);
        }
    }   
}

以上算法适用于没有循环的线性控制流图（阅读：循环）正常的 BFS 遍历不能确保在节点本身之前访问节点的前驱。

示例配置文件：

正常的 BFS 遍历将是： 0, 1 , 2 , 3 , 12, 4, 5, 9, 10, 11, 8 , 6, 7

但是，我希望顺序为 0、1、2、3、4、5、6、7、8、9、10、11、12，可以通过其中的小修改来实现我的代码显示在开头。

但是，这种修改会导致在涉及到循环时无限跳块。

可能会失败的示例 CFG：

在这种情况下，我的代码将无限期推迟对节点 1、2、3 的访问

所以，我一直在寻找一种遍历方式，确保以这样的方式遍历 CFG 的节点（有或没有循环），即在节点本身之前访问节点的前身。

我正在考虑识别后缘，即检查节点 N 是否是其前任 P 的支配者，那么 P->N 是后缘，无需将 P 视为节点 N 的前任. 然而，这似乎不起作用，因为节点 N 并不总是必须支配节点 P。

Answer 1

我解决这个问题的方法是先找到支配者，创建支配树，然后在 DFS 预序中遍历树。

Answer 2

对于寻求 CFG 和支配计算指导的其他人来说，查看 IBM WALA tools 可能会有用。我在这里为我的特定任务找到了很多有用的信息。

控制流图遍历 - BFS，但要确保前辈被访问

Control Flow Graph Traversal - BFS, but make sure predecessors are Visited

algorithm

tree

graph

tree-traversal

graph-traversal