使用非递归 dfs 检测有向图中的循环

Question

我的代码有效，但不适用于所有测试用例。

我想在这里做的是创建一个 'boolean ifparent array' 来保存我正在穿越的路径的记录。

'boolean visited array'记录所有访问过的顶点。

我正在为 DFS 使用堆栈。

//v is no of vertex, adj[] is the adjacency matrix
bool isCyclic(int v, vector<int> adj[])
{
    stack<int> st;
    st.push(0);

    vector<bool> visited(v, false);
    vector<bool> ifparent(v, false);
    int flag= 0;

    int s;
    while(!st.empty()){
        s= st.top();
        ifparent[s]= true;
        visited[s]=true;
        flag=0;

        for(auto i: adj[s]){
            if(visited[i]){
                if(ifparent[i])
                    return true;
            }
            else if(!flag){
                st.push(i);
                flag= 1;
            }
        }

        if(!flag){
            ifparent[s]= false;
            st.pop();
        }
    }

    return false;

}

Answer 1

如果您喜欢使用 DFS 进行循环检测的迭代方法，我会推荐您对代码进行稍微重组的版本，我在其中以更常见的方式编写 DFS。

bool isCyclic(int V, vector<int> adj[]) {
  vector<bool> visited (V, false);
  vector<bool> on_stack (V, false);
  stack<int> st;

  for (int w = 0; w < V; w++) {

    if (visited[w])
      continue;
    st.push(w);

    while (!st.empty()) {
      int s = st.top();

      if (!visited[s]) {
        visited[s] = true;
        on_stack[s] = true;
      } else {
        on_stack[s] = false;
        st.pop();
      }

      for (const auto &v : adj[s]) {
        if (!visited[v]) {
          st.push(v);
        } else if (on_stack[v]) {
          return true;
        }
      }
    }
  }
  return false;
}

使用非递归 dfs 检测有向图中的循环

detect cycle in directed graph with non-recursive dfs

c++

algorithm

graph-theory

depth-first-search