一起动脑筋 · 先看一个小故事
机器人画出一棵树，又在两个分支之间加了一条线。女孩发现现在可能绕圈了。
把过程摊开来看
- 树连通且没有环
- 增加一条边可能出现环
- 一般图允许更复杂连接
树是图的一种特殊情况。
对无向树，任意两点之间恰有一条简单路径。一般图可能有多条路径，也可能有些点互相到不了。
01树和图是不是完全不同的东西？
不是。
树可以看成一种特殊的无向图。
它满足两个关键条件：
连通
任意两个节点之间都能找到路径。
无环
不存在绕一圈回到原点的简单环。
02一般图可以比树复杂在哪里？
树
连通、无环，常具有层级关系。
一般图
可以有环，可以不连通，连接关系更自由。
03树一定有根吗？
从纯图论角度看，一棵无根树并不一定指定根。
在程序和算法中，我们经常人为选择一个节点作为根，于是就能描述父子、深度和子树。
04树为什么任意两点只有一条简单路径？
因为如果两个点之间存在两条不同简单路径，把它们组合起来就会形成环，这和树“无环”的性质矛盾。
05图里的节点有父亲和孩子吗？
一般图本身没有天然的父子关系。
只有在搜索、生成树或特定有向结构中，我们才可能人为建立“父节点”概念。
06树和图的遍历为什么都能用 DFS / BFS？
因为两者本质上都是“节点 + 边”的连接结构。
DFS 和 BFS 都是在沿着边访问节点，只是访问顺序不同。
图可能有环，所以遍历图时通常尤其需要 visited 记录已访问节点。
你已经知道了什么
- 树可以看成特殊的图。
- 树要求连通且无环。
- 一般图可以有环，也可以不连通。
- 树的根常是人为指定的观察起点。
- 一般图没有天然父子关系。
- DFS/BFS 都可以用于树和图，但图中要特别注意重复访问。
下一篇：怎样为问题选择合适的数据结构？
轮到你来试一试
两个互不连接的点，没有环，能称为一棵无向树吗？
想好了吗？点开看解释
不能，因为不连通。树同时要求连通与无环。