Как создать итератор-оболочку для структуры DAG в Java?

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

Я знаю, как посетить DAG с рекурсивным посетителем, но я не могу придумать простую и чистую структуру для реализации итерационных методов next() и hasNext().

Внутри итератора я создал текущий экземпляр узла и повторите с циклом for по всем дочерним узлам, а затем вернитесь к родительскому узлу. Необходим "уже посещенный" флаг. Итак, мой DagElement имеет следующие дополнительные атрибуты: 

DagElement parent
boolean alreadyVisited

Я не думаю, что это чистое решение.

Какой-нибудь совет?

1 2
iterator directed-acyclic-graphs

1 ответ:

Быстрый и грязный метод преобразования рекурсивной эвристики в итеративную заключается в использовании стека (LIFO) или очереди (LILO) для хранения "дорог, не занятых" - путей, найденных, но еще не занятых. В этом случае итератор будет иметь переменную экземпляра стека или очереди. Что-то вроде:

    class DagIterator<T>
    extends Iterator<T> {

        private Stack<DagNode<T>> nodes;

        private DagIterator(Dag<T> dag) {
            nodes.push(dag.getRootNode());
        }

        public boolean hasNext() {
            return ! nodes.isEmpty();      
        }

        public T next() {
            final DagNode node = nodes.pop();
            for (final DagNode child : node.getChildren()) {
                nodes.push(child);
            }
            return node.getValue();
        }

    }

Вы настраиваете порядок посещения на основе структуры данных (LIFO или LILO), порядок, в котором дети поставлены в очередь, и когда они поставлены в очередь. Меня бы не удивило, что некоторые посещения заказы могут потребовать постановки в очередь всего набора узлов в надлежащем порядке с самого начала (в конструкторе).

1