DFS在DFS中，具有已知字符串的DFS

Question

我正在寻找我的代码的复杂性计算。它只是DFS (深度优先搜索)中的DFS(深度优先搜索)。DFS从头到尾在一个图(状态机)上运行(向后搜索)。每当它到达start时，它就会累积使其到达start的字符串，并使用另一个DFS在另一个图上尝试该字符串，以检查它是否也在具有相同字符串的另一个图上达到start状态。

外部DFS复杂度确定为O(Vo+Eo)，其中Vo :外部图中的顶点数，Eo :外部图中的边数。但是，当将要跟随的字符串已知时，DFS内部的复杂性是什么？

如果可能的话，你能对整个算法的复杂性负责吗？

我不确定它是O((Eo+Vo)+(Ei+Vi))还是O((Eo+Vo)(Ei+Vi))还是smtg .else

先谢谢你，

Answer 1

这取决于您在第二个DFS失败的情况下如何处理。失败的意思是告诉您第二个图不包含在第一个DFS中找到的字符串。

如果第二个DFS失败意味着您在第一个DFS中回溯并搜索另一个字符串，然后再次尝试第二个DFS，那么您的复杂性就是O((Eo+Vo)*(Ei+Vi))，因为在最坏的情况下，您可能会为第一个DFS中到开始节点的每个单独的DFS路径执行第二个图的完整DFS。

如果第二个DFS失败意味着您停止，那么在最坏的情况下，您将执行第一个图的单个DFS和第二个图的单个DFS，从而导致O((Eo+Vo)+(Ei+Vi))最坏情况的复杂性。

DFSing检查图形是否包含字符串的事实意味着，在某些情况下，您可以提前终止DFS (例如，您到达一个没有剩余字符可供检查的非起始顶点)。然而，你是否能够提前终止完全取决于图的结构，所以我会说第二个DFS在最坏的情况下仍然是O(Ei+Vi)的，因为对于一个讨厌的图，你可能仍然会发现自己正在经历所有的边和所有的顶点。