У меня есть ориентированный граф, и я хочу найти путь, который посещает каждый узел ровно один раз. Я хочу сделать это с хорошей сложностью. Это возможно? И если да, то как?Посетите все узлы ровно один раз в ориентированном графе
Вы ищете Hamiltonian path, который является простым открытым путем, который содержит каждый узел ровно один раз.
Поиск пути гамильтониана в заданном графе NP-complete. Фактически, определение того, является ли данный (направленный или неориентированный) граф гамильтоновым путем, уже является NP-полным (доказано посредством сокращения, например, от vertex cover problem).
Если вы все еще хотите его закодировать, введите an implementation on github. Если вы хотите быстрое решение, возможно, достаточно эвристики (например, inspired by DNA molecules или решение, которое работает быстро на подмножестве графиков. Например, если у вас есть DAG, вы можете сделать топологическую сортировку, а затем проверить, будут ли последовательные вершины Если это так, то топологическая сортировка дает гамильтоновую траекторию.
ответить на ваш вопрос: да, возможно. И теперь, что вы пробовали до сих пор? – codePG
Я запускаю bfs, и я держу битмаску, которая говорит, какие узлы Я посетил. –
Не могли бы вы объяснить, как это сделать? –