什么是图

在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

图的术语

在图中，最基本的单元是顶点（vertex），相当于树中的节点。顶点之间的关联关系，被称为边（edge）。

在有些图中，每一条边并不是完全等同的。比如刚才地铁线路的例子，从A站到B站的距离是3公里，从B站到C站的距离是5公里......这样就引入一个新概念：边的权重（Weight）。涉及到权重的图，被称为带权图（Weighted Graph）。

图的表示

邻接矩阵

拥有n个顶点的图，它所包含的连接数量最多是n（n-1）个。因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用二维数组（矩阵）。

邻接表和逆邻接表

为了解决邻接矩阵占用空间的问题，人们想到了另一种图的表示方法：邻接表。在邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。

十字链表

十字链表的每一个顶点，都是两个链表的根节点，其中一个链表存储着该顶点能到达的相邻顶点，另一个链表存储着能到达该顶点的相邻节点。

我们没有必要把链表的节点都重复存储两次。在优化之后的十字链表中，链表的每一个节点不再是顶点，而是一条边，里面包含起止顶点的下标。

总结

1. 根据图的边是否有方向，可分为有向图和无向图。根据图的边是否有权重，可分为带权图和无权图。当然，也可以把两个维度结合起来描述，比如有向带权图，无向无权图等等。

2. 图的表示方法有很多种。包括邻接矩阵、邻接表、逆邻接表、十字链表（还有一种邻接多重表，有兴趣的小伙伴可以自学下）。

推荐阅读

漫画：为什么你需要了解数据结构中的图？ (opens new window)