algorithm - 非递归 DFS 代码的复杂性

Question

我认为这段代码的复杂度是:时间 : O(v) : v 是顶点Space: O(v) : v是顶点

public void dfs() {
        Stack<Integer> stack = new Stack<Integer>();
        stack.add(source);

        while (!stack.empty()) {
            int vertex = stack.pop();
            System.out.println(" print v: " + vertex);
            for (int v : graph.adj(vertex)) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.add(v);
                    edgeTo[v] = vertex;
               }
            }
        }
    }

如有错误请指正

Answer 1

假设 graph.adj() 总是产生有限数量的顶点(可能只有一个)，那么你是对的。

但是，如果它以任何方式取决于系统中存在的顶点总数，则不是。如果这种依赖是线性的，那么算法就是 O(n^2)。

一般来说，如果 f(n) 是每个顶点 graph.adj() 的平均数，那么答案就是 O(n*f(n))。