지시 된 그래프 및 복잡성

Question

내 프로그램의 복잡성을 찾는 데 문제가 있습니다. 각 노드가 가장자리의 arraylist를 갖는 하나의 방향 그래프로 구성됩니다.

누군가가이 유도 그래프를 검색하는 복잡성을 알고 있습니까?

내 코드 : 깊이 우선 탐색을 사용하여 $ (| | V) 미주리와

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

자세한 내용에 갈 최소한이 $ O를 말할 수 있습니다. 하지만 격리 된 구성 요소를 처리하기 위해 뭔가해야합니다. 경로가 없으면 DFS가 노드에 도달 할 수 없기 때문입니다.