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

Question

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

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

#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 

Answer 1

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