如何使用深度优先搜索找到所有简单路径的复杂度？

Question

感谢所有提供想法和替代方案的人。更高效的解决问题方法总是受欢迎的，同时也需要提醒我对假设进行质疑。话虽如此，请您暂时忽略我正在尝试使用算法解决的问题，帮助我分析我编写的算法的大O复杂度——使用深度限制搜索查找图中所有简单路径，如此处所述，并在此处实现。谢谢！ 编辑：这是一份作业，但我已经提交了这个任务，我只是想知道我的答案是否正确。当涉及到递归时，我会有点困惑Big-O复杂度。

原问题如下：

我正在尝试找出由此算法给出的所有路径搜索的复杂性。 给定两个顶点，我正在使用深度优先搜索查找它们之间的所有简单路径。

我知道DFS的时间复杂度为O（V + E），空间复杂度为O（V），我的直觉告诉我，所有路径的搜索复杂度将超过这个值，但是我无法确定它将是多少。

相关SO问题在此和在此。

更新（响应下面的评论）：

我正在尝试解决六度分隔的凯文·贝肯问题。这通常需要查找一对演员之间最低的分隔度，但我必须找到所有的分隔度（目前小于6，但这可能会改变）。

- hexium

---

我的实现与这里描述的实现非常相似，如果这有助于分析的话（尽管它声称是BFS，但实际上是DFS！）。 - hexium

可能存在指数级别的路径数量（例如考虑完全图），因此仅输出这些路径就需要指数时间。为什么要查找所有路径？ - ShreevatsaR

@ShreevatsaR：这是一项更大的作业的一部分。我需要找到所有路径，并使用了这个算法。现在我有困难表达它的复杂度（以Big-Oh术语）。此外，如果有更有效的解决方法，我想知道。 - hexium

是的。问题是，你只想要一个数字列表（比如每个数字对应一条路径），还是一个巨大的路径列表？例如，在完全图中，给定两个顶点，你可以通过1、2、3、...或n-2步从一个到达另一个。很容易生成这个数字列表（以及每个数字对应的一两条路径）。但是，仅仅为了产生所有可能的方式，使得这两个顶点在n/10度内相连（比如说），必然需要指数级的时间复杂度。你应该仔细看看你的作业要求是哪一个。 - ShreevatsaR

祝你好运。答案是它与深度呈指数关系，更具体的分析并不是很有趣。我可以问一下这个作业是在哪个学校/大学布置的吗？ :-) - ShreevatsaR

Answer 1

最坏情况下（我认为）是完全图，有n个顶点。该图有n！条简单路径，对于每一条路径，你的算法至少会执行n^2个计算步骤 - 对于最后一个顶点相邻的每个顶点，它都要在先前访问节点的链接列表上进行线性扫描。（这还不包括搜索的所有中间阶段）。因此，复杂度至少为O(n^2 * n!)，可能更糟。请问您想解决的更大问题是什么？

- David

---

如果我知道图是稀疏的，那么它会变成O(b！*n^2)吗？ - hexium

（其中“b”是分支因子）请返回翻译后的文本。 - hexium

我正在尝试解决六度分隔问题（http://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon）。这通常需要找到一对演员之间的最低分隔度，但我必须找到所有分隔度（少于6个（但这可能会改变））。 - hexium

阶乘方面应该超越 n^2 因子中的乘法器。 - warren

@David 假设你使用深度优先搜索找到了所有路径中的最短路径。那么复杂度会是多少呢？我基本上使用深度优先搜索来计算所有路径，然后遍历这些路径以找到最短的一条。 - RoadRunner

Answer 2

通过我的分析回答自己的问题，请评论/纠正！

