图

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

一个图G = (V, E)由以下元素组成。

V：一组顶点

E：一组边，连接V中的顶点

度的概念

表示一个顶点又多少条边

• 入度 表示又多少条变指向这个顶点
• 出度 表示这个顶点指出多少条边

邻接矩阵

在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。

• 无向图： 顶点 i 和顶点 j 之间有边，就将A[i][j] 和A[j][i] 标记为1
• 有向图 如果 顶点i和顶点 j之间 ，有一条箭头从i指向 j 将A[i][j] 标记为1
• 有权图，数组存储相应的权重

稀疏图

顶点多，但是每个顶点边并不多

应用：微信号几亿的用户，对应到图上就好几亿的顶点，但是每个用户的好友并不会很多，最多5000，如果用邻接矩阵来存储，那么存储空间都被浪费了

邻接表

邻接矩阵存储比较浪费时间，但是使用起来比较节省时间。相反邻接表存储起来比较节省空间，但是使用就比较浪费时间。

上图是否存在一条从顶点2到顶点4的边，就要遍历顶点2对应的链表

推荐阅读
https://www.jianshu.com/p/bce71b2bdbc8

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/90679421