找到沒有指定結束節點的所有路徑？

Question

我正在嘗試進行深度優先搜索以查找所有路徑的列表，然後確定最短和最長的路徑。

Python文檔（https://www.python.org/doc/essays/graphs/）具有以下，這需要一個端節點：

def find_all_paths(graph, start, end, path=[]): 
    path = path + [start] 
    if start == end: 
     return [path] 
    if not graph.has_key(start): 
     return [] 
    paths = [] 
    for node in graph[start]: 
     if node not in path: 
      newpaths = find_all_paths(graph, node, end, path) 
      for newpath in newpaths: 
       paths.append(newpath) 
    return paths 

我的問題是如何能夠找到一個（有向無環）圖中的所有路徑，而無需指定端節點？我的開始節點在任何時候都會保持不變。

我可以在開始時使用for循環並遍歷節點。但這並不像是最有效的方式，因爲如果我可以使用相同的路徑來重新訪問節點，那將會浪費計算時間。

for node in nodeList: 
    find_all_paths(graph, 0, node) 

Answer 1

您可以修改您的深度優先搜索代碼，只需稍作調整即可找到所有終端節點的所有路徑。

首先，放下end參數，並在基地情況下start == end。然後，在開始遞歸步驟之前，只需將path添加到paths即可。在遞歸調用中，不要再試圖通過end。

就是這樣：

def find_all_paths(graph, start, path=[]): 
    path = path + [start] 
    if not graph.has_key(start): 
     return [path] 
    paths = [path] 
    for node in graph[start]: 
     if node not in path: 
      newpaths = find_all_paths(graph, node, path) 
      for newpath in newpaths: 
       paths.append(newpath) 
    return paths 

請注意，您可以在此多一點效率做一個遞歸的發電機，而不是建立路徑的大名單（我還修改了專項檢查的節點未在圖中：使用not in操作比使用dict.has_key越好）：

def find_all_paths(graph, start, path=[]): 
    path = path + [start] 
    yield path 
    if start not in graph: 
     return 
    for node in graph[start]: 
     if node not in path: 
      yield from find_all_paths(graph, node, path) 

注意yield from只有在Python 3.3及更高版本。如果您使用的是早期版本，請使用顯式循環：

for newpath in find_all_paths(graph, node, path): 
    yield newpath