什么是图？

图是一种复杂的非线形数据结构，由若干个顶点和连结顶点之间的边组成，根据不同的性质，图可以分为有权图和无权图，有向图和无向图，连通图和非连通图。

在线性结构中，数据节点之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继。

在树形结构中，数据节点之间有着明显的层次关系，并且每个数据节点只与上一层中的一个节点及下一层的多个节点相关。

而在图形结构中，节点之间的关系是任意的，图中任意两个数据节点之间都有可能相关。

图是由顶点和边组成，顶点之间通过边来连结，我们一般用符号G = (V, E)来表示图，V表示顶点的集合，E表示边的集合。

根据边是否有方向，可以将图分为有向图和无向图，上面的图是无向图，边(1,2)也可以表示为(2,1)，但是在有向图中，边是有方向的，所以边(1,2)和边(2,1)是不同的两条边。

根据边是否有权重，分为有权图和无权图，上面两个都是无权图，下面这个是有权图

如果图中任意两个顶点都有路径连通，则称为连通图，如果不能则称为非连通图。上面看到的都是连通图，下面这个就是非连通图。

在代码实现中，经常会用两种方式来表示图

1. 邻接矩阵，用一个n*n二维数组G来表示，n是图中顶点的个数，在无权图中，G[i][j]表示顶点i和顶点j是否有边，在有权图中，G[i][j]表示边的权值，在无向图中，G[i][j]和G[j][i]应该相等。
2. 邻接表，用长度为n的数组G+链表的形式表示，n是图中顶点的个数，G[i]表示顶点i，而以G[i]为头节点所指向的链表，表示顶点i与其它顶点所连结的边。

用邻接矩阵表示图

用邻接表表示图

邻接矩阵的优缺点

优点：操作简单，查找、添加和移除某条边非常容易而且高效。

缺点：消耗的内存空间等于顶点的平方数，如果图的边数较少¹，则会浪费大量的内存空间。

邻接表的优缺点

优点：节约内存空间，因为只需要存储实际存在的边。

缺点：操作麻烦，查找和删除都需要遍历链表，效率低。