檢查是否存在包含一組N個節點的路徑

Question

給定圖g和一組N個節點my_nodes = [n1, n2, n3, ...]，如何檢查是否存在包含所有N個節點的路徑？如該圖生長

上面的搜索可以被限制在my_nodes成對耦合之間的路徑間all_simple_paths

1. 檢查包含在my_nodes所有節點的路徑計算上變得笨重。這只是在很小程度上降低了複雜性。加上它需要很多蟒蛇循環，這是很慢的

是否有更快的解決方案來解決這個問題？

Answer 1

您可以在這裏嘗試一些貪婪算法，從所有節點的路徑查找檢查中查找，並逐步瀏覽您的圖形。不能提供一些實際樣品，但僞代碼應該是這樣的：從您的所有n節點

• 開始n路徑存根找到
• 對於所有這些路徑存根由所有的鄰居進行調整，其之前沒有檢查過
• 如果你在路徑樁之間有一些交集，那麼你得到了一個新的，它包含了比以前更多的你需要的節點
• 如果在合併存根路徑之後，需要的節點，你完成了
• 如果還有一些額外的節點添加到路徑，則繼續第二步再次
• 如果沒有留在圖中的節點，路徑不存在

該算法的複雜性O(E + N)，因爲你正在以非遞歸方式訪問邊和節點。

但是，在有向圖的情況下，「合併」會稍微複雜一點，但仍然會完成，但在這種情況下，最糟糕的情況可能需要很長時間。

更新：

至於你說的那個圖是定向的，上面的方法將無法正常工作。在這種情況下，你可以簡化你的任務是這樣的：

• 查找圖中的strongly connected components（我建議你自己來實現它，例如，Kosaraju's algorithm）。複雜度爲O(E + N)。如果您需要一些收件箱解決方案，則可以使用NetworkX method for this。
• 根據步驟1信息創建圖表的縮合，並保存關於哪個組件可以從其他組件訪問的信息。再次，這裏有一個NetworkX method。
• 現在你可以很容易地說，你的集合中的哪些節點在同一個組件中，所以包含所有這些節點的路徑肯定存在。
• 之後，您需要檢查的是您的節點的不同組件之間的連接。例如，您可以獲得topological sort of condensation並再次檢查線性時間。