The algorithm is simplified and analyzed as follows: 
(Note: here MAXDEPTH is the maximum degrees of separation to search for, default 6)
1. For the current vertex, get neighbors (amortized O(1))
2. For every neighbor, do the following [O(b), where b is the branching factor, or the avg. number of neighbors of a vertex]
2.1.    Check if already visited [O(MAXDEPTH), since it’s a linked list of max size MAXDEPTH)
2.2.    Append path to paths list [amortized O(1)]
3. End for 
4. Do the following MAXDEPTH times [O(MAXDEPTH)]
4.1.    For every neighbor do the following [O(b)]
4.1.1.      Check if already visited [O(MAXDEPTH)]
4.1.2.      Add to visited list [O(1)]
4.1.3.      Recursively call search again [becomes O(MAXDEPTH*b)]
4.1.4.      Delete from visited list [O(1)]
4.2 End for /* Neighbor */
5. End loop /* MAXDEPTH */

Thus, the complexity becomes O((MAXDEPTH*b)^MAXDEPTH).

- hexium

Answer 3

6度关系的概念很好，因为它给了你一个限制。我知道这个“6”是可以改变的，但我认为这里的方法仍然适用。在任何我说到“6”的地方，只需替换成“#度关系”即可。

如果你愿意，你可以使用广度优先搜索（BFS）。如果我理解正确，你需要找到从起点（演员/女演员）到终点（凯文·贝肯）的所有路径，且路径长度小于或等于6。你可以将其分解为子问题，首先找到所有距离1度的连接，然后找到所有距离2度的路径，...，最后找到所有距离6度的路径。这正是BFS的工作原理...首先检查所有距离一个边缘的节点，然后是两个边缘，以此类推。

另外，你也可以使用修改过的深度优先搜索（DFS），通过进行普通的DFS并尽可能地沿着每条路径走得更远，但保持计数器不超过任何特定路径的6个边缘。

我认为你的解决方案可能比普通的O(V+E)更好，因为你可能不会访问所有顶点或沿着所有边行进（假设我们的图是大量演员之间的关系），而是受限于整个图的子图。你开始搜索算法时，就像你要访问所有顶点/边缘一样，但无论你使用BFS还是DFS，你都将在距离起始顶点6个边缘处停止，而不是查看整个图。

考虑到类似DFS的东西可以表示为O(V+E)，但也可以表示为O(b^d)，其中b是分支因子，d是图深度（有关更多信息，请参见Wikipedia_DFS）。那么，考虑到有这么多演员，b会是多少？鉴于您所知道的问题约束（6度等），d会是多少？

我想我可能已经说得足够多了。希望这能为您启动它。我应该补充说明，我并不确定答案，这只是问题对我的影响方式；）

- Brent Writes Code

---

感谢您的回复，Brent Nash。实际上，我已经解决了问题并实施了解决方案，只是我无法理解复杂性分析。我确实使用了深度限制搜索（但对于所有路径<6）。由于“6”可能会改变，因此对于复杂性分析（据我所知），我需要考虑最坏情况，这将退化为完整的DFS。我试图在问题中抽象出细节，因为我只需要帮助复杂性分析。 - hexium

我想到了时间复杂度为O((MAXDEPTH*b)^MAXDEPTH)和时间复杂度为O(MAXDEPTH*b^MAXDEPTH)（基于伪代码分析——循环、递归等），但我不确定它是否正确。 - hexium

很抱歉没有给你更多的帮助...我只是在考虑是否该在家庭作业问题上给予太多额外帮助而犹豫。祝好运！ - Brent Writes Code

Answer 4

我在思考使用O((n^2)*depth)算法

1. 对于每个演员，找到他与之合作过的所有演员。(O(n^2)空间和时间复杂度，但两者都取决于实际连接数量，并且对于大多数演员不超过500或你Facebook上好友数量的5倍) 这将带来500*n的时间和空间复杂度。

2. 整合整个树结构，遍历同一层级的所有人并添加所有这些连接。O(n^2*depth)

如果您使用双向链接树来存储连接，则可以在深度*n的复杂性中找到所有连接

- Luka Rahne