在路径中查找前一个 "chokepoint"

Question

我有一个类似于 "tree" 的节点结构，我正在尝试找出一种算法，当给出结束节点时，该算法将找到前一个 "chokepoint"。这里有一张图片可以更好地展示：

所以我要搜索的节点是所有路径到达结束节点必须经过的前一个节点。

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

继续遍历

是否有潜在的算法已经可以做到这一点，如果没有，我该如何实现？

Answer 1

A topological sort 是图形的排序，每个箭头都与该顺序一致。例如，在您的示例中，我们可能会提出以下命令：

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

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

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

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

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

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

Answer 2

我相信你的"choke points"就是俗称的"dominators"。在有向图中，如果到 Y 的所有路径都必须经过 X，则一个节点 X 支配另一个 Y。在您的图中，1 和 7 支配所有更大的节点。

有向图的支配者形成一棵树。维基百科文章给出了一个简单的算法，可以在二次时间内找到它们。

您可以在线性时间内完成，但这很棘手。经典算法来自 Lengauer 和 Tarjan。您可以在这里找到它：https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf

Find previous "chokepoint" in path