哪种算法可以找到所有外发路径从另一个节点可达的最近节点

Question

你推荐哪种算法来找出从特定节点出来的所有路径可以到达的最近节点。图是有向无权重的。

我正在尝试分析控制流程图，当有'IF‘块时，我想找到“关闭”'IF’的块。

Answer 1

并行运行一组广度优先搜索，从开始节点的每个出站路径开始，每次检查一个节点时，其计数递增1。(注意:这里的“并行”意味着你应该首先对所有搜索进行所有的"distance = 1“评估，然后是所有的"distance = 2"，等等-这可以确保你找到的结果在任何路径上都是最近的)。如果图中存在循环，请确保不会遍历循环。

在第一个节点上停止，该计数递增到与原始节点的外路径数相同的计数。

运行时间为O(N+E)，其中N是节点数，E是当前节点下游的边数。由于提前终止，大多数搜索将花费较少的时间。