使用迭代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（即DFS从其到达顶点v的顶点）存储一个“父”节点f。例如，它可以存储在堆栈中。在这种情况下，您将对存储在堆栈中，第一个值是顶点v，第二个值是顶点的父f。

无向图中有一个周期，当且仅当你遇到一个边缘大众将已经访问过的顶点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）总时间来完成。