C++圖形DFS循環檢查

Question

我爲直接圖形編寫DFS方法並檢查是否存在循環。我的大部分代碼都來自我的課堂筆記和教科書。問題是它說週期存在時沒有周期。我做了一些更改，但代碼甚至沒有運行。我會很感激你的幫助。 這裏是我的檢查週期

char check; 
char vertex; 
int exit=0; 
cout<<"Checking to see if there is a DFS cycle"; 
j=0; 
for(i=0;i<columns;i++) 
{ 
    vertex=matrix[i][j]; 
    j++; 
    if(matrix[i][j]!='0') 
    { 
    check=matrix[i][j]; 
    j=0; 
    i=0; 
    int count=1; 
    while(exit<rows) 
    { 
     if(check==matrix[i][j]) 
     j++; 
     else 
     i++; 
     if(vertex==matrix[i][j]&&count>1) 
     { 
     cout<<"This graph has a DFS cycle!"; 
     break; 
     } 
     if(vertex!=matrix[i][j]&&check!=matrix[i][j]) 
     { 
     check=matrix[i][j]; 
     j=0; 
     i=0; 
     cout << "This graph has no DFS cycle!"; 
     break; 
     } 
     exit++; 
    } 
    j=0; 

    } 
    else 
    j=0; 
    } 
    system("PAUSE"); 
    return 0; 
} 

Answer 1

你可以把代碼作爲參考代碼，但它是用Java實現。您可以根據需要採用該算法。

public Cycle(Graph G) { 
    if (hasSelfLoop(G)) return; 
    if (hasParallelEdges(G)) return; 
    marked = new boolean[G.V()]; 
    edgeTo = new int[G.V()]; 
    for (int v = 0; v < G.V(); v++) 
     if (!marked[v]) 
      dfs(G, -1, v); 
} 


// does this graph have a self loop? 
// side effect: initialize cycle to be self loop 
private boolean hasSelfLoop(Graph G) { 
    for (int v = 0; v < G.V(); v++) { 
     for (int w : G.adj(v)) { 
      if (v == w) { 
       cycle = new Stack<Integer>(); 
       cycle.push(v); 
       cycle.push(v); 
       return true; 
      } 
     } 
    } 
    return false; 
} 

// does this graph have two parallel edges? 
// side effect: initialize cycle to be two parallel edges 
private boolean hasParallelEdges(Graph G) { 
    marked = new boolean[G.V()]; 

    for (int v = 0; v < G.V(); v++) { 

     // check for parallel edges incident to v 
     for (int w : G.adj(v)) { 
      if (marked[w]) { 
       cycle = new Stack<Integer>(); 
       cycle.push(v); 
       cycle.push(w); 
       cycle.push(v); 
       return true; 
      } 
      marked[w] = true; 
     } 

     // reset so marked[v] = false for all v 
     for (int w : G.adj(v)) { 
      marked[w] = false; 
     } 
    } 
    return false; 
} 
private void dfs(Graph G, int u, int v) { 
    marked[v] = true; 
    for (int w : G.adj(v)) { 

     // short circuit if cycle already found 
     if (cycle != null) return; 

     if (!marked[w]) { 
      edgeTo[w] = v; 
      dfs(G, v, w); 
     } 

     // check for cycle (but disregard reverse of edge leading to v) 
     else if (w != u) { 
      cycle = new Stack<Integer>(); 
      for (int x = v; x != w; x = edgeTo[x]) { 
       cycle.push(x); 
      } 
      cycle.push(w); 
      cycle.push(v); 
     } 
    } 
}