CS61B 课程笔记:图结构基础与深度优先遍历
树与遍历回顾
在深入图(Graph)之前,我们先快速回顾一下树的遍历方式。树可以看作是图的一种特例,其遍历主要包含三种顺序:前序(Preorder)、中序(Inorder)和后序(Postorder)。这三种方式的区别在于根节点被访问的时机。
- 前序遍历:首先访问根节点,再递归处理子树。
- 中序遍历:先访问左子树,再访问根节点,最后访问右子树。
- 后序遍历:先处理左右子树,最后访问根节点。
树形结构非常适合文件管理场景,递归遍历能方便地统计文件夹下的文件总数。

图的基本概念
图是比树更广义的数据结构。树要求任意两点之间有且只有一条路径,而图允许存在环(Cycle),甚至允许两点之间不相连。

这种结构之所以称为 Graph,是因为它更接近几何图形,由顶点(Vertex)和边(Edge)组成。顶点可以编号或设置权重。
- Path(路径):一系列通过边相连的顶点。
- Simple Path(简单路径):不经过重复顶点的路径。
- Cycle(环):起始顶点和终止顶点相同的路径。
- Connected(连通):如果两个顶点之间存在路径,则称它们相连;若图中所有顶点都相互连通,则该图为连通图。

图的分类主要有两种维度:
- 有无环:分为无环图(Acyclic)和有环图(Cyclic)。
- 方向性:分为有向图(Directed)和无向图(Undirected)。







