algorithm - DFS in DFS, DFS with a known string

Question

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

外部 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) 因为有一个讨厌的图形您可能仍然会发现自己遍历了所有的边和所有的顶点。