Найти предыдущий "chokepoint" в пути

Question

У меня есть древовидная структура узлов, и я пытаюсь выяснить алгоритм, который найдет предыдущую "точку притяжения", когда задан конечный узел. Вот картинка, чтобы лучше продемонстрировать:

• Поэтому, когда 15 указано в качестве конечного узла, я хочу найти 7
• И если 7 указан как конечный узел, я хочу найти 1
• Но в приведенном выше примере, если в качестве конечного узла указывается все, кроме 7, 15 или 16, найденный узел является предыдущим, поскольку это единственный узел, соединяющийся с конечным узлом.

Таким образом, узел, который я ищу, является предыдущий узел, через который должны пройти все пути go, чтобы добраться до конечного узла.

Я попробовал алгоритм, в котором я начинаю с конечного узла и go в обратном направлении (используя ширину в первую очередь) и каждый узел, который я нахожу у которого есть 2 или более выходов, которые я добавляю в новый список, и узлы с одним выходом, которые я пропускаю. Например, в случае с 15 в качестве конечного узла я добавляю 10 и 7 в список потенциальных узлов, но я не уверен, как оттуда. Так как мне не следует продолжать переход с 7.

Существует ли потенциально какой-либо алгоритм, который уже это делает, и если нет, то как мне этого добиться?

Answer 1

Я полагаю, что ваши "точки удушья" - это то, что обычно называют "доминаторами". В ориентированном графе один узел X доминирует над другим Y, если все пути к Y должны проходить от go до X. На вашем графике 1 и 7 доминируют над всеми большими узлами.

См .: https://en.wikipedia.org/wiki/Dominator_ ( graph_theory)

Доминаторы ориентированного графа образуют дерево. Статья в Википедии дает простой алгоритм для нахождения их всех в квадратичном c времени.

Вы можете сделать это за линейное время, но это сложно. Алгоритм classi c от Ленгауэра и Тарьяна. Вы можете найти его здесь: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf

Answer 2

A топологическая сортировка - это порядок графа такой, что каждая стрелка соответствует порядку. Например, в вашем примере мы могли бы придумать порядок:

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

Выполнить топологическую сортировку, используя для этого любой из O(n) алгоритмов.

Далее мы пройдемся по графику и отследите, сколько входящих ребер имеет каждый узел.

Наконец, мы проходим график в нашем отсортированном порядке и отслеживаем, сколько ребер мы видели один конец, но не другой, и сколько узлов не имеют входящих ребер. Каждый раз, когда мы подходим к узлу, у которого все исходящие ребра не закончились, и у каждого будущего узла есть входящие ребра, это точка пересечения.

После этого мы можем подготовить две карты. Первый - от каждого узла до его топологического порядка. Второе - это сбалансированное бинарное дерево, в котором находятся критические точки.

Предварительный анализ - O(n). Фактические поиски теперь O(log(n)).