深度优先和广度优先是遍历图的两种常见方法。
图遍历是只访问图中每个顶点一次的过程。有两种流行的遍历图的方法：深度优先遍历（或深度优先搜索）和广度优先遍历（或广度-首先搜索）。两次遍历都会生成生成树，可以使用类对其进行建模，如下图所示。请注意，Tree 是在 AbstractGraph 类中定义的内部类。 AbstractGraph.Tree 与搜索元素中定义的 Tree 接口不同。 AbstractGraph.Tree 是一个专门的类，用于描述节点的父子关系，而 Tree 接口定义了树中的搜索、插入和删除等常见操作。由于不需要对生成树执行这些操作，因此 AbstractGraph.Tree 未定义为 Tree.
Tree 类在 AbstractGraph.java 中第 226-293 行的 AbstractGraph 类中被定义为内部类。构造函数创建一棵具有根、边和搜索顺序的树。
Tree 类定义了七个方法。 getRoot() 方法返回树的根。您可以通过调用 getSearchOrder() 方法来获取搜索顶点的顺序。您可以调用 getParent(v) 在搜索中查找顶点 v 的父节点。调用 getNumberOfVerticesFound() 返回搜索到的顶点数。方法 getPath(index) 返回从指定顶点索引到根的顶点列表。调用 printPath(v) 显示从根到 v 的路径。您可以使用 printTree() 方法显示树中的所有边。
以上是图遍历的详细内容。更多信息请关注PHP中文网其他相关文章！
