什么是图
图结构是一种与树结构有些相似的数据结构.图论是数学的一个分支，并且，在数学的概念上，树是图的一种。它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系
图的现实案例
(1)人与人之间的关系网
(2)地铁线路图
(3)村庄之间的关系网
…
那么，什么是图呢?
我们会发现，上面的结点(其实图中叫顶点Vertex)之间的关系，是不能使用树来表示.我们使用几叉树都不能模拟.这个时候，我们就可以使用图来模拟它们
图的特点
- 一组顶点：通常用
V(Vertex)表示顶点的集合- 一组边：通常用
E(Edge)表示边的集合
边是顶点和顶点之间的连线
边可以是有向的，也可以是无向的
不如a—b，通常表示无向，a–>b通常表示有向
图的术语
1、顶点：表示图中的某一个节点(比如地铁站中的某个站/多个村庄中的某个村庄…)
2、边：表示顶点和顶点之间的连线
3、相邻顶点：由一条边连接在一起的顶点称为相邻顶点
4、度：一个顶点的度是相邻顶点的数量
5、路径：路径是顶点v1,v2,…vn的一个连续序列
6、简单路径: 简单路径要求不包含重复的顶点,比如0 1 5 9
7、回路：第一个顶点和最后一个顶点相同的路径称为回路,比如0 1 5 6 3 0
8、无向图：所有的边都没有方向(例如 既可以0->1，也可以1->0)
9、有向图：图中的边是有方向的(比如0->1，不能保证一定可以1->0,要根据方向来定)
10、无权图：边没有携带权重(不能说0-1的边比4-9的边更远或者用的时间更长)
11、带权图：带权图表示边有一定的权重，这里的权重可以是任一你希望表示的数据(比如距离或者花费的时间或者票价)
图的表示
怎么在程序中表示图呢？
我们知道一个图包含很多顶点，另外包含顶点和顶点之间的连线(边)，这两个都是非常重要的图信息，因此都需要在程序中体现出来
顶点的表示相对简单：
我们可以抽象成1 2 3 4,也可以抽象成A B C D.那么这些我们可以使用一个数组来存储起来(存储所有的顶点).当然 A, B, C, D有可能还表示其他含义的数据(比如村庄的名字)
那么边怎么表示呢？
因为边是两个顶点之间的关系，所以表示起来会比较麻烦？
一种比较常见的表示图的方式：邻接矩阵
邻接矩阵让每个节点和一个整数相关联，该整数作为数组的下标值
我们用一个二维数组来表示顶点之间的连接
邻接矩阵的问题：
邻接矩阵还有一个比较严重的问题，你就是如果图是一个稀疏图.那么矩阵中将存在大量的0，这意味着我们浪费了计算机存储空间来表示根本不存在的边
另外一种常见的表示图的方式：邻接表
邻接表由图中每个顶点以及顶点相邻的顶点列表组成.这个列表有很多方式来存储：数组/列表/字典(哈希表)都可以
邻接表的问题：
邻接表计算“出度”是比较简单的（出度：指向别人的数量，入度：指向自己的数量）
邻接表如果需要计算有向图的“入度”，那么是一件非常麻烦的事情
它必须构造一个“逆邻接表”，才能有效的计算“入度”，但是开发中“入度”相对用的比较少