线性时间内深度优先搜索的时间复杂度

Question

我对以下算法的时间复杂度感到困惑，它是 O(V) 还是 O(V+E)？

DFS(G,s,t):


vis[s] = true
        if s == t
            vis[s] = false, return 1
        cont = 0
        for v is adj(s)
            if vis[v] == false
                cont = cont + DFS(G,s,t)
        vis[s] = false
        return cont

Answer 1

在研究图复杂性理论时，有时更容易想到“我处理每个边/顶点多少次”而不是这个循环运行多少次。这是因为图中的循环具有可变长度，并且随着循环的进行，事情就会变得混乱。

最终，在 DFS 算法中，您必须检查每条边的另一端是什么，并决定是否访问该顶点。您将只对每个边执行一次此操作。所以，你有义务考虑每一条边。

由于每个顶点也被考虑（访问）一次，因此这会产生 O(V+E) 复杂度。