图

还记得当年学习数据结构时，看到图这章内容，基本上都是略过，大概浏览一遍即完成。主要考试不会涉及这种相对复杂的结构，所以也就大致知道有这么一种数据结构。

图概念

图也是一种非线性结构，比二叉树相对复杂一些，树中的元素我们称之为节点。图中的元素我们称之为顶点，图中的顶点可以和任一顶点进行连接，这种建立连接的关系叫做边。

每个顶点与图中多少个其它顶点连接，连接的个数叫做度。

对于图中顶点与其它顶点的连接，如果有方向的话，则叫做有向图，没有方向的话，则是无向图。有向图则每个顶点又有出度和入度，类似于微博中你关注的微博和你的粉丝。如果像QQ那样好友之间还有一个亲密度的关系，则表示边的权重。权重代表了好友之间的亲密关系

图存储

邻接矩阵：使用一个二维数组进行存储。

无向图：任一两个顶点i和j，有连线则a[i][j] = a[j][i] = 1 , 否则 a[i][j] = a[j][i] = 0

有向图：任一两顶点i和j，存在i指向j的连线则 a[i][j] = 1 , 存在j指向i的连线则 a[j][i] = 1

权重图：任一两顶点i和j，存在权重为w的连线则 a[i][j] = a[j][i] = w.

对于无向图来说其实只要一半的存储就可以，所以说邻接矩阵浪费了一半的内存空间。对于稀疏图来说，顶点很多但是顶点的连线很少的情况，用邻接矩阵存储就浪费了绝大部分内存空间。

优点：1，邻接矩阵的存储方式简单，直接，因为基于数组所以非常高效。2，用邻接矩阵存储图的另一个好处是方便计算。可以将很多图的运算转换成矩阵之间的运算。

邻接表：使用一个一维数组加链表的方式存储，类似于散列表。

数组存储图中所有的顶点，链表存储顶点与顶点的关系。对于无向图来说就是两个顶点相连，对于有向图就是各个顶点箭头的指向。

对于稀疏图来说就特别适合使用邻接表来进行存储。由于顶点间关系相对顶点的数目来说很少，不需要浪费邻接矩阵那么多内存空间。还有一点就是链表存储的顶点间关系，可以使用跳表，散列表，红黑树进行优化。