algorithm - 在路径中查找先前的“阻塞点”

我有一个类似“树”的节点结构，我试图找出一种算法，当给出结束节点时，它会找到以前的“阻塞点”。这是一张更好地演示的图片：

所以我要搜索的节点是所有路径必须经过才能到达末端节点的前一个节点。

我尝试了一种算法，我从结束节点开始并向后退（使用广度优先），并且我发现每个具有 2 个或更多输出的节点都添加到一个新列表中，并且我跳过具有一个输出的节点。例如，如果以 15 作为结束节点，我最终会将 10 和 7 添加到潜在节点列表中，但我不确定如何从那里开始。因为我不应该继续从 7 开始。

是否有潜在的算法已经可以做到这一点，如果没有，我怎么能做到这一点？

标签： algorithmpathgraph-theorygraph-algorithmpseudocode

拓扑排序是图的排序，使得每个箭头都与顺序一致。例如，在您的示例中，我们可能会提出以下命令：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 15

使用任何O(n)算法对其进行拓扑排序。

接下来，我们遍历图并跟踪每个节点有多少传入边。

最后，我们按照排序顺序遍历图，并跟踪我们看到了一端但没有看到另一端的边，以及有多少节点没有传入边。任何时候我们到达一个所有出边都没有结束并且每个未来节点都有入边的节点，这就是一个阻塞点。

之后，我们可以准备两张地图。首先是从每个节点到它的拓扑顺序。第二个是阻塞点所在位置的平衡二叉树。

前面的分析是O(n)。实际查找现在是O(log(n)).