21. Tree and Graph Traversals

Depth First Traversals

树的 Depth First Traversals 有三种类型：

• Preorder：
  • 先访问一个节点，然后遍历其子节点（“访问”意味着打印，“遍历”仅仅是到达）
  • 打印顺序：DBACFEG
  • 例如：用于获取某个目录结构
• Inorder：
  • 先遍历左子节点，再访问该节点，然后遍历右子节点
  • 打印顺序：ABCDEFG
• Postorder：
  • 先遍历左子节点，再遍历右子节点，最后访问
  • 打印顺序：ACBEGFD
  • 例如：用于获取某个文件夹内文件总大小

基本思想：先遍历深层节点，再遍历浅层节点（具体演示）

Graph

图的性质：

• 有一组顶点（vertices），也称为节点（nodes）。
• 有一组边（edges）：由成对的顶点组成。
  • 一个顶点可以有零个边或若干个边，每条边只能连接两个节点（和树最大的区别）
  • 如果两个顶点之间有一条边连接，则称它们是相邻的（adjacent）。
• 顶点或边可以带有标签（labels）或权重（weights）。

简单图（simple graph）的性质如下（下文提到的图均指简单图）：

• 一个顶点的边不能连接其自身，即不存在 loop。
• 任意两个相同顶点之间至多只有一条边，即不存在 parallel edge。
• 错误示例：
  

路径和环：

• 路径（path）是由边连接起来的一系列顶点。
• 简单路径（simple path）是没有重复顶点的路径。
• 环（cycle）是起点和终点相同的路径。
• 含有环的图称为循环图（cyclic）。
• 如果两个顶点之间存在路径，则称它们是连通的（connected）；如果图中所有顶点彼此连通，则称该图为连通图（connected graph）。

Depth-First Traversal

s-t Connectivity（DFS 思想）

欲判断上图 s 和 t 是否连通，并记录一条路径，算法核心逻辑为：

• 先标记 s 为已访问（为了防止无限递归。如果不标记 s，它邻居的遍历可能又回到 s）
• 如果 s 就是 t，直接找到
• 否则递归搜索 s 的所有未访问邻居
  • 只要其中一个能连到 t，就返回 true
• 全部都不行，返回 false （演示幻灯片）

这种在移动到下一个邻居前，先完整遍历当前邻居所在整个子图，直到无法继续为止的思想，被称为深度优先遍历（Depth-First Search, DFS）。

DFS Preorder

DFS 可以用于判断 s 与 t 是否连通，并记录一条路径，但不保证最短；无权图最短路径应使用 BFS。

核心逻辑：（依靠实例变量）

• 从当前节点 v 出发
• 先标记 v 为已访问
• 检查 v 的所有邻居 w
  • 如果某个邻居 w 尚未被标记：
    • 记录 edgeTo[w] = v
      • 表示：在搜索过程中，到达节点 w 的路径来自节点 v
      • 最终通过不断回溯 edgeTo：
        • 从目标节点反向追踪到起点
        • 从而还原完整路径
    • 然后在该 w 中重复上述操作，实现递归搜索（完整演示）

特点： 先设置 edgeTo，打印，再递归深入邻居。由此，便保存了整个图的路径关联信息。

打印顺序：012543678

DFS Postorder

特点：先递归深入邻居，到头后，再往回打印

打印顺序：347685210

核心区别：

• Preorder：先处理当前节点，再深入
• Postorder：先深入到底，再处理当前节点

BFS（广度优先遍历）

核心思想：先处理完当前层所有节点，再进入下一层。

打印顺序：0 1 24 53 68 7

BFS 的实现：https://blog.carkree.com/cs61b/22. Graph Traversals and Implementations/