一、图
1、定义：
描述的是多对多的关系，图是一种网状数据结构，图是由非空的顶点集合和一个描述顶点之间关系(边)的集合组成。
2、分类：
3、图的存储
（1）邻接矩阵：二维数组 顺序存储结构
（2）邻接表：链表 链式存储结构
4、应用：
各种地图，地铁线路图等
二、图的遍历
1、概念
图的遍历就是从图中某个顶点出发，按某种方法对图中所有顶点访问且仅访问一次。
图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
2、方式
（1）深度优先遍历(DFS):类似于树的先根遍历，是树的先根遍历的推广（可以采用递归和借助栈的非递归方式实现）
（2）广度优先遍历(BFS):类似于树的层次遍历，可以借助队列的非递归方式实现。
如：
三、最短路径
1、分类
最短路径1：段数最少的最短路径：
生活案例：换乘最少，或国际象棋AI，计算最少走多少步就可以获胜
解决方案：使用广度优先搜索
实现：对于已检查过结点，已改标记为已检查，且不再检查它。否则可能会导致无限循环，可以使用另外一个列表存放已经检查过的结点，找到即为可达，第一次找到，即为跳转最少，如果到最后队列为空，表明没有路径可达。
最短路径2：权值最小的最短路径
生活案例：时间最少，距离最短
解决方案：使用狄克斯特拉算法
案例：
(1)定义2个数组
(2)先列出v1到各结点的权重，并选择最小的权重，v1到v2权重最小，所以将v2放入S数组
（3）接着，列出v2可以直接到达结点的权重，将列得的权重与之前到v1到v2的最小权重相加，再和原表格中的权重比较，如果小于原数值，则替换掉。然后再将其中最小权重的结点放入S数组
（4）依次类推 v1-v2-v3-v4 v4放入S数组
（5）v1-v2-v3-v4-v6 v6放入S数组
（5）v1-v2-v3-v4-v6-v7 v7放入S数组
中间步骤省略，最终得到结果如下：
得出结论：v1到v8最短路径为12