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);
        }
    }
}