Я пытаюсь спроектировать алгоритм, который запускается за O (n + m) времени, чтобы определить, существует ли гамильтонов путь на заданном направленном ациклическом графе.
Вот алгоритм для этой задачи:
Выполните топологическую сортировку DAG, затем проверьте, связаны ли последовательные вершины в сортировке в графе.Если это так, топологическая сортировка дает гамильтонов путь.С другой стороны, если существует гамильтонов путь, он дает топологический вид DAG.
Теперь я не знаю, как доказать его правильность и выяснить его космическую сложность.Любая помощь будет оценена.