查找給定圖python的所有路徑

我需要查找給定圖的所有路徑。我現在可以這樣做，但是我的遞歸代碼效率不高，我的圖形也非常複雜。因此我需要一個更好的算法。這裏是我的代碼到目前爲止，查找給定圖python的所有路徑

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截取，它僅僅示出了從任何節點傳出邊緣。鍵是節點，值是節點的輸出邊。但是，當我有如下複雜圖形時，此代碼無法找到所有路徑。

enter image description here

有沒有更好的算法，你可以建議？或有什麼辦法來優化我的算法複雜的圖形？

來源

2014-07-01 genclik27

發生此問題http://codereview.stackexchange.com/爲@sundarnatarajСундар感謝優化和效率 –

我不知道該網站。 [問題]（http://codereview.stackexchange.com/questions/55767/finding-all-paths-from-given-graph-python） – genclik27

它確定。你會得到很好的評論，如何優化和效率 –

爲什麼你需要找到給定圖形的所有路徑？哪個上下文？我問你這個問題，因爲作爲圖論的東西在當今計算很受歡迎，有可能是一個算法完全適合您的需求...

例如，如果最後你需要比較來發現的所有路徑最好的一個，你可能會感興趣的「最短路徑問題」，並宣讀：Find all paths between two graph nodes & https://en.wikipedia.org/wiki/Shortest_path_problem

關於「優化」課題，蟒蛇允許您使用列表理解，多線程和/或子基於代碼。

您也可以嘗試使用「本機圖形數據庫」（如neo4js）來存儲您的節點，然後使用一些內置方法，如：http://neo4j.com/docs/stable/cypherdoc-finding-paths.html來完成這項工作。

問候

來源

2016-03-09 17:05:34

查找給定圖python的所有路徑

回答

相關問題