複雜

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