java - 如何遍历图 "forwards"和 "backwards"？

Question

我正在使用调查图/图遍历

compile group: 'org.jgrapht', name: 'jgrapht-core', version: '1.1.0'

使用下面的代码我可以创建一个简单的图表

final Graph<String, DefaultEdge> directedGraph = new DefaultDirectedGraph<>(DefaultEdge.class);
directedGraph.addVertex("v1");
directedGraph.addVertex("v2");
directedGraph.addVertex("v3");
directedGraph.addVertex("v4");

directedGraph.addEdge("v1", "v4");
directedGraph.addEdge("v4", "v2");
directedGraph.addEdge("v2", "v3");      

并“向前”遍历它

TopologicalOrderIterator<String, DefaultEdge> topologicalOrderIterator = new TopologicalOrderIterator<>(directedGraph);
System.out.println("topologicalOrderIterator");
while (topologicalOrderIterator.hasNext()) {

    System.out.println(topologicalOrderIterator.next());

}

但是，我还希望能够从任何顶点“回溯”我的步骤并返回到图表的“开始”。

例如topologicalOrderIterator.previous()

我在jgrapht-core中看不到任何明显的方法？

可以进行反向图遍历吗？ (逻辑？)

Answer 1

TopologicalOrderIterator 没有 previous() 方法。解决此问题的一个简单方法是实现您自己的迭代器，该迭代器扩展了 TopologicalOrderIterator 并维护您遇到的项目的内存。这是一个未经测试、格式不正确的示例:

public class ReversibleTopoIterator extends TopologicalOrderIterator{
    Stack<V> back=new ...
    Stack<V> front=new ...

    public V next(){
        V v;
        if(front.isEmpty())
            v=super.next();
        else
            v=front.pop();
        back.push(v);
        return v;
    }
    public V previous(){
        V v=back.pop();
        front.push(v);
        return v;
    }
    public boolean hasNext(){return !front.isEmpty() || super.hasNext()};
    public boolean hasPrevious(){return !back.isEmpty()}
}

总之，您维护 2 个堆栈back 和front。如果使用 next() 方法向前移动，则首先清空 front 堆栈，然后向 TopologicalOrderIterator 请求新元素。使用 next() 获得的所有项目都被推送到 back 堆栈上。同样，如果使用 previous() 方法向后移动，则会弹出 back 堆栈中的项目。使用 previous() 方法获得的所有项目都被推送到 front 堆栈上。