Алгоритм, чтобы найти путь, который посещает каждую вершину в ориентированном графе, по крайней мере, один раз

Question

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

Answer 1

Если вам нужен какой-либо путь (не обязательно простой), то вы можете найти некоторый путь от 1 до 2, затем некоторый путь от 2 до 3, и так далее (1, 2, 3, ... - это количество вершин в вашем SCC). И если вам нужен простой путь, то Глилейн правильно заметил в комментариях, что это NP-полная задача о гамильтоновом пути.