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

Question

我认为这段代码的复杂性是：时间：O（v）：v是顶点空间：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))。

Answer 2

您正在遍历每个未访问节点的邻接矩阵，并且每个节点仅访问一次。因此，您实际上访问了每个边一次，因此复杂性是O(E)，这可能与O(v^2)最坏情况一样多。