algorithm - 在有向图中找到所有可能路径中的公共路径

Question

我试图找到循环有向图中每条可能的路径总是访问的公共节点。我的想法是计算所有可能的路径，然后搜索公共元素。然而，a）这似乎不是很有效，b）它不考虑循环。

目标：是实现不经意的散列边界作为防篡改方法。为此，我需要确定一组在控制流图中与输入无关的通用基本块。换句话说，我想找到将为任何给定输入执行的程序（基本块集）的确定性块。

Answer 1

要执行您想要执行的操作，您需要为路径提供一组起始顶点和结束顶点。所以你的陈述是：

查找从集合 S 中的任何顶点遍历到集合 E 中的任何顶点时总是通过的所有顶点。

然后你会注意到你正在搜索的顶点是顶点分隔符。存在计算最小顶点分隔符的算法。