图遍历

深度优先和广度优先是遍历图的两种常见方法。
图遍历是只访问图中每个顶点一次的过程。有两种流行的遍历图的方法：深度优先遍历（或深度优先搜索）和广度优先遍历（或广度优先搜索）。两次遍历都会生成生成树，可以使用类对其进行建模，如下图所示。请注意，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() 方法显示树中的所有边。

以上就是图遍历的详细内容，更多请关注叮当号网其它相关文章！