從格拉夫

Question

如何檢測如果一個圖具有周期或不從該部分的代碼，其示出了檢測週期深度優先搜索的曲線圖是在鄰接矩陣

// ------------------------------------------------------------ 
    public void dfs() // depth-first search 
    { // begin at vertex 0 
     int k = 0; 
     vertexList[0].wasVisited = true; // mark it 
     displayVertex(0); // display it 
     theStack.push(0); // push it 
     while (!theStack.isEmpty()) // until stack empty, 
     { 
      // get an unvisited vertex adjacent to stack top 
      int v = getAdjUnvisitedVertex(theStack.peek()); 
      int x = nAdjVisitedVertex(v); 

      if (v == -1) // if no such vertex, 
       theStack.pop(); 
      else // if it exists, 
      { 
       vertexList[v].wasVisited = true; // mark it 
       displayVertex(v); // display it 
       if (x == 2) 
        k++; 

       theStack.push(v); // push it 

      } 
     } // end while 
      // stack is empty, so we’re done 
     for (int j = 0; j < nVerts; j++) 
      // reset flags 
      vertexList[j].wasVisited = false; 

     if(k != 0) 
      System.out.println("not a cycle"); 
     else 
      System.out.println("cycle"); 

    } // end dfs 

Answer 1

實現在遍歷該圖，你需要繼續尋找已經訪問過的節點。如果您遇到已經訪問過的節點，則會發現一個循環。如果遍歷完成而沒有獲取任何訪問節點，則圖中沒有循環。關於實施，首先嚐試，如果您遇到任何問題，請回過頭來解決問題。