Разложить циклический граф на минимальное количество подграфов кратчайшего пути

Question

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

                      +-------------------------+
                       |                         |
                       |                         |
            +----------+----------+              |
            v          |          v              |
+---+     +---+      +---+      +---+     +---+  |
| 1 | --> | 3 | <--> | 4 | <--> | 5 | --> | 6 |  |
+---+     +---+      +---+      +---+     +---+  |
                       ^                         |
                       |                         |
                       |                         |
                     +---+                       |
                     | 2 |                       |
                     +---+                       |
                     +---+                       |
                     | 7 | <---------------------+
                     +---+

Подграф кратчайшего пути относительно 1 будет:

+---+     +---+     +---+     +---+
| 1 | --> | 3 | --> | 4 | --> | 7 |
+---+     +---+     +---+     +---+
            |
            |
            v
          +---+     +---+
          | 5 | --> | 6 |
          +---+     +---+

Подграф кратчайшего пути относительно 2 будет:

          +---+
          | 7 |
          +---+
            ^
            |
            |
+---+     +---+     +---+     +---+
| 2 | --> | 4 | --> | 5 | --> | 6 |
+---+     +---+     +---+     +---+
            |
            |
            v
          +---+
          | 3 |
          +---+

Кратчайший путь sugraph относительно 5 будет:

+---+     +---+     +---+     +---+
| 6 | <-- | 5 | --> | 4 | --> | 7 |
+---+     +---+     +---+     +---+
            |
            |
            v
          +---+
          | 3 |
          +---+

Обратите внимание, что подграф кратчайшего пути относительно 3 - это подмножество 1, 4 - это подмножество 2. 6 и 7 - листья.

Моим текущим (наивным) решением было бы выполнить BFS для каждого узла, помечая узлы как посещенные для предотвращения циклов. Затем проверить, являются ли подграфы подмножествами друг друга, чтобы создать минимальное количество отдельных подграфов. Есть идеи для лучшего, более формального решения?

РЕДАКТИРОВАТЬ График в моей ситуации невзвешенный, но иметь общее решение для потомков приятно.

(графики сделаны с http://bloodgate.com/graph-demo)

Answer 1

Каждое из перечисленных выше деревьев называется деревом кратчайшего пути Чтобы найти одно дерево кратчайшего пути с корнем в некоторой вершине, вы можете использовать алгоритм Дейкстры, который находит кратчайшие пути от исходного узла к каждому другому узлу и показывает, какие ребра используются для достижения этих узлов. Это сразу дает вам дерево кратчайшего пути для одного узла, предполагая, что граф не содержит отрицательных ребер. Если вы хотите перечислить все деревья, вы можете сделать это, запустив алгоритм Дейкстры, начиная с каждого узла. Учитывая кучу Фибоначчи, это работает в O (VE + V ² log V), что очень быстро.

Если у вас нет кучи Фибоначчи, или вы используете плотные графы, или у вас могут быть отрицательные циклы, вы можете использовать алгоритм Флойда-Варшалла. Этот алгоритм выполняется за время O (V ³ ) и вычисляет для каждого узла кратчайший путь к каждому другому узлу, даже если имеются отрицательные ребра. Отсюда вы можете легко восстановить все деревья кратчайших путей.

Надеюсь, это поможет!

РЕДАКТИРОВАТЬ : Если ваш график невзвешенный, то, очевидно, существует действительно хороший алгоритм для решения этой проблемы, который выполняется за время O (M (n) log n), где M (n) - время требуется умножить матрицы небольших чисел вместе. Поскольку это можно сделать довольно быстро (около O (n ^2.3 ), это будет лучший алгоритм для решения проблемы. Здесь есть статья об алгоритме здесь , но за платным доступом. Практически, если вы не имеете дело с действительно большими графиками (скажем, с десятками тысяч узлов), я не думаю, что вам нужно беспокоиться об использовании этого более мощного алгоритма, но он все еще хорош знать о.

Answer 2

templatetypedef, использование OP "BFS" ​​предполагает, что график является невзвешенным.

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

Ради уникальности я собираюсь предположить, что «кратчайший путь» означает наименьший в порядке длина-лекс. На высоком уровне мы вычисляем порядок, в котором нужно обрабатывать вершины, так что если дерево BFS вершины u объединяет вершины v, то u упорядочивается до v. Каждая вершина обрабатывается за линейное время, что включает определение вершин, которые она включает.

Порядок вычисляется путем нахождения сильных компонентов, топологической сортировки сильных компонентов и последующего произвольного упорядочения вершин внутри каждого отдельного компонента. Ясно, что u включает v только в том случае, если множество вершин, достижимых из u, является правильным надмножеством вершин, достижимых из v.

Чтобы обработать вершину u, вычислите дерево BFS из u, а затем определите набор вершин, у поддеревьев которых нет дуги, выходящей из поддерева - это те, которые попадают в категорию. Определите последний, пройдя сначала по глубине дерева, записав для каждой вершины v интервал I (v), левая конечная точка которого является временем входа, а правая конечная точка - временем выхода. Для каждой вершины v вычислим наименьший интервал J (v), содержащий I (v) и все I (w) с дугой v-> w. Используя DFS, вычислим для каждой вершины v наименьший интервал K (v), содержащий K (w), для всех потомков w из v. Вершина v, отличная от u, определяется как тогда и только тогда, когда K (v) = I (v) .

Почему это должно работать? Мы знаем, что поддерево v дерева с корнем в u является подмножеством дерева с корнем в v. Предположим, что u включает v (другими словами, эти два дерева равны). Затем ясно, что голова каждой дуги из поддерева v переходит в поддерево v, иначе голову нужно было исследовать. И наоборот, предположим, что u не включает v. Дерево с корнем в v содержит вершину, не входящую в поддерево v, и, таким образом, дуга покидает поддерево v.

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