发现使用深度优先搜索所有简单路径的复杂性？ [英] Complexity of finding all simple paths using depth first search?

问题描述

感谢的想法和替代解决方案大家答复。解决问题总是受欢迎的更有效的方法，以及提醒怀疑我的假设。不过，我想你忽略了一会儿什么问题，我试图解决的算法，只是帮我分析一下大哦，我复杂的算法，因为我已经写了 - 一个所有简单路径在使用深度限制搜索的描述这里图，并实施<一href="http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices/58446#58446">here.谢谢！

Thanks to everyone replying with ideas and alternate solutions. More efficient ways of solving problems are always welcome, as well as reminders to question my assumptions. That said, I'd like you to ignore for a moment what problem I'm trying to solve with the algorithm, and just help me analyze the big-Oh complexity of my algorithm as I've written it -- an all simple paths in a graph using depth-limited search as described here, and implemented here. Thanks!

编辑：这是家庭作业，但我已提交了这项任务，我只是想知道，如果我的回答是正确的。我有点儿困惑过大O的复杂性涉及递归时。

This is homework, but I've already submitted this assignment and I'd just like to know if my answer correct. I get a little confused over Big-O complexity when recursion is involved.

---

低于原题：

我试图找到的全部路径复杂搜索所给出的的这个算法。 给定两个顶点，我发现它们之间的所有简单路径使用深度优先搜索。

I'm trying to find the complexity of an all-paths search as given by this algorithm. Given two vertices, I'm finding all simple paths between them using a depth-first search.

我知道DFS的时间复杂度为O（V + E），其空间复杂度为O（V），而我的直觉是，一个全路径的复杂性搜索将不止于此，但我中号无法确定这将是。

I know that the time complexity of DFS is O(V+E) and its space complexity is O(V), and my intuition is that the complexity of an all-paths search will be more than that, but I'm unable to determine what it will be.

相关SO问题<一href="http://stackoverflow.com/questions/1642139/algorithm-to-find-the-number-of-distinct-paths-in-a-directed-graph">here和<一href="http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices">here.

更新（根据下文评论）：

Update (in response to a comment below):

我要解决的贝肯数的问题。这通常需要找到一个对演员之间的分离程度最低的，但我必须找到所有分离度（现在，不到6，但可以改变）。

I'm trying to solve the six degrees of Kevin Bacon problem. This generally requires finding the lowest degree of separation between a pair of actors, but I have to find ALL degrees of separation (for now, less than 6, but this can change).

推荐答案

回答我的问题与我的分析，请评论/正确的！

Answering my own question with my analysis, please comment/correct!

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).

这篇关于发现使用深度优先搜索所有简单路径的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！