首页 文章

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

提问于
浏览 次
2

所以，我通过以下方法以迭代方式实现了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代码中我需要做些什么改变来检测周期？我尝试了，但我真的想不出这样做的方法 . 谢谢！

c++ graph depth-first-search

1 回答

  • 4

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

    当且仅当你遇到已经访问过的顶点w的边vw时，无向图才有一个循环，这不是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）总时间内完成 .

    回复于

相关问题