Я знаю, что вы используете рекурсивную реализацию DFS, где все узлы начинаются как белые, окрашиваются в серый цвет при первом обнаружении и окрашиваются в черный цвет после изучения всех их дочерних элементов, вы знаете, что существует цикл, если вы когда-либо столкнетесь с серый узел.
Но как это сделать с реализацией стека?
Этот ответ на Stackoverflow указывает на код Java пример реализации DFS со стеком.
Кроме того, если вы чувствуете себя комфортно с C и я надеюсь, что вам нравятся шахматы, как и мне, я настоятельно советую вам изучить исходный код 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];
...
Расширение программы для определения позиции циклического обнаружения (учитывая, что разные последовательности движений могут привести к одной и той же позиции/столкновению) было бы отличным упражнением, связанным с вашим вопросом.
