java - 应用访问者模式来检测图中的循环

Question

我需要检测有向图中是否存在循环，例如拓扑排序，但我想使用访问者模式。你有什么想法吗？我可以使用节点的数组列表，以及边或其他结构（不是数组）。

Answer 1

访问者模式真的无法以最纯粹的形式实现这样的事情。

请记住，访问者模式通常具有“访问者”在对象网络中旅行，但对象网络“指导”访问者。由于访问者实际上是不知道路径的，因此它可以防止某些类型的破损。

来自访问者模式的维基百科示例（Java 中）

class Car implements CarElement {
    CarElement[] elements;
 
    public Car() {
        //create new Array of elements
        this.elements = new CarElement[] { new Wheel("front left"), 
            new Wheel("front right"), new Wheel("back left") , 
            new Wheel("back right"), new Body(), new Engine() };
    }
 
    public void accept(CarElementVisitor visitor) {     
        for(CarElement elem : elements) {
            elem.accept(visitor);
        }
        visitor.visit(this);    
    }
}

注意Car接受方法。它确保覆盖汽车的所有子元素，封装导航，同时公开将外部函数应用于整个数据结构的能力。

由于您的代码需要了解数据结构是如何连接在一起的，因此访问者模式不太适合该任务。如果访问者遇到循环数据结构，未来的访问者将陷入同一个循环，无法访问某些数据，从而破坏Visitor了VisitAcceptors.

现在您可能能够在一定程度上实现目标，前提是您在访问路径中没有遵循“可能是循环的”链接。您仍然必须确保访问路径中的所有节点都跟随在访问路径中，只是访问路径的其他分支。然后，您的访问者基本上会变成一大群节点，这些节点可能会被未经过的反向链接击中，但是当您实施这样一个奇怪的解决方案时，您会想知道为什么要打扰访问者部分。