我们可以将二叉树的父与子之间的关系推广到树上,这样每个父亲的儿子 可以有许多个,而且可以排出顺序。于是,关于二叉树的三种遍历算法完全可以 移置到一般的树上来。 树的先根次序遍历算法 i.若T为空,则返回 访问T的根 ii.按树的先根次序遍历T的第一棵子树; iv.按树的先根次序依次遍历T的其余子树。 树的中根次序遍历算法 V.若T为空,则返回 按树的中根次序遍历T的第一棵子树 vi.访问T的根; vii.按树的中根次序依次遍历T的其余子树。 树的后根次序遍历算法 若T为空,则返回 x.按树的先根次序遍历T的第一棵子树; xi.按树的先根次序依次遍历T的其余子树。 访问T的根; 般图的遍历 无论是二叉树还是一般的树,由于其不含有圈,所以属于同根的各个子树之 间是相互独立的(树中去掉一点以及与之关联的所有边后,出现若干棵树,均称 之为以这点为根的子树)。因此遍历过程是对各个子树的分别遍历和对根遍历以 及把这些遍历有机地组合起来。一般的图没有这种独立性,所以上述方法不能施 行。但是,上述方法的思想可以借鉴,于是产生了深度优先搜索方法和宽度优先 搜索方法。 问题:在一个给定的图G=(V,E)中是否存在一条起于顶点v而终于顶点u 的路径?确定与某一起点ⅴ有路相通的所有顶点 1。宽度优先搜索算法(BFS) 开始:起点v和一个空的待访队列Q。 从顶点ⅴ开始访问,并将v标记为已访问的顶点。然后顺序(这个顺序通 常是图的顶点存储顺序)搜索邻接于顶点v的未被访问的顶点,并把这些顶点依 次放在待访队列Q的尾部。 用队列Q的首元素u替换ⅴ(并从队列Q中去掉首元素u),重复以上过程, 直到队列Q空为止。 图的宽度优先搜索算法伪代码我们可以将二叉树的父与子之间的关系推广到树上，这样每个父亲的儿子 可以有许多个，而且可以排出顺序。于是，关于二叉树的三种遍历算法完全可以 移置到一般的树上来。 树的先根次序遍历算法： i. 若 T 为空，则返回； ii. 访问 T 的根； iii. 按树的先根次序遍历 T 的第一棵子树； iv. 按树的先根次序依次遍历 T 的其余子树。 树的中根次序遍历算法： v. 若 T 为空，则返回； vi. 按树的中根次序遍历 T 的第一棵子树； vii. 访问 T 的根； viii. 按树的中根次序依次遍历 T 的其余子树。 树的后根次序遍历算法： ix. 若 T 为空，则返回； x. 按树的先根次序遍历 T 的第一棵子树； xi. 按树的先根次序依次遍历 T 的其余子树。 xii. 访问 T 的根； z 一般图的遍历 无论是二叉树还是一般的树，由于其不含有圈，所以属于同根的各个子树之 间是相互独立的（树中去掉一点以及与之关联的所有边后，出现若干棵树，均称 之为以这点为根的子树）。因此遍历过程是对各个子树的分别遍历和对根遍历以 及把这些遍历有机地组合起来。一般的图没有这种独立性，所以上述方法不能施 行。但是，上述方法的思想可以借鉴，于是产生了深度优先搜索方法和宽度优先 搜索方法。 问题：在一个给定的图 G=(V,E)中是否存在一条起于顶点 v 而终于顶点 u 的路径？确定与某一起点 v 有路相通的所有顶点。 1。宽度优先搜索算法（BFS） 开始：起点 v 和一个空的待访队列 Q。 从顶点 v 开始访问，并将 v 标记为已访问的顶点。然后顺序（这个顺序通 常是图的顶点存储顺序）搜索邻接于顶点 v 的未被访问的顶点，并把这些顶点依 次放在待访队列 Q 的尾部。 用队列 Q 的首元素 u 替换 v（并从队列 Q 中去掉首元素 u），重复以上过程， 直到队列 Q 空为止。 图的宽度优先搜索算法伪代码