枚舉圖中單個來源的所有路徑

我想知道是否知道一種算法來枚舉單個來源的圖中所有可能的簡單路徑，而不重複任何頂點。請記住，該圖將非常小（16個節點）並且相對稀疏（每個節點2-5個邊）。枚舉圖中單個來源的所有路徑

爲了使我的問題明確：

頂點：A，B，C

A connects to B, C 
B connects to A, C 
C connects to A, B

路徑（從A）：

A,B 
A,C 
A,B,C 
A,C,B

頂點：A，B，C，d

A connects to B, C 
B connects to A, C, D 
C connects to A, B, D

路徑（來自A）：

A,B 
A,C 
A,B,C 
A,B,D 
A,C,B 
A,C,D 
A,B,C,D 
A,C,B,D

這當然不是BFS或DFS，儘管它們可能的變體之一可能有效。我在SO中看到的大多數類似問題都是處理一對節點圖，所以我的問題稍有不同。

此外Find all possible paths from one vertex in a directed cyclic graph in Erlang是相關的，但答案太Erlang相關或不清楚究竟需要做什麼。正如我所看到的，該算法可以替代地描述爲從單個來源找到所有可能的簡單路徑，用於指定的跳數。然後對於跳數（1到N），我們可以找到所有的解決方案。

我使用Java，但即使是僞代碼對我來說也是足夠的幫助。

來源

2014-01-26 Alexandros

在Python的風格，這是一個不同的跟蹤一個BFS的訪問：

MultiplePath(path, from): 
    from.visited = True 
    path.append(from) 
    print(path) 

    for vertex in neighbors(from): 
    if (not vertex.visited): 
     MultiplePath(path, vertex) 

    from.visited = False 
Return

來源

2014-01-26 23:15:10 Rodolfo

枚舉圖中單個來源的所有路徑

回答

相關問題