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

Question

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

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