图

图是用来表示“事物以及它们之间的连接”的数据结构。事物称为顶点（或节点），连接称为边。几乎一切带有关系的东西都能套进这个图景：用道路相连的城市、互为好友的人、彼此链接的网页、互相依赖的任务。每当你下意识地画一些点、再用线把它们连起来时，你画的就是一张图。

图有不同的种类。在无向图中，A 与 B 之间的边是双向的（好友关系：A 认识 B，则 B 也认识 A）。在有向图中，每条边都有方向，是从一个顶点指向另一个顶点的箭头（单行道，或社交媒体上的“A 关注 B”）。边还可以带权，携带一个数值，例如距离、成本或容量；无权图则只记录连接是否存在。设有 V 个顶点、E 条边，这两个量决定了几乎所有图算法的开销。

图比树更一般：树不过是没有环的连通图。图可以有环、可以分成互不相连的几块、同一对顶点之间也可以有多条路径——这正是图能很好地刻画纷繁现实的原因，也正因如此，遍历时必须小心（以免永远重复访问同一个顶点）。