使用Boost圖庫找到的所有路徑

Question

我有一個DAG，我需要能夠找到一個區域內的一定長度的所有可能的路徑。例如，我想找到所有包含至少3個頂點但不超過7個頂點的路徑。我首先想到的是找到一個能找到所有路徑的算法，然後把它們除掉。

任何人都可以提供意見？

Answer 1

枚舉長度K的所有路徑是在一般O（2^K），所以我認爲以上未列舉的所有可能路徑的建議是好的。例如：

比方說，在這個圖中所有的邊是有向從左至右（所以這是一個DAG）。然後從最左邊到最右邊的節點有2^3個路徑（即長度爲6的2^3路徑），因爲對於3個「鑽石」中的每一個，您可以選擇採用上面或下面的路徑（所以我們正在所有三個二元選擇的排列）。您可以根據圖案來擴展圖形（通過釘在鑽石上），對於K鑽石，將會有2^K的長度爲2K的路徑。

所以，你可能會想枚舉只有你有（特別是如果他們在你的例子短等）的路徑。我認爲上面的建議使用寬度優先搜索將用於枚舉所有路徑，但對於較大的情況下，空間要求將是2^K（當查找長度爲K或更小的所有路徑時）。我這樣說是因爲你必須記住長度爲n-1的所有路徑才能找到所有長度爲n的路徑。深度優先搜索（或者更確切地說，它的修改版本）會工作，以及：

DFS(int maxLen, Node node): 
    list<Node> path 
    path.add(node) 
    DFS_Helper(maxLen, path) 

DFS_Helper(int maxLen, list<Node> path): 
    print(path) 
    if (path.size() >= maxLen) 
     return 
    set<Node> targets = graph.getNodesPointedToBy(path.last()) 
    for Node target in targets: 
     path.append(target) 
     DFS(maxLen, path) 
     path.removeLastNode() 

佔用空間O（| V |）（V中的任何頂點頂點集可以出現在「目標」由於該圖是非循環的，因此最多設置一次遞歸調用）。請注意，這仍然會有O（2^k）運行時（不可避免的如上所述），我猜測那是因爲這種提升將不會有一個現成的算法爲你做到這一點（這就是爲什麼我包含了一些僞代碼以上）。這不包括下限，但不應包括太差。

編輯：我本來認爲，DFS的空間使用是O（K）其中K爲最大路徑長度。這是不正確的，並且低於實際的空間使用情況，因爲我忽略了將每個遞歸調用中設置的「目標」使用的空間都包含在DFS_Helper中。空間使用率仍然明顯低於BFS。