访客设计模式和深度优先搜索之间的区别？

Question

深度优先搜索似乎能够执行与访问者设计模式类似的功能。访问者允许您定义一些数据结构，并根据需要在这些结构上添加操作（以多个访问者的形式），而无需修改结构本身。 wikipedia 上提供了访问者模式的描述。如果我们对数据结构进行深度优先搜索（或任何其他图搜索算法，如广度优先搜索），并且每次找到结构的元素时，我们都会运行所需的操作，那么这似乎执行与访客。例如，考虑一棵树。即使树的某些节点具有不同的类型，我们仍然可以在进行DFS时检查节点类型，然后根据节点类型执行不同的操作。

Answer 1

深度优先搜索就是搜索。访问者模式与深度优先搜索正交，从某种意义上说，访问者不一定关心如何遍历树；它只知道需要在每个节点上/对每个节点做什么。

Answer 2

您可以在没有 DFS 的情况下实现访客。同样，您可以在不使用访问者模式的情况下执行 DFS。它们是完全分开的。

我碰巧同意它们可以以一种优雅的方式一起使用的含义。

请注意，对于规范的访问者模式，被访问的对象需要实现某种 AcceptVisitor 接口 - 您问题中的“不修改结构本身”子句让我怀疑您是否在做那。

Answer 3

让我用代码来回答这个问题：

/**
 * This method makes it easier for a class to process all
 * the nodes in an item. The class should implement
 * the NodeVisitor interface. This method will cause the 
 * NodeVisitor.processNode() method to be called once for each
 * node in this item. 
 * @param visitor the class that will visit each node
 * @throws PipelineException some recoverable exception
 */
public void visitNodes(NodeVisitor visitor) throws PipelineException {
    visitNodes(visitor, root);
}

private void visitNodes(NodeVisitor visitor, Node node) throws PipelineException {
    visitor.processNode(node);
    if (node.hasChildren()) {
        int childCount = node.getChildCount();
        NodeList children = node.getChildren();
        for (int i = 0; i < childCount; i++) {
            visitNodes(visitor, children.get(i));
        }
    }
}

/**
 * Classes that implement this interface can be used with
 * Item.visitNodes(). This method provides a convenient
 * way to iterate over all the nodes in an item.
 */
public interface NodeVisitor {
        public void processNode(Node node) throws PipelineException;
}

在本例中，visitNodes() 方法实现了深度优先搜索，但它不是必须的。它可以实现任何命中所有节点的搜索。它是 VisitNodes() 方法和 NodeVisitor 接口的组合，构成了“访问者模式”（或其一种特定表现形式）。

设计模式和搜索算法之间没有“权衡”。设计模式只是让算法更容易使用。

Answer 4

在图论中，您可以构造一个图，使得最小生成树不是来自深度优先搜索的路径，更确切地说，它是一个非路径：https://cs.stackexchange.com/questions/6749/深度-首先搜索找到最小生成树。我认为你不能将其应用于设计模式。

Answer 5

深度优先搜索是一种“算法”，而访问者模式是一种忘记算法问题并专注于要执行的操作的方法。

实际上，访问者模式可能是索引内容的好方法，因为它提供了“结构不可知”的行为（您可以更改结构而无需重写访问者）

但是如果您想要执行搜索，我不建议您使用它。任何搜索算法都与特殊类型的结构（树、有向图、流程图等）相关。

在某些情况下，您可以使用访问者模式实现深度优先搜索 >，但这不是这个模式的目的。

访问者模式的使用并不取决于您所使用的解析类型，而是取决于必须执行解析的目的。

Answer 6

visitor 实例可以选择按照自己的意愿访问其子节点，并且不受深度优先搜索的遍历顺序的约束。 （例如，它可以使用呼吸优先搜索）

另一件事是要遍历的结构不需要是显式树。我已经实现了访问者，它迭代根本不像树的结构化数据。在这种情况下，我使用了访问者，因为我可以隐藏正在解析的文件的复杂二进制格式，并允许客户端控制他们想要解析的结构的哪些部分，而不需要他们知道文件格式规范。

Answer 7

我也同意 NRITH 的答案，因为访问者模式知道“只对节点做什么” 在该访问者之上，让您“定义一个新操作，而无需更改其上元素的类”它运行'，DFS 讨论如何执行节点搜索。但是为了执行深度遍历和短路分支遍历，我们使用分层访问者模式( http://c2.com/cgi/wiki?HierarchicalVisitorPattern）。

您还可以查看我什么时候应该使用访客设计Pattern？讲的是访问者模式/DFS/分层访问者模式之间的关系。

Answer 8

访问者模式（第一个？）在 Erich Gamma 等人的“设计模式”中描述。等人。在accept方法中并不一定包括对数据结构的遍历。虽然这是一个非常方便的组合，但在本书的示例代码章节末尾有一个明确的外部迭代示例。

因此，正如其他人已经说过的，在接受方法之外实现的深度优先遍历仍然可以实现访问者模式。那么问题是，调用 element.accept(visitor) 进而直接调用访问者.visitElement(me) 与直接调用访问者.visitElement(element) 之间有什么区别？
我只能看到人们想要这样做的两个原因：

1. 您不能或不想找出元素的具体类，并且通过愚蠢地调用 element.accept(visitor)，元素本身必须决定，无论是visitor.visitElement还是例如visitor.visitAnotherElement都是要调用的正确操作。

2. 某些元素是复合元素，无需外部访问所包含的内部元素，并且访问者操作是为内部元素定义的。因此，accept 方法将循环遍历内部元素并调用 Visitor.visitInnerElement(innerElement)。由于您无法从外部获取内部元素，因此您也无法从外部调用访问者.visitInnerElememt(innerElement)。

总结：如果你有一个封装得很好的遍历算法，你可以传入一个类似“Visitor”的类，并且能够根据遍历过程中遇到的对象类型分派到匹配的访问方法，那么你不需要担心接受方法。您仍然可以通过添加新的访问者实现来添加新的操作，而无需触及您的数据结构或遍历算法。这是否仍应称为访问者模式是一个相当学术性的讨论。
我认为在大多数情况下，只有当接受方法的实现也包括遍历时，使用接受方法才有意义。