Алгоритм первого поиска глубины

Question

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

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

любое предложение...

РЕДАКТИРОВАТЬ: График ациклическая.

Answer 1

Если вы хотите перечислить все пути в ациклическом графике, то я не думаю, что вы можете легко изменить поиск глубины, чтобы сделать это. Есть алгоритмы, специально разработанные для этой цели, в частности: Рубин, Ф.; , «Перечислив все простые пути в графе,« Схемы и системы, IEEE транзакции, VOL.25, No.8, с. 641-642, августа 1978 года.

Если вы знаете алгоритм Floyd-Warshall, вы можете легко изменить его, чтобы вычислить список путей в каждом элементе матрицы, а не мин расстояние, которое сделает работу. Вышеуказанная статья использует некоторые битные операции, чтобы сделать это немного быстрее.

Answer 2

Хотите, чтобы вершины можно посетить всякий раз, когда есть ветвь в любой вершине.

Что вы предлагаете, чтобы итератор делал, когда он достигает ветки в вершине?

Глубина первый поиск - только один ответ на этот вопрос. Здесь некоторые другие.

Но вы должны что-то выбрать. Это не вопрос выключения DFS.

Answer 3

Я думаю, что это невозможно по дизайну. Потому что, если ваш график содержит циклы (и у вас там, когда вы говорите, что вершина может быть посещена более чем один раз), алгоритм в конечном итоге в бесконечке.