java - 如何在 Java 中为 DAG 结构创建迭代器包装器？

Question

我想要一个数据结构的迭代器。现在我不知道什么是数据结构，也许它是一个DAG(有向无环图)，但也许它也可能是一个链表。所以我想把它包装成一个迭代器，现在不考虑特定的数据结构。

我知道如何使用类似递归的访问者访问 DAG，但我想不出一个简单干净的结构来实现迭代器方法 next() 和 hasNext()。

在迭代器中，我创建了一个当前节点实例，并使用 for 循环遍历所有子节点，然后返回到父节点。需要一个“已经访问过”的标志。所以我的 DagElement 有更多的属性:

DagElement parent
boolean alreadyVisited

我认为这不是一个干净的解决方案。

有什么建议吗？

Answer 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)、 child 排队的顺序以及他们排队的时间调整访问顺序。我不会感到惊讶，某些访问顺序可能需要立即(在构造函数中)以正确的顺序对整个节点集进行排队。