深度优先和广度优先是遍历图的两种常见方法。图遍历这是一个只访问图中每个顶点一次的过程。流行的遍历图有两种方法:深度优先遍历(或深度优先搜索)和广度优先遍历(或优先搜索广度)。两次遍历都会生成生成树,可以用类来建模,如下图所示。请注意,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() 这种方法显示了树的所有边缘。
以上是图遍历的详细内容,请关注图灵教育的其他相关文章!