CS61B 课程笔记：图结构基础与深度优先遍历
树与遍历回顾
在深入图（Graph）之前，我们先快速回顾一下树的遍历方式。树可以看作是图的一种特例，其遍历主要包含三种顺序：前序（Preorder）、中序（Inorder）和后序（Postorder）。这三种方式的区别在于根节点被访问的时机。
- 前序遍历：首先访问根节点，再递归处理子树。
- 中序遍历：先访问左子树，再访问根节点，最后访问右子树。
- 后序遍历：先处理左右子树，最后访问根节点。
树形结构非常适合文件管理场景，递归遍历能方便地统计文件夹下的文件总数。
图的基本概念
图是比树更广义的数据结构。树要求任意两点之间有且只有一条路径，而图允许存在环（Cycle），甚至允许两点之间不相连。
这种结构之所以称为 Graph，是因为它更接近几何图形，由顶点（Vertex）和边（Edge）组成。顶点可以编号或设置权重。
- Path（路径）：一系列通过边相连的顶点。
- Simple Path（简单路径）：不经过重复顶点的路径。
- Cycle（环）：起始顶点和终止顶点相同的路径。
- Connected（连通）：如果两个顶点之间存在路径，则称它们相连；若图中所有顶点都相互连通，则该图为连通图。
图的分类主要有两种维度：
- 有无环：分为无环图（Acyclic）和有环图（Cyclic）。
- 方向性：分为有向图（Directed）和无向图（Undirected）。
