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

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, если < r, .., v, .., w> где w - раковина, то мы должны игнорировать пути < r, .., v, .., x> где x! = w.

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

Answer 1

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

предлагаемый мною алгоритм:.

1. Найти все пути между r и v, используя, например, ответы предоставлены в Find the paths between two given nodes?

2. Найти все пути между v и используя тот же алгоритм. Так как G ациклическая, ни один путь от В до D может привести обратно к пути уже найденному на шаге 1. Таким образом, в результате графа все пути между г и д будут проходить ст.

Answer 2

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

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