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

Question

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

Answer 1

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

请记住，访问者模式通常让“访问者”在对象网络中移动，但对象网络“引导”访问者。由于访问者实际上不知道路径，因此可以防止某些类型的破坏。

from the wikipedia example of the Visitor pattern (in 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接受方法。它确保覆盖汽车的所有子元素，封装导航，同时公开针对整个数据结构应用外部函数的能力。

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

现在，如果您的访问路径中有“可能是循环”的链接未被遵循，您也许能够在某种程度上实现该目标。您仍然必须确保图的所有节点都在访问路径中遵循，只是访问路径的其他分支遵循。然后，您的访问者基本上会成为一个大型节点集合，可能会被未访问的反向链接命中，但是当您实现如此奇怪的解决方案时，您会想知道为什么要为访问者部分烦恼。