我需要从给定图表中找到所有路径。我现在可以这样做,但是我的递归代码效率不高,而且我的图表也非常复杂。因此我需要一个更好的算法。到目前为止,这是我的代码,
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
,它简单地显示了来自任何节点的传出边。键是节点,值是节点的出边。但是,当我有如下非常复杂的图表时,此代码无法找到所有路径。
有没有更好的算法可以推荐?或者有什么方法可以优化我的复杂图形算法?