Поиск циклов с помощью поиска в глубине стека

Question

Я знаю, что вы используете рекурсивную реализацию DFS, где все узлы начинаются с белого, окрашиваются в серый цвет при первом обнаружении и окрашиваются в черный цвет после изучения всех их дочерних элементов, вы знаете, что если вы когда-либо встречать серый узел.

Но как это сделать с помощью стека?

Answer 1

Этот ответ на Stackoverflow указывает на код Java sample , реализующий DFS со стеком.

Кроме того, если вы чувствуете себя комфортно с C, и я надеюсь, что вы, как и я, любите chess , я настоятельно советую вам изучить fbk2rbm Энди Дюплана, опубликованный в открытом доступе. домен.

Это удобная утилита для преобразования Fritz power-books в Rebel 7 (открытие библиотек на шахматном языке).

Используется стек , шахматный ход рассматривается как узел.

Выдержка:

...

/* Used to hold move */
struct Move {
  char FromFile, FromRank;
  char ToFile, ToRank;
  unsigned char Eval;
  char StartVar;    
};

/* List of moves seen */
struct Move Moves[256]; 

...

Расширение программы для определения положения зацикливание обнаружение (учитывая, что различные последовательности перемещения могут привести к одной и той же позиции / столкновению) было бы отличным упражнением, связанным с вашим вопросом.