Сложность без recursiveDFS кода

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)).

Answer 2

Вы просматриваете матрицу смежности каждого нерассмотренного узла, и каждый узел посещается ровно один раз. Таким образом, вы фактически посещаете каждый край один раз, и, следовательно, сложность O(E), которая может быть целых O(v^2) в худшем случае.