c++ - 在有向循环图中找到所有可能的路径

Question

我想在有向循环图中找到所有可能的路径。我已经编写了一个这样做的程序，但我注意到如果节点数量增加到 40 或 50 以上，它就会开始花费无限时间。

从理论上讲，N 个节点的有向循环图可能有多少条路径。是像 factorial(N) 还是什么？你能给我猜一下下面这个有 119 个节点的例子吗？当然，我只遍历一次循环，所以你可以忽略循环路径。

Graph Image

Answer 1

让我们采用图表中显示的这种常见模式:

A ---> B
|     /|
|    / v
|   /  C
|  /   |
| /    |
vv    /
D <---

请原谅 ASCII 艺术。所以这里有三个路径:A -> D、A -> B -> D 和 A -> B -> C -> D.

现在假设您有从 D 到另一个节点 G 的完全相同的图形:

D ---> E
|     /|
|    / v
|   /  F
|  /   |
| /    |
vv    /
G <---

您拥有与之前相同的类似三个路径:D -> G、D -> E -> G 和 D -> E -> F -> G.

现在，从A到G有多少条路径？

要从A 到G，您必须从A 到D。您可以通过以下三种方式之一执行此操作。然后你必须从 D 到 G。您可以通过以下三种方式之一执行此操作。这两个选择(A 到D 和D 到G)是相互独立的。因此，您有 3 * 3 = 9 从 A 到 G 的可能路径。

如果您不断重复该图，则每次重复时，可能的路径数将乘以 3。所以用三个数字，27条路径；四个数字，81条路径；等

这是指数级增长。换句话说:如果你想提高效率，就必须找到另一种方法来做你正在做的事情。

编辑:粗略估计:只计算这些数字，甚至不看中间的复杂困惑，我得到 3 * 3 * 3 * 3 * (2^8) * (4^8 ) * 3 * 3 * 2 * 3 = 73383542784 可能的路径，仅通过那些简单的节点。

编辑:您似乎在进行代码分析。在不知道你到底想做什么的情况下，我的建议是整合你沿着那些必须到达的节点收集的任何信息(例如节点A，D 和 G 在我的例子中)。然后进行搜索，直到您到达必须到达的下一个节点，并在那里收集您的信息。这将防止指数爆炸。