Алгоритм подграфа

Question

Я хотел бы знать, существует ли эффективный алгоритм S = F (v, G) для построения подграфа S из DAG G = (V, E) так, чтобы все пути в S содержали вершину v из V. Если это так, можно эффективно расширить F до F '(N, G) для набора вершин N. Я открыт для любых структур данных для первоначального хранения DAG G.

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

Другое условие, которое я пропустил, дано расширенное F '(N, G), так что для всех v, w из N, если , где w - сток, то мы следует игнорировать пути , где x! = w.

У меня есть одно решение, но оно не масштабируется, когда #V> 2000 и #N> 2.

Answer 1

Результирующий граф содержит узлы, которые достижимы из v, и узлы v достижимы из (или узлов, которые достижимы из v в транспонированном подграфе). Получение набора достижимых узлов может быть выполнено эффективно.

Это может быть легко расширено для набора узлов: вам нужно просто добавить их все в начале поиска в ширину.

Answer 2

Я предполагаю, что вы ищете самый большой подграф S из G = ({r} + V + {d}, E), где r - уникальный узел источника, а d - приемник, такой что каждый путь от r до d проходит определенный узел v.

Мой предложенный алгоритм:

1. Найдите все пути между r и v, используя, например, ответы, представленные в Найти пути между двумя заданными узлами?

2. Найти все пути между v и использовать тот же алгоритм. Поскольку G ацикличен, ни один путь от v до d не может привести к пути, уже найденному на шаге 1. Таким образом, в результирующем графе все пути между r и d пройдут v.