Имеется задача:
1. Есть граф, направленный, взвешенный, с циклами (но без зацикливания вершин на самих себя).
2. Нужно итеративно построить дерево всех возможных самых глубоких путей из некоторой данной вершины графа.
Что есть и что я знаю:
1. Есть граф, сохранённый в виде списка вершин и списка рёбер с весами.
2. Я в курсе, что есть стек, дерево, рекурсия и т. п.
3. Я понимаю, что мы выходим из начальный вершины, берём её детей, затем её детей и т. п. и на каждом этапе смотрим, чтобы каждая вершина была по одному разу, иначе попадём в петлю.
В чём проблема: не могу ухватить суть, а именно: как организовать условие, по которому мы запускаем цикл, как хранить пройденные вершины для каждого пути и как организовать возврат, когда мы дошли до листочков (leaves) дерева графа, детей больше ни у кого нет и нам нужно обратно.
ПРИМЕЧАНИЕ: 1) я в курсе, что, наверное, есть и другие, более эффективные способы - нужно сделать именно ТАК. 2) я не прошу готовый скрипт - мне нужен алгоритмический пинок
Заранее всем спасибо!