有向圖和複雜性

Question

我有一個問題，在我的程序中發現複雜性。 它由一個有向圖組成，其中每個節點都有一個邊緣陣列列表。

有沒有人知道搜索的複雜性槽有向圖？

我的代碼：

class Project{ 
    ArrayList<Task> subProject = null; 
    int manpower, maxNr; 



    Project(int maxNr, int manpower){ 
      this.maxNr = maxNr; 
      this.manpower = manpower; 
      subProject = new ArrayList<Task>(); 
    } 
} 

class Task { 
    int id, time, staff, slack; 
    String name; 
    int earliestStart, latestStart, finished; 
    ArrayList<Edge> outEdges = null; 
    int cntPredecessors; 
    Boolean rund; 

    Task(int n){ 
     id = n; 
     cntPredecessors = 0; 
     outEdges = new ArrayList<Edge>(); 
     rund = false; 
    } 
} 

class Edge { 
    int edges; 

    Edge(int edges){ 
     this.edges = edges; 
    } 
} 

public void run(){ 
     while(runTasks == false){ 
      System.out.println("Time: " + runT); 
      for(Task t: subProject){ 
       if(t.cntPredecessors == 0 && t.rund == false){ // Checks if there is no edges to the task and if the task hasen't started 
        System.out.println("  Starting: " + t.id); 
        ferdige.add(t); 
        t.rund = true; 
        t.earliestStart = runT; 
        t.finished = runT + t.time; 
        if(cirdep < t.finished){ 
         cirdep = t.finished; 
        } 
        tId = t.id; 
        workers += t.staff; 
        System.out.println("  Current staff: " + workers); 
       } 
       if(t.cntPredecessors == 0 && t.finished == runT){ 
        maxNr--; 
        System.out.println("  Finished: " + t.id); 
        minPre(t.id); 
        workers -= t.staff; 
       } 
       if((t.cntPredecessors == 0 && t.rund == false) || (t.cntPredecessors == 0 && t.finished == runT)){ 
        System.out.println("  Current staff: " + workers); 
       } 
      } 

Answer 1

含鉬的更多信息去，你至少可以說這是$Ø通過深度優先搜索$（| | V）。但是你必須做一些事情來處理孤立的組件，因爲如果沒有路徑，DFS就無法到達節點。