图是由顶带点和边构成的，因此如何表示图，就是如何表示顶点和边，而边又是由两个顶点构成的，因此表示边其实就是表示两个顶点之间的关系。

邻接矩阵

我们可以用一个一维数组表示所有的顶点，一个二维数组表示顶点之间的关系，如果两个顶点构成边，则对应二维数组元素标记为1，如果有权则标记为权值，否则标记为0（有权图标记为自定义的无穷大）。如下图所示：

如果表示的图是有向图，则其第i行非0元素的总和就是结点vi的出度，低i列非0元素的总和就是结点vi的入度。

如果有向图是加权的，则把1改成权值即可，如图所示：

而对于无向图，其第i列和第i行的非0元素总和都可以表示顶点vi的度。并且无向图的邻接矩阵一定是对称的矩阵，如图所示：

同理，如果无向图也加权，将权值替换1，无穷大替换0即可。

邻接表

邻接表就是存放顶点的数组的每个元素添加一个指针域，然后对每个顶点 vi 建立一个单链表，把与vi有关联的顶点连接成一个单链表，链表表中每个结点都设为3个域（如果是不加权的图也可以使用2个域），如图所示：


上面两张图就是加权和不加权的不同结构，但是其表示图的思想都是一样的。邻接表也都可以表示无向图和有向图，如图所示：

注意： 顶点所指链表不一定就是出度边相关顶点，完全也可以入度边相关顶点，前者是找出度易而找入度难，后者是找入度易而找出度难。

邻接矩阵和邻接表的对比

采用邻接矩阵的存储方式易于实现图的各种基本操作，但是当图的边很少的时候，关系数组中含有大量的0或者无穷大元素，空间利用率很低，因此邻接矩阵的方法适合存储稀疏图。邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。

而邻接表的优点就是能够节约大量没有意义的内存空间，只存储了有关联的顶点关系，非常适合存储稀疏图。而其缺点也显而易见，就是求顶点度的时候比较困难，需要遍历顶点的整个链表。而且如果需要删除一条边，就需要在两个链表上查找并删除。