使用迭代 DFS 检测无向图中的循环？

Question

所以，我通过以下方法以迭代的方式实现了DFS：

void dfsiter (graph * mygraph, int foo, bool arr[])
{
    stack <int> mystack;
    mystack.push(foo);
    while (mystack.empty() == false)
    {
        int k = mystack.top();
        mystack.pop();
        if (arr[k] == false)
        {
            cout<<k<<"\t";
            arr[k] = true;
            auto it = mygraph->edges[k].begin();
            while (it != mygraph->edges[k].end())
            {
                if (arr[*it] == false)
                {
                    mystack.push(*it);
                }
                it++;
            }

        }
    }
}

以上代码完全可以正常工作。现在，我想使用上面的代码（迭代 DFS）检测无向图中的循环。现在，我读到，If an unexplored edge leads to a node visited before, then the graph contains a cycle. 因此，我只想问你，我如何准确地跟踪这一切？

我的图表是这样的：

class graph
{
    public:
    int vertices;
    vector < vector<int> > edges;
};

我是否应该将上面的内容更改为：

class graph
{
    public:
    int vertices;
    vector < vector<pair<int,bool> > edges;
};

每条边的 bool 在哪里将被标记为真？我需要在上面的 DFS 代码中做哪些更改来检测周期？我试过了，但我真的想不出办法。谢谢！

Answer 1

您可以在 DFS 树中为每个顶点 v 存储一个 "father" 节点 f，即 DFS 的顶点来到了顶点v。例如，它可以存储在堆栈中。在这种情况下，您将对存储在堆栈中，第一个值是顶点 v，第二个是它的父亲 f.

一个无向图有一个循环当且仅当你遇到一条边 vw 去已经访问过的顶点 w，这不是v.

的父亲

您可以在下面看到修改和清理后的代码。

bool hascycle (graph * mygraph, int start, bool visited[])
{
    stack <pair<int, int> > mystack;
    mystack.push(make_pair(start, -1));
    visited[start] = true;

    while (!mystack.empty())
    {
        int v = mystack.top().first;
        int f = mystack.top().second;
        mystack.pop();

        const auto &edges = mygraph->edges[v];
        for (auto it = edges.begin(); it != edges.end(); it++)
        {
            int w = *it;
            if (!visited[w])
            {
                mystack.push(make_pair(w, v));
                visited[w] = true;
            }
            else if (w != f)
                return true;
        }
    }
    return false;
}

注意：如果图是断开的，那么必须从几个顶点开始DFS，保证访问到整个图。它可以在 O(V + E) 总时间内完成。

使用迭代 DFS 检测无向图中的循环？

Detecting cycle in an undirected graph using iterative DFS?

c++

graph

depth-first-search