Алгоритм поиска пути Гамильтона в DAG

Я имею в виду книгу Скенны по алгоритмам.

Проблема проверки того, содержит ли граф G a Hamiltonian path NP-hard, где путь гамильтониана P - это путь, который посещает каждую вершину ровно один раз. Нет необходимости иметь ребро в G от конечной вершины до начальной вершины P, в отличие от проблемы гамильтонова цикла.

Учитывая направленный ациклический граф G (DAG), дайте алгоритм времени O(n + m) для проверки того, содержит ли он гамильтонов путь.

Мой подход,

Я планирую использовать DFS и Topological sorting. Но я не знал, как связать две концепции в решении проблемы. Как можно определить топологическую сортировку для определения решения.

Любые предложения?

Ответ 1

Вы можете сначала топологически отсортировать DAG (каждая DAG может быть топологически отсортирована) в O (n + m).

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

(1,2), (2,3), ..., (n-1,n).

(Это потому, что в гамильтоновском пути вы не можете "вернуться", но все же вам нужно посетить всех, поэтому единственный способ - "не пропустить" )

Вы можете проверить это условие в O (n).

Таким образом, общая сложность O (m + n).

Ответ 2

Я не думаю, что выражение от @agassaa совершенно верно. Рассмотрим простой пример, где есть три узла "A", "B", "C" и ребра A- > B, B- > C, A- > C. В то время как A имеет двух детей, а C имеет двух родителей, A- > B- > C образует гамильтонов путь. Вам не нужно перемещать каждое ребро в графе, чтобы путь был гамильтониан.

DAG, который имеет гамильтоновский цикл