图
复习
- 堆：父不大于子，堆顶是最值
- 优先队列：每次取出最值
- 字典树（进阶）：字典树按字符逐层组织字符串
TL;DR
- 图由节点和边组成，能表示任意两两关系
- 分有向图和无向图
- 边还可以带上权重
- 树其实是图的一种特例
正文
树能表示层次，但它有个限制：每个节点只能有一个父节点，而且不能有环。可现实中很多关系并非如此——朋友之间可以互相认识，城市之间可以互相到达。要表示这种任意两两关系，就需要更一般的结构：图（graph）。
其实我们早就见过图了：前面讲网络路由时，就是把网络抽象成“节点加边”的带权图。
比树更一般
图由两部分组成：
- 节点（顶点）：表示对象
- 边：表示两个对象之间的关系
和树对比一下就很清楚：
- 树里每个节点只有一个父节点，图里的节点可以和很多节点相连
- 树没有环，图可以有环
- 树中任意两点之间通常只有一条路，图中可能有很多条
其实，树就是“无边环、且连通”的一种特殊图。所以图比树更一般，也更能描述复杂的关系。
有向与无向
边还有“方向”之分：
- 无向图：边没有方向，
A—B和B—A是一回事。适合表示互相的关系，比如“朋友” - 有向图：边有方向，
A→B不代表B→A。适合表示单向关系，比如“关注”“依赖”
再进一步，边还可以带上权重，表示距离、费用、时间等。带权的图，就是我们做路径选择时用的那种。
它无处不在
图的建模能力极强，现实里到处都是它的影子：
- 社交网络：人和人的关注、好友关系
- 地图导航：城市与道路
- 任务依赖：谁必须在谁之前完成
只要问题里出现“对象之间的连接”，多半就能抽象成图。 但也正因为连接复杂，怎样把它存进计算机、又怎样在里面“走”，就成了接下来几章的主题。
思考题 1
图和树有什么根本区别？
思考题 2
有向图和无向图，分别适合表示什么样的关系？
小结
知识点
- 图由节点与边构成，表示任意两两关系
- 有向图区分方向，无向图不区分
- 边可以带权重
- 树是图的一种特例
参考资料
- Wikipedia(zh)：图 (数学)：由顶点和边组成的结构
- Wikipedia(zh)：有向图：边具有方向的图
思考题答案（仅供参考）
思考题 1
树要求每个节点最多一个父节点、没有环，且通常连通；图则更一般，节点可以和任意多个节点相连，也允许有环。树可以看成满足特定限制的图。
思考题 2
无向图适合表示互相、对等的关系，比如好友、双向道路；有向图适合表示单向关系，比如关注、依赖、网页链接等“从一方指向另一方”的关系。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