c++ - 为什么图中的DFS周期检测总是返回true？

我最近读到了关于使用dfs在图中进行循环检测的文章，并决定实现它。使用邻接列表，我的代码运行得非常棒，所以我决定使用这些技巧来解决实际问题这是the problem I chose。但是，我最终这么做的原因是，我的代码甚至无法正确地解决示例案例，而且似乎总是返回true（不是很奇怪，一定是一些愚蠢的bug…）。
对于这个问题，我使用的方法是运行一个dfs（深度优先搜索）并检查我们是否再次访问一个访问过的节点。我运行详尽的dfs，即检查每个未访问的节点。为了确保无向图中顶点之间的距离是Atlas4，我一直跟踪递归堆栈和访问的PDF树的级别，直到树中的每个节点（使用tmp_recursive_堆栈和recursion_堆栈，我有一种直观的感觉，它们是问题的根本原因），并建立在进度上，但幸运的是，代码无法执行下面是失败的代码和测试用例。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int n, m;
vector<string> matrice;
vector< vector<bool> > flag;
int recursion_stack = 0;

void dfs(int i, int j)
{
    if(!flag[i][j])
    {
        flag[i][j] = true;
        recursion_stack++;
        int tmp_rec_stack = recursion_stack;
        if(j > 0)
        {
            if(matrice[i][j] == matrice[i][j-1])
            {
                if(flag[i][j-1] && recursion_stack >= 3)
                {
                    cout << "Yes\n"; exit(0);
                }

                dfs(i, j-1);
            }

        }
        recursion_stack = tmp_rec_stack;
        if(j < m-1)
        {
            if(matrice[i][j] == matrice[i][j+1])
            {
                if(flag[i][j+1] && recursion_stack >= 3)
                {
                    cout << "Yes\n"; exit(0);
                }

                dfs(i, j+1);
            }
        }
        recursion_stack = tmp_rec_stack;
        if(i < n-1)
        {
            if(matrice[i][j] == matrice[i+1][j])
            {
            if(flag[i+1][j] && recursion_stack >= 3)
                {
                    cout << "Yes\n"; exit(0);
                }

                dfs(i+1, j);
            }
        }
        recursion_stack = tmp_rec_stack;
        if(i > 0)
        {
            if(matrice[i][j] == matrice[i-1][j])
            {
                if(flag[i-1][j] && recursion_stack >= 3)
                {
                    cout << "Yes\n"; exit(0);
                }

                dfs(i-1, j);
            }
        }
    }
}

int main(void)
{
    scanf("%d%d", &n, &m);
    matrice.clear(); matrice.resize(n);
    flag.clear(); flag.resize(n, vector<bool>(m, false));
    for(int i = 0;i < n;i++) cin >> matrice[i];

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            if(!flag[i][j])
            {
                dfs(i, j);
                recursion_stack = 0;
            }
        }
    }
    cout << "No\n";
}

失败的测试用例：

IN
3 4
AAAA
ABCA
AADA

预期出局：

No

我的出局：

Yes

最佳答案

你的算法不正确这里有一个非常简单的例子：AAA。假设您从最左边的位置执行深度优先搜索当它到达最右边的A时，recursion_stack是3因此，当它检查(i, j - 1)单元格（这是第二个A）时，它会发现一个不存在的循环。怎么解决好吧，最简单的方法是实现一个寻找周期的正确算法，而不是试图修复这个周期下面是正确解决方案的伪代码：

hasCycle = false
visited = an empty set

dfs(node, parent)
    visited.add(node)
    for child <- children(node)
         if not child in visited
             dfs(child, node)
         else if child != parent
             hasCycle = true

for node <- nodes
    if not node in visited
        dfs(node, node) // we can also use a fictive value for a parent like null
print hasCycle

这是正确的，因为它在一个图中发现了一些圈，并且在这个问题中没有少于4个顶点的圈（由于图的构造方式）。

关于c++ - 为什么图中的DFS周期检测总是返回true？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29147748/