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

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

在研究图复杂度理论时，有时更容易想到"how many times do I process each edge/vertex"这个循环运行有多少次。这是因为图中的循环具有可变长度，并且随着循环的发生，事情变得一团糟。

最终，在DFS算法中，你将不得不检查每条边的另一端是什么，并决定是否访问该顶点。您将对每条边执行一次且仅执行一次。因此，您必须考虑每条边。

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