Мне нужно найти все пути из заданного графа. Я могу сделать это сейчас, однако мой рекурсивный код неэффективен, а мои графики очень сложны. Поэтому мне нужен лучший алгоритм. Вот мой код до сих пор,
def findLeaves(gdict):
# takes graph and find its leaf nodes
leaves = []
for endNode in gdict.iterkeys():
if not gdict[endNode]:
leaves.append(endNode)
return leaves
graphPaths = {}
def findPaths(gname, gdict, leave, path):
# finds all noncycle paths
if not gdict:
return []
temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path]
if temp:
for node in temp:
findPaths(gname, gdict, node, [node] + path)
else:
graphPaths[gname].append(path)
# main
leaves = findLeaves(graph['graph'])
graphPaths['name'] = []
seenNodes = []
for leave in leaves:
findPaths(graph['name'], graph['graph'], leave, [leave])
Существует только один начальный узел, что упрощает работу с рекурсивной функцией. Каждый лист должен попасть туда, если лист следует в обратном порядке. Начальный узел — это тот, который не имеет входящего ребра.
У меня много графиков, поэтому я держу их в словаре. Ключи — это имена графиков. Вот пример моих данных:
graph['graph']: {
0: {1: {}},
1: {2: {}, 3: {}},
2: {3: {}},
3: {4: {}},
4: {5: {}},
5: {6: {}},
6: {7: {}},
7: {6: {}, 5: {}}
}
graph['name'] = nameofthegraph
Эта структура взята из pygraphviz, она просто показывает исходящие ребра от любых узлов. Ключи — это узлы, а значения — исходящие ребра к узлам. Однако, когда у меня есть очень сложные графики, как показано ниже, этот код не может найти все пути.
Есть ли лучший алгоритм, который вы можете предложить? Или есть способ оптимизировать мой алгоритм для сложных графиков?
