在有向圖中查找從節點到根的路徑的高效圖算法

Question

我有一個有特定根節點的有向圖，從中可以找到所有其他節點。

很容易找到一個任意算法來查找從給定節點到根的所有路徑，例如這個solution (DFS) using LinkedHashSets。

那麼，這個算法適用於小圖，但是對於較大的圖，它在合理的時間內不會結束。

我的示例圖有129個節點和200條邊。在我眼裏不中有着非常巨大的圖 ...

有人可以給我一個提示如何有效地解決這個問題？

也許我們可以利用我的圖表的其他屬性。他們都是：

• 連接
• 直接與循環
• 有指定的起始節點
• 有指定的終端節點

Answer 1

嗯，不是真的 - 你不能讓它顯著更多高效的，因爲輸出尺寸本身是巨大的。路徑的數目是在節點數量指數，看看這個簡單的例子：

V = {a, b, c}, E = {(a,b), (a,c), (b,c)} 

這看起來很簡單，有「只有」領導到c圖2無小事路徑。 a→c，a→b→c。

現在，考慮增加一個節點d與邊緣（d，A），（d，B） - 你將有3路從新根導致c，d->a->b->c，d->a->c，d->b->c，還不算太差，但注意在將e與(e,d),(e,a)一起添加時，會得到一個從e->d開始的「家族」（以上3個路徑），此外，還有以「e-> a」（2個路徑）開頭的「家族」路徑。總共有5條路徑。通過重複這個過程，您將獲得另外兩個家庭，一個家庭擁有5條路徑，另一個家庭擁有3條路徑。你可能會開始明白，如果你重複k這個過程，你會得到#fibo(k)不同的路徑，but the fibonacci number is very, very big for inputs such as 100（約354 * 10^20，並且保持快速增長）。

因此，無論你做什麼 - 查找圖中的所有路徑將會效率低下，除了一些「簡單」圖形（如樹）。

---

TL;博士：
有指數數量的路徑通往目標節點，並發現他們都需要指數時間。 DFS是解決這個問題的可靠解決方案。