使用迭代深度优先搜索检测无向图中的环？

Question

使用迭代深度优先搜索检测无向图中的环？

5

因此，我按照以下方法以迭代方式实现了深度优先搜索：

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）检测无向图中的循环。现在，我读到了这样一句话：如果未探索的边导致到达之前访问过的节点，则该图包含一个循环。 因此，我只想问你，我应该如何确切地跟踪所有这些内容？

我将我的图形设置为这样：

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

我应该将上面的内容改为什么呢？

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

每条边的bool将被标记为true的位置在哪里？并且我需要对上面的DFS代码进行哪些更改才能检测出循环？我尝试过了，但是确实想不出该怎么做。谢谢！

- John Lui

你想要接收什么样的输出数据？ - stgatilov

我正在尝试修改上述迭代DFS算法，以便检测无向图中是否存在环。在这样做之后，我将尝试对有向图进行操作。但是我并不确定如何修改上述图形以存储查找此类信息所需的信息。 - John Lui

数组 arr 不是检查节点是否已被访问的一种方式吗？为什么需要修改图形类以添加此信息？ - Gerard Abello

但是仅仅使用arr，我如何检查循环呢？ - John Lui

我可能错了，但在这个循环中：

if (arr[*it] == false){
    mystack.push(*it);
}

如果你发现 arr[*it] 为 true，我认为你刚刚检测到一个循环。在这种情况下，边是未探索的，因为你刚刚第一次访问了 k，并且找到了一个已访问的节点。 - Gerard Abello

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- stgatilov · Accepted Answer

对于每个顶点 v，在 DFS 树中可以存储一个“父亲”节点f，即从哪个顶点 v 进入 DFS。例如，可以将其存储在堆栈中。在这种情况下，您可以在栈中存储一对值，第一个值是顶点 v，第二个值是它的父节点f。

无向图仅在遇到一条边vw指向已访问过的非v的父节点w时才具有循环。

您可以在下面看到修改后的整洁代码。

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

注意：如果图不连通，则必须从多个顶点开始进行深度优先搜索，以确保整个图都被访问。在总时间 O(V + E) 内完成这一操作。