Python-сообщество

Уважаемые товарищи, всем привет!

Имеется задача:

1. Есть граф, направленный, взвешенный, с циклами (но без зацикливания вершин на самих себя).
2. Нужно итеративно построить дерево всех возможных самых глубоких путей из некоторой данной вершины графа.

Что есть и что я знаю:

1. Есть граф, сохранённый в виде списка вершин и списка рёбер с весами.

2. Я в курсе, что есть стек, дерево, рекурсия и т. п.

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

В чём проблема: не могу ухватить суть, а именно: как организовать условие, по которому мы запускаем цикл, как хранить пройденные вершины для каждого пути и как организовать возврат, когда мы дошли до листочков (leaves) дерева графа, детей больше ни у кого нет и нам нужно обратно.

ПРИМЕЧАНИЕ: 1) я в курсе, что, наверное, есть и другие, более эффективные способы - нужно сделать именно ТАК. 2) я не прошу готовый скрипт - мне нужен алгоритмический пинок

Заранее всем спасибо!

Отредактировано alekscooper (Апрель 13, 2015 06:54:01)

Прикреплённый файлы:
L19_graph.png (106,1 KБ)

Тут надо просто почаще рекурсией обмазываться. Потом проще будет.
Все пути примерно так ищутся (могу ошибиться)

def paths(node, acc=[]):
    if node in acc:
        return [acc]
    if children(node):
        return [sum(paths(child, acc + [node]), []) for child in children(node)]
    return [acc + [node]]

Про рекурсию знаю, страха перед ней нет, просто лёгких путей мы не ищем

alekscooper
1. Есть граф, сохранённый в виде списка вершин и списка рёбер с весами.

alekscooper
мне нужен алгоритмический пинок

alekscooper
Про рекурсию знаю, страха перед ней нет, просто лёгких путей мы не ищем

kamisama
Так тебе без рекурсии надо чтоли? Непонятно что имелось в виду под словом “итеративно”

Вопрос отпал, стоило лишь включить мозг на 100% ТЕМА RESOLVED

alekscooper
стоило лишь включить мозг на 100%

terabayt
мотрели фильм “Люси”? ))

alekscooper
Впервые слышу