Проверьте, является ли график циклическим

Question

Следующий код работает нормально, за исключением случаев, когда он проходит через ациклический граф.Он помечает ациклический граф как циклический, и я не могу понять, почему.

   @Override
    public boolean isCyclic(DirectedGraph<T> graph) {
        List<Node<T>> visitedNodes = new ArrayList<>();
        int cycles = 0;

        for (Node<T> node : graph) {
            if (recNodeCycleCheck(node, visitedNodes)) {
                cycles++;
            }

            visitedNodes = new ArrayList<>();
        }

        return cycles > 0;
    }

    private boolean recNodeCycleCheck(Node<T> node, List<Node<T>> visitedNodes) {
        if (visitedNodes.contains(node)) {
            return true;
        }

        visitedNodes.add(node);

        for (Iterator<Node<T>> it = node.succsOf(); it.hasNext();) {
            Node<T> currentNode = it.next();

            if (visitedNodes.contains(currentNode)) {
                return true;
            }

            if (recNodeCycleCheck(currentNode, visitedNodes)) {
                return true;
            }
        }

        return false;
    }

Я пытался назвать код как можно более понятным, чтобы его было легко читать.Первый метод isCyclic () получает граф, и для каждого узла в графе он проверяет свой смежный список и преемников узлов в этом списке.Если в какой-то момент они указывают на уже посещенный узел, график является циклическим.

Кажется, это работает нормально для всех графиков, кроме ациклических.

Есть идеи, что происходит?

Answer 1

Ваша логика, вероятно, не создана для учета следующего случая ациклического графа:

//A, B and C are the nodes in the graph
A -> B // Edge between A and B
B -> C // Edge between B and C
A -> C // Edge between A and C

В этом случае ваш алгоритм работает так: он начинается с A, посещает B и C. Затемидет к следующему преемнику A (который является C), затем видит, что он уже посещен, и возвращает true.