Как построить максимальный путь в графе с помощью обхода в ширину?

Question

[sashx]

Друзья, здравствуйте! Подскажите, как я могу найти максимальный по длине путь в графе с помощью обхода в ширину?

Comments

[Wataru]

Граф ориентированный? Без циклов?

[sashx]

Wataru, граф неориентированный, с циклами

[Wataru]

sashx, Тогда в нем нет максимального пути. Можно бесконечно кружить по циклу.

[sashx]

Wataru, имеется ввиду построить такой путь от s до t

[Wataru]

sashx, 1) идете от s до цикла.
2) крутитесь там проивзольное количество раз.
3) идете до t.

Получаете сколь угодно длинный путь.

Даже если запретить ходить по уже обойденным вершинам, то все-равно остается только полный перебор.

В очень частном случае, когда вершин мало можно построить искуственный граф, где вершинами будут подмножества вершин исходного графа X какая вершина последняя. Этот граф уже будет ациклический и можно по нему однозначно восстановить путь в исходном графе. Но это работает максимум для ~20 вершин максимум.

Answer 1

[Wataru]

Максимальный путь в графе с циклами найти тяжело. Обходом в ширину - вообще никак. Только полным перебором (что является скорее рекурсивным обходом в глубину, но с откатами).

Если граф дерево или ориентированный ациклический, то работает любой обход.