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

Question

我的代码可以运行，但并非所有测试用例都适用。

我在这里尝试创建一个“布尔型ifparent数组”，它保存了我正在遍历的路径记录。

“布尔型visited数组”记录了所有已访问的顶点。

我正在使用堆栈进行深度优先搜索。

//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;

}

- Vipul

---

哪些情况不起作用？对于这些情况，实际结果是什么，预期结果又是什么？ - undefined

@JaMiT 链接 这是问题的链接。 - undefined

问题应该是自包含的，不依赖于外部链接来获取关键信息。请编辑问题以解释哪些情况不起作用，这些情况下的实际结果是什么，以及这些情况下的预期结果是什么。 - undefined

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

- gimme_danger

---

如果（！visited[v]）{ no_unseen_adjacent = false; st.push(v); } 这个代码块将会把每个相邻的节点都压入栈中，这样就不再是深度优先搜索了。 - undefined

推送所有相邻节点不会破坏深度优先遍历。这只涉及节点访问的顺序。实际上，递归和迭代方法有不同的顺序。无论如何，我的代码中有一个错误，我已经修复了它，并在您提供的链接上检查了新代码。现在测试系统接受它。 - undefined

你的代码很有帮助。我发现我没有考虑到断开的图的情况。 - undefined

考虑一下递归版本的循环检测算法。我认为这种方法更直观。这里有一个链接，提供了一个很好的实现：链接。 - undefined