Почему мое обнаружение цикла DFS на графике всегда возвращает true?

Недавно я прочитал об обнаружении циклов в графах с помощью dfs и решил реализовать его. Используя список смежности, мой код работал потрясающе, поэтому я решил решить реальную проблему, используя навыки. Вот задача, которую я выбрал. Но причина, по которой я оказался в SO, заключается в том, что мой код даже не может правильно решить примеры случаев и всегда, кажется, возвращает true (не очень странно, должно быть какая-то глупая ошибка...).

Что касается вопроса, подход, который я использовал, состоял в том, чтобы запустить dfs (поиск в глубину) и проверить, вернемся ли мы к посещенному узлу снова. Я запускаю исчерпывающий dfs, т.е. Я проверяю каждый непосещенный узел на предмет проверки. Чтобы убедиться, что расстояние между вершинами в неориентированном графе равно атласу 4, я отслеживаю рекурсивный стек и посещаемые уровни дерева pdf до самого узла в дереве (используя tmp_recursive_stack и recursion_stack, я интуитивно чувствую, что они являются корень проблемы) и наращивать прогресс, но, к счастью, код не работает. Ниже прикреплен код и тестовый пример, в котором он не работает.

#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

c++ debugging algorithm graph-theory graph-algorithm
person Nalin Bhardwaj    schedule 19.03.2015    source источник
comment
Использование осмысленных имен переменных очень помогло бы понять, что здесь происходит. Использование отдельных букв делает вещи немного загадочными для случайного наблюдателя. Ваша функция DFS не очень пригодна для повторного использования, если она выходит из приложения. Подумайте, как вы могли бы вернуть результат, чтобы main() отвечал за вывод положительного результата.   -  person Arunas    schedule 19.03.2015
comment
Возможно, причина сбоя в том, что все ваши «посещенные» флаги устанавливаются, но никогда не очищаются. Вам нужно сбрасывать флаги после каждого вызова dfs, так как вы запускаете новую DFS из нового местоположения.   -  person Arunas    schedule 19.03.2015

Ответы (1)


arrow_upward
1
arrow_downward

Ваш алгоритм неверен. Вот очень простой пример: 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 вершинами (из-за способа построения графа).

person kraskevich    schedule 19.03.2015
comment
Хммм, я не совсем понимаю, чему ты пытаешься меня научить. Я имею в виду, вы можете лучше объяснить псевдокод или дать мне несколько ссылок на страницы, которые могут меня научить? - person Nalin Bhardwaj; 19.03.2015
comment
@Nib Вы можете прочитать об этом здесь: geeksforgeeks.org/detect-cycle-undirected- graph (он говорит почти то же самое, что и мой псевдокод, но обратите внимание, код там не очень хорош: он пропускает память и использует указатели без уважительной причины). - person kraskevich; 19.03.2015