Алгоритм первого поиска глубины
-
08-10-2019 - |
Вопрос
Глубинный алгоритм, реализованный в библиотеке Boost, посещает каждую вершину только один раз.
Есть ли какие-либо работы, чтобы деактивировать этот вариант. Я хочу, чтобы вершины можно посетить всякий раз, когда есть ветвь в любой вершине.
любое предложение...
РЕДАКТИРОВАТЬ: График ациклическая.
Решение
Если вы хотите перечислить все пути в ациклическом графике, то я не думаю, что вы можете легко изменить поиск глубины, чтобы сделать это. Есть алгоритмы, специально разработанные для этой цели, в частности: Рубин, Ф.; , «Перечислив все простые пути в графе,« Схемы и системы, IEEE транзакции, VOL.25, No.8, с. 641-642, августа 1978 года.
Если вы знаете алгоритм Floyd-Warshall, вы можете легко изменить его, чтобы вычислить список путей в каждом элементе матрицы, а не мин расстояние, которое сделает работу. Вышеуказанная статья использует некоторые битные операции, чтобы сделать это немного быстрее.
Другие советы
Хотите, чтобы вершины можно посетить всякий раз, когда есть ветвь в любой вершине.
Что вы предлагаете, чтобы итератор делал, когда он достигает ветки в вершине?
Глубина первый поиск - только один ответ на этот вопрос. Здесь некоторые другие.
Но вы должны что-то выбрать. Это не вопрос выключения DFS.
Я думаю, что это невозможно по дизайну. Потому что, если ваш график содержит циклы (и у вас там, когда вы говорите, что вершина может быть посещена более чем один раз), алгоритм в конечном итоге в бесконечке.