在有向图中查找从节点到根的路径的高效图算法

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是解决这个问题的可靠解决方案。